\\ known Andre permutations
andre = [0];

\\ encode a permutation (in base 10)
encode(p) = fromdigits(Vec(p))

\\ is known Andre permutation?
is(p) = setsearch(andre, encode(p))

\\ index of 1
one(p) = for (k=1, oo, if (p[k]==1, return (k)))

\\ flatten permutation (so that the domain is 1..#p)
flatten(v) = {
	my (w=Set(v));
	apply(k -> setsearch(w, k), Vec(v))
}

\\ check if p is an Andre permutation
checked = [0]
nb = 0
check(p) = {
	my (ok=0);
	if (#p<=1,
		ok = 1,
		my (mi=one(p));
		if (mi<#p
		    && vecmin(p[mi+1..#p])==2
			&& is(flatten(p[1..mi-1]))
			&& is(flatten(p[mi+1..#p])),
			ok = 1
		);
	);
	if (ok,
		if (#checked<nb++,
			checked = concat(checked, vector(#checked));
		);
		checked[nb] = encode(p);
	);
}

{
	for (w=1, 9,
		old = #andre;
		nb = 0;
		forperm (w, p, check(p));
		andre = setunion(andre, Set(checked[1..nb]));
		for (n=old+1, #andre,
			print (n-1 " " andre[n]);
		);
	);
}

quit