[GAP Forum] combinations

[R. Keith Dennis]

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.

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:

[I carry along the combination number in position n+1 as well as the
total number of combinations in position n+2 as that is convenient for
further use.]

InitComb:=function(m,n)
    local B,seq;
    B:=Binomial(m,n);
    seq:=[1..n];
    Append(seq,[1]);
    Append(seq,[B]);
    return seq;
end;

NextCombination := function(m,n,seq)
    local i,j;
    if(seq[n+1]<=seq[n+2]) then    
        seq[n+1]:=1+seq[n+1];
        for i in [n,n-1..1] do
            if(seq[i]<m-(n-i)) then
                seq[i]:=1+seq[i];
                for j in [i+1..n] do
                    seq[j]:=1+seq[j-1];
                od;
                return seq;
            fi;
        od;
    fi;
end;

ListComb:=function(m,n)
    local seq,test;
    seq:=InitComb(m,n);
    test:=true;
    while(test) do
        Print(seq,"\n");
        if(seq[n+1]=seq[n+2]) then
            test:=false;
            continue;
        fi;
        seq:=NextCombination(m,n,seq);
    od;
end;

If something equivalent to "NextCombination" is already available in GAP,
I'd appreciate learning that.  If not, this are something similar might be
a useful addition to the next version.


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;


thanks.

Keith