Question concerning a sequence in GAP

Question

I would like to know, what's the best (fastest) way to programm the following in GAP (perhaps using some functionality from the QPA package):

Input:

$n\geq 2$

Output:

A list of all sequences ${(c_i)}_{i=0}^{n-1}$ with the following properties:

$\bullet$ $2\leq \min \{c_i\ |\ i=0,...,n-1\}=c_0 \leq n+1$

$\bullet$ $c_{n-1}=c_0+1$

$\bullet$ $c_{i-1}-1\leq c_i$ for $i=1,...,n-1$

Example: The case $n=3$ should give the following result:

$[[2,2,3],[2,3,3],[2,4,3],[3,3,4],[3,4,4],[3,5,4],[4,4,5],[4,5,5],[4,6,5]]$.

Thanks for the help.

Answer 1

Sorry but I couldn't render this properly in mathjax, but copy-past will work. I hope this gives the result.

fun:=function(n)
local c0,cn_1,T,t,s,ret;
ret:=[];
for c0 in [2..n+1] do 
    cn_1:=c0+1;
    T:=Tuples([c0..cn_1+1],n-2);
    for t in T do 
        s:=Concatenation([c0],t,[cn_1]);
        if ForAll([2..n],i->s[i-1]-1<=s[i]) then 
            Add(ret,s); 
        fi;
    od;
od;
return ret;
end;

Update: this is a little bit more fine-tuned version of the function above. First, I've switched to IteratorOfTuples to avoid filling up the memory with tuples and then throwing some of them away when the condition checked by ForAll fails. Second, a very important observation is to not use Concatenation with multiple lists. In

s:=Concatenation([c0],t,[cn_1]);

first a new list l is created to concatenate the 1st two arguments, and then another new list will be created to copy over the list l and then [cn_1]. I've reduced at least one copying of the list t by concatenating the first two lists and then adding the last element to the result.

fun2:=function(n)
local c0,c,cn_1,T,t,s,ret;
ret:=[];
for c0 in [2..n+1] do 
    c := [c0];
    cn_1:=c0+1;
    T:=IteratorOfTuples([c0..cn_1+1],n-2);
    for t in T do 
        s:=Concatenation( c, t );
        s[n]:=cn_1;
        if ForAll([2..n],i->s[i-1]-1<=s[i]) then 
            Add(ret,s);
        fi;
    od;
od;
return ret;
end;

It now produces the result for $n=15$ a little bit faster:

gap> fun(15);;time;
104102
gap> fun2(15);;time;      
89032

Also, it does not run out of memory immediately for $n=20$ but I am not enough patient to wait till it enumerates just 387420489 tuples of length 18 from [2..4] even on the first iteration :-)

So, for $n=20$ this already looks impractical. I may have some further ideas to suggest:

• There are many tuples which are generated and then thrown away because the condition ForAll([2..n],i->s[i-1]-1<=s[i]) fails. One may try to write an own function to generate all tuples satisfying such restriction instead of using Tuples or IteratorOfTuples. Maybe this will be faster, but beware that already for $n=15$ we have $4767165$ tuples in the result.

• The condition always fails "in the middle", so it is the tuple t which either satisfies it or not. Hence, we may select "good tuples" of length $n-2$ for [1..3] once, and then use that to construct all good tuples of length $n-2$ for [c0..c0+2]. This will not help with $n=20$ since one still to pass through the first iteration, but may speed up smaller cases.

Update 2: I've implemented my suggestion about selecting "good" tuples first. Note the following piece of GAP syntax:

gap> r:=[11..13];
[ 11 .. 13 ]
gap> t:=[1,2,3,2,1,3,2,1,1];
[ 1, 2, 3, 2, 1, 3, 2, 1, 1 ]
gap> r{t};       
[ 11, 12, 13, 12, 11, 13, 12, 11, 11 ]

So, the third version of the function is

fun3:=function(n)
local c0,c,cn_1,T,t,s,good,range,ret;
ret:=[];
good:=[];
T:=IteratorOfTuples([1..3],n-2);
# selecting patterns of "good" tuples
for s in T do
    if ForAll([2..n-2],i->s[i-1]-1<=s[i]) then 
        Add(good,s);
    fi;
od;
# creating tuples from patterns 
for c0 in [2..n+1] do 
    c := [c0];
    cn_1:=c0+1;
    range := [c0..cn_1+1];
    for t in good do 
        s:=Concatenation( c, range{t} );
        s[n]:=cn_1;
        Add(ret,s);
    od;
od;
return ret;
end;

This version is more than 7 times faster for $n=15$:

gap> fun(15);;time;         
104176
gap> fun3(15);;time;
14318

It took 40 seconds for $n=16$, but choke on $n=17$. Anyhow, perhaps you may modify our code and process the resulting tuples as soon as they are generated instead of storing them, so hope this is of some help. Would be interesting to know what are the values of $n$ for which you're interested to calculate this in practice.