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

[Richard O'Keefe]

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.