Permutations by swapping: Difference between revisions
Content added Content deleted
(Updated both D entries) |
(Added iterative/lazy version) |
||
Line 1,481: | Line 1,481: | ||
L(4,3,2,1), L(3,4,2,1), L(3,2,4,1), L(3,2,1,4), L(2,3,1,4), L(2,3,4,1), |
L(4,3,2,1), L(3,4,2,1), L(3,2,4,1), L(3,2,1,4), L(2,3,1,4), L(2,3,4,1), |
||
L(2,4,3,1), L(4,2,3,1), L(4,2,1,3), L(2,4,1,3), L(2,1,4,3), L(2,1,3,4) ) |
L(2,4,3,1), L(4,2,3,1), L(4,2,1,3), L(2,4,1,3), L(2,1,4,3), L(2,1,3,4) ) |
||
</pre> |
|||
An iterative, lazy version, which is handy as the number of permutations is n!. Uses "Even's Speedup" as described in the Wikipedia article: |
|||
<lang zkl> fcn [private] _permuteW(seq){ // lazy version |
|||
N:=seq.len(); NM1:=N-1; |
|||
ds:=(0).pump(N,List,T(Void,-1)).copy(); ds[0]=0; // direction to move e: -1,0,1 |
|||
es:=(0).pump(N,List).copy(); // enumerate seq |
|||
while(1) { |
|||
vm.yield(es.pump(List,seq.__sGet)); |
|||
// find biggest e with d!=0 |
|||
reg i=Void, c=-1; |
|||
foreach n in (N){ if(ds[n] and es[n]>c) { c=es[n]; i=n; } } |
|||
if(Void==i) return(); |
|||
d:=ds[i]; j:=i+d; |
|||
es.swap(i,j); ds.swap(i,j); // d tracks e |
|||
if(j==NM1 or j==0 or es[j+d]>c) ds[j]=0; |
|||
foreach e in (N){ if(es[e]>c) ds[e]=(i-e).sign } |
|||
} |
|||
} |
|||
fcn permuteW(seq) { Utils.Generator(_permuteW,seq) }</lang> |
|||
<lang zkl>foreach p in (permuteW(T("a","b","c"))){ println(p) }</lang> |
|||
{{out}} |
|||
<pre> |
|||
L("a","b","c") |
|||
L("a","c","b") |
|||
L("c","a","b") |
|||
L("c","b","a") |
|||
L("b","c","a") |
|||
L("b","a","c") |
|||
</pre> |
</pre> |