[GAP Forum] combinations

[Frank Lübeck]

On Fri, Aug 06, 2010 at 09:58:11AM -0400, R. Keith Dennis wrote:
> I've been trying to do some tests where I look at certain combinations of
> subgroups and take intersections.  I've been using
> 
> Combinations([1..m],k);
> 
> which works fine as long as Binomial(m,k) is small enough.  When the number
> is very large, then there is a memory problem & one can't even look at a few
> example combinations.  Presumably the program is recursively computing all
> combinations & runs out of memory.
> 
> Now this may well be simply because I haven't used the right GAP command.
> I'd appreciate it if someone would point out the correct way to use a 
> built-in command if there is one.

Dear Keith, dear Forum,

Sorry for the late response (because of summer holidays). 

The current release 4.4.12 of GAP has no builtin functionality for
memory efficient looping over large sets of combinations. 

> In the meantime I solved the problem a different way, namely I wrote a 
> program that generates one combination at a time using only the preceding 
> one.  See below:
> [...]

GAP has a concept for this, see '?Iterators' in the help system. 
Your code could be easily turned into a proper iterator using
'IteratorByFunctions'. 

In fact, the next GAP release will contain code for
  IteratorOfCombinations( mset[, k] );
and 
  EnumeratorOfCombinations( mset );
(I don't know how to do a (mset, k)-version of the enumerator).
They are a bit more general than your code because they work for all
multisets mset (not only the set [1..m]). 

Examples:

gap> i := 0;;
gap> mset := "aabcdddefghijjklmnopqrrrstuvw";
gap> for c in IteratorOfCombinations(mset,10) do i := i+1; od; time;
8241
gap> i;
3244707
gap> NrCombinations(mset,10);
3244707
gap> en := EnumeratorOfCombinations(mset);;
gap> Length(en);
75497472
gap> en[50000000];
"acddfjjlpqsuw"
gap> Position(en, "bcddfhikl");
15106

If someone wants to use this functionality in the current GAP release,
fetch the file
  http://www.math.rwth-aachen.de/~Frank.Luebeck/tmp/itercomb.g
and read it into your GAP session.

> The GAP manual says a lot about random generation of various kinds.  No 
> doubt there must be a way to do the following or something similar 
> with a built-in command.  What's the correct way to generate a random
> permutation of a list?
> 
> I've been using the following (more or less copying the idea from
> perl):
> 
> FisherYates:=function(seq)
>     local i,j,l,t;
>     #  Fisher-Yates shuffle:
>     #  generate a random permutation of array in place
>     l:=Length(seq);
>     for i in [l,l-1..1] do
>         j:=Random(1,i);
>         t:=seq[i];
>         seq[i]:=seq[j];
>         seq[j]:=t;
>     od;
>     return seq;
> end;

Yes, provided Random(1,i) yields uniformly random integers, this function 
applies a uniformly random permutation to the list seq. 
I usually use 
   seq := Permuted(seq, Random(SymmetricGroup(Length(seq))));
for this, and the algorithm in the background is exactly the same as in
the code shown above. 
Maybe we should put a 'Shuffle(list)' into the library.

Best regards,
  Frank

-- 
///  Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64,  ///
\\\                    52062 Aachen, Germany                          \\\
///  E-mail: Frank.Luebeck at Math.RWTH-Aachen.De                        ///
\\\  WWW:    http://www.math.rwth-aachen.de/~Frank.Luebeck/           \\\