Permutations by swapping: Difference between revisions
Added XPL0 recursive version
(Added XPL0) |
(Added XPL0 recursive version) |
||
Line 685:
Perm: [ 2 1 4 3 ] Sign: 1
Perm: [ 2 1 3 4 ] Sign: -1
</pre>
===Recursive Version===
<lang XPL0>include c:\cxpl\codes;
int Rev;
proc GenPerms(A0, N, M); \Generate permutations of N items
char A0; int N, M;
char A1, Sign;
int I, J, K, L;
[N:= N+1; \add item and call it "N"
A1:= Reserve(N);
for K:= 0 to N-1 do
[J:= 0;
L:= K; \assume ascending order
if N=M & Rev then L:= N-1-K; \descending order
for I:= 0 to N-1 do \insert new member
if I#L then [A1(I):= A0(J); J:= J+1]
else A1(I):= N;
if N#M then
GenPerms(A1, N, M) \recurse
else [for I:= 0 to N-1 do IntOut(0, A1(I));
Sign:= " +1^M^J";
Text(0, Sign); \display result at maximum depth (M)
Sign(1):= if Sign(1)=^+ then ^- else ^+;
];
];
if N=M then Rev:= not Rev; \last item zigzags
];
char A;
[A:= Reserve(1);
A(0):= 1;
Rev:= false;
GenPerms(A, 1, 3);
CrLf(0);
Rev:= false;
GenPerms(A, 1, 4);
]</lang>
Output:
<pre>
321 +1
231 -1
213 +1
123 -1
132 +1
312 -1
4321 +1
3421 -1
3241 +1
3214 -1
2314 +1
2341 -1
2431 +1
4231 -1
4213 +1
2413 -1
2143 +1
2134 -1
3124 +1
3142 -1
3412 +1
4312 -1
4132 +1
1432 -1
1342 +1
1324 -1
1234 +1
1243 -1
1423 +1
4123 -1
</pre>
| |||