Finding lists as fast as possible via GAP

Question

Call a list with $n$ entries $[c_0,c_1,...,c_{n-1}]$ an n-LNakayama algebra in case the following conditions are satisfied:

• $c_i \geq 2$ are natural numbers for $i \neq n-1$ and $c_{n-1}=1$.

• $c_i -1 \leq c_{i+1}$ for all $i=0,1,...,n-2$.

I managed to program this, imitating the programme of ahulpke here: Finding elements of cartesian product satisfying a set of constraints in GAP .

Here the program:

BuildSequencesLNak:=function(n)
local all,range,len,new,seq,i,sel;
all:=[[1]];
range:=[2..n];
for len in [1..n-1] do
    new:=[];
    for seq in all do
        sel:=Filtered(range, x->x<=1+seq[1]);
        for i in sel do
            Add(new,Concatenation([i],seq));
        od;
    od;
    all:=new;
od;
return all;
end; 

Call an index $i$ projective-injective in case $c_i \geq c_{i-1}$ (setting $c_{-1}=1$ and calculating mod $n$ for the indices).

Now call a $n$-LNakayama algebra special in case the following is true:

In case $i$ is projective-injective, also $i+r$ is projective injective for every $r=c_{i-1},c_{i-1}+1,...,c_i -1$ (no condition for this $i$ in case $c_{i-1}=c_i -1$).

I can program also this by using Filtered in GAP after making the list of all n-LNakayama algebras with the above program BuildSequencesLNak, but it is not as fast as I want and so I wonder how to make it faster.

I can get the list for about n=16 and then it loads very long. I would hope that with a somehow better program one might get to n=21 or 22 to test some conjectures.

Example: All 5-LNakayama algebras: [ [ 2, 2, 2, 2, 1 ], [ 3, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 3, 3, 2, 2, 1 ], [ 4, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 3, 2, 3, 2, 1 ], [ 2, 3, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ], [ 4, 3, 3, 2, 1 ], [ 2, 4, 3, 2, 1 ], [ 3, 4, 3, 2, 1 ], [ 4, 4, 3, 2, 1 ], [ 5, 4, 3, 2, 1 ] ]

The special ones among them:

[ [ 2, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 3, 3, 3, 2, 1 ] ]

The number of n-LNakayama algebras should be $C_{n-1}$, the Catalan numbers. The number of special n-LNakayama algebras should be given by https://oeis.org/A005043 (at least for $n \leq 15$), although I know no proof.

Answer 1

Two obvious speed improvements are to replace sel with an immediate bound calculation and to build the list in reverse order, avoiding Concatenation and a list of length 1, that is the inner loop becomes

    for i in [2..seq[Length(seq)]+1] do
      nl:=ShallowCopy(seq);
      Add(nl,i);
      Add(new,nl);
    od;

However a back-of-an envelope calculation indicates that for $n=21$ memory use might be prohibitive. You might have to think about reducing intermediate storage and discarding sequences that are not special.