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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
