Anonymous user
Permutations by swapping: Difference between revisions
Added zkl
(Added Ruby) |
(Added zkl) |
||
Line 1,385:
Perm: [ 2 1 4 3 ] Sign: 1
Perm: [ 2 1 3 4 ] Sign: -1
</pre>
=={{header|zkl}}==
{{trans|Python}}
{{trans|Haskell}}
<lang zkl>fcn permute(seq)
{
insertEverywhere := fcn(x,list){ //(x,(a,b))-->((x,a,b),(a,x,b),(a,b,x))
(0).pump(list.len()+1,List,'wrap(n){list[0,n].extend(x,list[n,*]) })};
insertEverywhereB := fcn(x,t){ //--> insertEverywhere().reverse()
[t.len()..-1,-1].pump(t.len()+1,List,'wrap(n){t[0,n].extend(x,t[n,*])})};
seq.reduce('wrap(items,x){
f := Utils.Helpers.cycle(insertEverywhereB,insertEverywhere);
items.pump(List,'wrap(item){f.next()(x,item)},
T.fp(Void.Write,Void.Write));
},T(T));
}</lang>
A cycle of two "build list" functions is used to insert x forward or reverse. reduce loops over the items and retains the enlarging list of permuations. pump loops over the existing set of permutations and inserts/builds the next set (into a list sink). (Void.Write,Void.Write,list) is a sentinel that says to write the contents of the list to the sink (ie sink.extend(list)). T.fp is a partial application of ROList.create (read only list) and the parameters VW,VW. It will be called (by pump) with a list of lists --> T.create(VM,VM,list) --> list
<lang zkl>p := permute(T(1,2,3));
p.println();
p := permute([1..4]);
p.len().println();
p.toString(*).println()</lang>
{{out}}
<pre>
L(L(1,2,3),L(1,3,2),L(3,1,2),L(3,2,1),L(2,3,1),L(2,1,3))
24
L(
L(1,2,3,4), L(1,2,4,3), L(1,4,2,3), L(4,1,2,3), L(4,1,3,2), L(1,4,3,2),
L(1,3,4,2), L(1,3,2,4), L(3,1,2,4), L(3,1,4,2), L(3,4,1,2), L(4,3,1,2),
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>
| |||