[plt-scheme] Combinations

On Jun  3, Iain Gray wrote:
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> 
> Does anyone know of an efficient way of generating the combinations of 
> k  objects from n objects? I could generate permutations and then 
> filter out on set equality, but my example is largish in choosing 4 
> from 70.
> 
> Any advice would be appreciated.

There was a discussion a while ago on c.l.scheme about computing the
list of all n-sized subsets.  Several different solutions were
suggested.  I made some graphs showing the differences.  You can see
that and get the source at

  http://scheme.barzilay.org/subsets/

(but if you want to know who wrote the different solutions, you'll
need to dig through the newsgroup.)

The point that I was trying to make is a good one -- memoization is
your friend.  You'll see that it performs as good as the other ones,
but the code is ridiculously smaller.

As for your problem -- a good solution is probably similar.  The least
you can do is use one of these things to get the list of subsets, then
permute them one by one.  But if your numbers are always a large input
and a small output, then things might be different.

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!