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

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.