Finding elements of cartesian product satisfying a set of constraints in GAP

Question

Given a fixed positive integer $n \geq 3$, I want to generate a list of lists in gap with the following properties: each list has $n$ entries $a_0,a_1,\ldots,a_{n-1}$. We have:

• $\min(a_0,a_1,\ldots,a_{n-1})=a_0 \geq2$
• $a_0 \leq n+1$
• $a_{n-1}=a_0+1$ and $a_i -1 \leq a_{i+1}$ for $i=0,\ldots,n-2$. What is the easiest way to do this in gap?

edit: I modified the above conditions a little because its enough to look at a little smaller class of such lists.(in fact $a_0 \leq n+1$ implies that the maximum of all $a_i$ has a good bound)

here is an example for n=6 :

L:=Cartesian([2,3,4,5,6,7],[2,3,4,5,6,7,8,9,10,11,12],
[2,3,4,5,6,7,8,9,10,11,12],[2,3,4,5,6,7,8,9,10,11,12],
[2,3,4,5,6,7,8,9,10,11,12],[3,4,5,6,7,8]);

LL:=Filtered(L, x->Minimum(x)>=2 and 
                x[6]=x[1]+1 and 
                Minimum(x)=x[1] and 
                x[2]-1 <=x[3] and 
                x[3]-1<=x[4] and 
                x[4]-1<=x[5] and 
                x[5]-1<=x[6]);

Using Cartesian, gap in combination with my computer isn't able to do this even for n=8.

By the way the motivation behind this is that those lists parametrise nonselfinjective Nakayama algebras with certain Kupisch series of theoretical interest. here is the number of such lists: https://oeis.org/A007946

it doesn't grow that much, so how can i avoid generating large lists and then have to filter?

Answer 1

If you try to build all sequences and then only select the ones which satisfy your condition you produce a lot of waste and then need to look through all of it. It will be much more effective to build the sequences entry by entry while satisfying your condition. Observe that the $a_0+1=a_{n-1}$ condition gives you the last entry, so one only needs to build of length $n-1$ and then check the condition that $a_{n-2}<=a_0+2$, finally adding the required last entry.

The condition on the last entry, together with the fact that the sequence cannot descend by more than $1$ in each step also means that $a_i\le a_0+n-i$ which substantially reduces on intermediate lists to be thrown away.

Since lists in GAP start indexing at 0 there is a trivial index shift.

The easiest way is clearly having someone else write the code. Thus, since its Christmas, here is a function that does so:

*New version of code based on changed conditions *

BuildSequences:=function(n)
local all,range,len,new,seq,i,sel;
  all:=[[]]; # start with empty
  range:=[2..2*n-1]; # valid entries
  for len in [1..n-1] do # build sequences in increasing length
    new:=[];
    for seq in all do
      # extend with all possible values based on condition
      if len=1 then
        sel:=[2..n+1]; # otherwise last entry is too large
      else
        sel:=Filtered(range,x->x>=seq[len-1]-1 and x>=seq[1]
               and x<=seq[1]+n-len+1);
      fi;
      for i in sel do
        Add(new,Concatenation(seq,[i]));
      od;
    od;
    all:=new;
  od;
  # Can we add the last entry while remaining valid?
  all:=List(all,x->Concatenation(x,[x[1]+1]));
  return all;
end;

It produces some overhead but far less than trying all sequences would do so. It produces counts 8, 35, 139, 539, 2078, 8007, 30887, 119339, 461889 that are consistent (difference 1) with the linked OEIS entry.

Answer 2

I will post another answer just to illustrate the use of iterators of cartesian products in case they may be useful for the readers of this question (but of course, this approach does not lead you that far in this particular problem as the code provided in @ahulpke's answer).

Starting from your example for $n=6$, the call to Cartesian creates a huge overhead since first GAP actually generates a list of 527076 tuples, and then filters them to pick only 540 ones satisfying the constraints:

gap> L:=Cartesian([2,3,4,5,6,7],[2,3,4,5,6,7,8,9,10,11,12],
> [2,3,4,5,6,7,8,9,10,11,12],[2,3,4,5,6,7,8,9,10,11,12],
> [2,3,4,5,6,7,8,9,10,11,12],[3,4,5,6,7,8]);;
gap> Size(L);
527076
gap> LL:=Filtered(L, x->Minimum(x)>=2 and 
>                 x[6]=x[1]+1 and 
>                 Minimum(x)=x[1] and 
>                 x[2]-1 <=x[3] and 
>                 x[3]-1<=x[4] and 
>                 x[4]-1<=x[5] and 
>                 x[5]-1<=x[6]);;
gap> Length(LL);
540

This is how to do the same using iterator, enumerating tuples one by one instead of generating the whole list at once:

gap> L:=IteratorOfCartesianProduct([2,3,4,5,6,7],[2,3,4,5,6,7,8,9,10,11,12],
> [2,3,4,5,6,7,8,9,10,11,12],[2,3,4,5,6,7,8,9,10,11,12],
> [2,3,4,5,6,7,8,9,10,11,12],[3,4,5,6,7,8]);
<iterator>
gap> LL:=[];
[  ]
gap> for x in L do
> if Minimum(x)>=2 and 
>   x[6]=x[1]+1 and 
>   Minimum(x)=x[1] and 
>   x[2]-1 <=x[3] and 
>   x[3]-1<=x[4] and 
>   x[4]-1<=x[5] and 
>   x[5]-1<=x[6] then
>     Add(LL,x);
>   fi;
> od;
gap> Length(LL);
540

Iterators provide a possibility to loop over the elements of a (countable) collection or list, without repetition, and this is exactly the case for IteratorOfCartesianProduct. For many collections, an iterator over them need not store all their elements (it's even possible to construct an iterator of some infinite domains, such as the field of rational numbers).