[GAP Forum] combinations

[Joe Bohanon]

Keith and forum

Two things to try.

1. Run until you hit the "you've run out of memory" break loop.  From in
here you can access the local variables of the "Combinations" function.
Grab however many you want, print to disk and start GAP again.

2. Try
g:=Random(SymmetricGroup(m));
List([1..k],i->i^m);

It's not systematic, but at least you can find a few random ones to test
whatever you want.

Joe

Joe

On Fri, Aug 6, 2010 at 9:58 AM, R. Keith Dennis <gap at rkd.math.cornell.edu>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.
>
> 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
>
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>