# Question:ISO Faster method of generating specific permutations of a list

## Question:ISO Faster method of generating specific permutations of a list

Maple

Situation:  I have multiple lists of the form [i\$i=1..n,0\$k] , where n is a positive integer and k is a nonegative integer.

Desired result:  For each list, produce a list of permutations of the list (as you would receive from combinat[permute]) such that in each permutation, the nonnegative integers in the list appear in ascending order from left to right and no two nonnegative integers are adjacent to one another.

Currently, I produce such a list of permutations by first producing a list of permutations such that all the nonnegative integers are in ascending order:

P:= proc(n,k) select( a->evalb( subs(0=NULL,a) = subs(0=NULL,sort(a)) ), combinat[permute]( [i\$i=1..n, 0\$k] ) ); end proc:

Then, I remove any permutations in that list that have two nonnegative integers adjacent to one another.  I provide no example of how I accomplish this, becuase my problem lies in the generation of the full list of permutations.

As n and k grow, the amount of (needless) computation rises dramatically.  Maple simply fails when n=6 and k=8  (I have not experimented to find a lowest threshold where the object from combinat[permute] becomes too large).  In an attempt to bypass this limitation, I copied the procedure combinat[permute1] and added a check:

my_permute1:= proc(a,r)
local i,k,p,t;
if r=0 then [[]] else
p:=NULL;
for i to nops(a) do
member(a[i],a,'k');
if k<i then next fi;
t := procname(subsop(i=NULL,a),r-1);
p := p, seq(a[i],op(k)],k=t);
od:
select( a-> evalb( subs(0=NULL,a) = subs(0=NULL,sort(a)) ), [p]);
fi;
end proc:

This has (thusfar) kept my lists of permutations from growing too large before they can be culled; however, this process is still extremely processor-intensive.  I'm looking for any insights that anyone may have as to how to generate these permutations in a matter of seconds rather than the minutes these larger lists require.

Thank you. ﻿