Anonymous user
Permutations by swapping: Difference between revisions
Added iterative/lazy version
(Updated both D entries) |
(Added iterative/lazy version) |
||
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(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>
| |||