On Mar 15, 2010, at 8:37 PM, Magicloud Magiclouds wrote:
Sorry, I did not make it clear, since I did not know how to say this in technical terms.
Technical terms are not necessary, but absent those, clear examples are.
With comprehension, I could get all the possibilities that "draw one elem from each list and put them together". But consider this: for example, there are two types of pet, dog and cat. And there are two persons, him and her. So "how many kinds of matches are there (orderless)?" The answer is two: "him with dog and her with cat, him with cat and her with dog".
Why can't they _both_ have cats, or _both_ have dogs? I _think_ you mean that there is one man and one woman and not two _types_ of pets, but one dog and one cat. So if the man gets the dog, there is no dog left for the woman to get. Let me offer you a building block: select :: [t] -> [(t,[t])] Given a list, select lazily returns a list of (item,rest) pairs, where item is an element of the original list, and rest is everything else in the original list, in the original order. select xs = choices xs [] where choices (x:xs) before = (x,reverse before++xs) : choices xs (x:before) choices [] _ = [] Example: select [1,2,3] = [(1,[2,3]),(2,[1,3]),(3,[1,2])] Now suppose you have any number of people and any number of pets and want to match up each person with a unique pet (but don't care if any pets are left over): matchings :: [a] -> [b] -> [[(a,b)]] matchings [] _ = [[]] matchings (h:hs) ps = [(h,p) : m | (p,ps') <- select ps, m <- matchings hs ps'] Example: matchings ["him","her"] ["bug","cat","dog"] = [ [("him","bug"),("her","cat")], [("him","bug"),("her","dog")], [("him","cat"),("her","bug")], [("him","cat"),("her","dog")], [("him","dog"),("her","bug")], [("him","dog"),("her","cat")] ] It should now be obvious how to extend this to more than two lists. It should also be obvious that this can be expensive. If there are N items in both xs and ys, then matchings xs ys has N! elements. More generally, if xs has M elements and ys has N elements and M <= N, matchings xs ys has M-to-the-falling-N = M!/(M-N)! elements (if I've got this right). You want to consider whether there are other constraints on acceptable solutions that should be applied early to reduce the number of candidates.