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@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
