[Haskell-cafe] How to do the "permutation and combination" thing?

Richard O'Keefe ok at cs.otago.ac.nz
Mon Mar 15 19:08:33 EDT 2010

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.