Permutations by swapping
Generate permutations of n items in which successive permutations differ from each other by the swapping of any two items. Also generate the sign of the permutation which is +1 when the permutation is generated from an even number of swaps from the initial state, and -1 for odd. Show the permutations and signs of three items, in order of generation here.
Such data are of use in generating the determinant of a square matrix and any functions created should bear this in mind.
Note: The Steinhaus–Johnson–Trotter algorithm generates successive permutations where adjacent items are swapped, but from this discussion adjacency is not a requirement.
- References
- Cf.
D
Iterative Version
This isn't a Range.
<lang d>import std.algorithm, std.array, std.typecons, std.range;
struct Spermutations {
const int n; alias Tuple!(int[], int) TResult;
int opApply(int delegate(ref TResult) dg) {
int result;
TResult aux;
int sign = 1;
alias Tuple!(int, int) Pair;
auto p = iota(n).map!(i => Pair(i, i ? -1 : 0))().array();
aux = tuple(p.map!(pp => pp[0])().array(), sign);
result = dg(aux); if (result) goto END;
while (p.canFind!(pp => pp[1])()) {
// Failed using std.algorithm here, too much complex
auto largest = Pair(-100, -100);
int i1 = -1;
foreach (i, pp; p)
if (pp[1]) {
if (pp[0] > largest[0]) {
i1 = i;
largest = pp;
}
}
int n1 = largest[0], d1 = largest[1];
sign *= -1;
int i2;
if (d1 == -1) {
i2 = i1 - 1;
swap(p[i1], p[i2]);
if (i2 == 0 || p[i2 - 1][0] > n1)
p[i2][1] = 0;
} else if (d1 == 1) {
i2 = i1 + 1;
swap(p[i1], p[i2]);
if (i2 == n - 1 || p[i2 + 1][0] > n1)
p[i2][1] = 0;
}
aux = tuple(p.map!(pp => pp[0])().array(), sign);
result = dg(aux); if (result) goto END;
foreach (i3, ref pp; p) {
auto n3 = pp[0], d3 = pp[1];
if (n3 > n1)
pp[1] = (i3 < i2) ? 1 : -1;
}
}
END: return result; }
}
void main() {
import std.stdio;
foreach (n; [3, 4]) {
writefln("\nPermutations and sign of %d items", n);
foreach (tp; Spermutations(n))
writefln("Perm: %s Sign: %2d", tp.tupleof);
}
}</lang>
- Output:
Permutations and sign of 3 items Perm: [0, 1, 2] Sign: 1 Perm: [0, 2, 1] Sign: -1 Perm: [2, 0, 1] Sign: 1 Perm: [2, 1, 0] Sign: -1 Perm: [1, 2, 0] Sign: 1 Perm: [1, 0, 2] Sign: -1 Permutations and sign of 4 items Perm: [0, 1, 2, 3] Sign: 1 Perm: [0, 1, 3, 2] Sign: -1 Perm: [0, 3, 1, 2] Sign: 1 Perm: [3, 0, 1, 2] Sign: -1 Perm: [3, 0, 2, 1] Sign: 1 Perm: [0, 3, 2, 1] Sign: -1 Perm: [0, 2, 3, 1] Sign: 1 Perm: [0, 2, 1, 3] Sign: -1 Perm: [2, 0, 1, 3] Sign: 1 Perm: [2, 0, 3, 1] Sign: -1 Perm: [2, 3, 0, 1] Sign: 1 Perm: [3, 2, 0, 1] Sign: -1 Perm: [3, 2, 1, 0] Sign: 1 Perm: [2, 3, 1, 0] Sign: -1 Perm: [2, 1, 3, 0] Sign: 1 Perm: [2, 1, 0, 3] Sign: -1 Perm: [1, 2, 0, 3] Sign: 1 Perm: [1, 2, 3, 0] Sign: -1 Perm: [1, 3, 2, 0] Sign: 1 Perm: [3, 1, 2, 0] Sign: -1 Perm: [3, 1, 0, 2] Sign: 1 Perm: [1, 3, 0, 2] Sign: -1 Perm: [1, 0, 3, 2] Sign: 1 Perm: [1, 0, 2, 3] Sign: -1
Recursive Version
Same output.
<lang d>import std.algorithm, std.array, std.typecons, std.range;
Tuple!(int[], int)[] sPermutations(in int n) /*pure nothrow*/ {
static int[][] sPermu(in int items) /*pure nothrow*/ {
if (items <= 0)
return [[]];
typeof(return) r;
foreach (i, item; sPermu(items - 1)) {
if (i % 2)
r ~= iota(cast(int)item.length, -1, -1)
.map!(i => item[0..i] ~ (items-1) ~ item[i..$])()
.array();
else
r ~= iota(item.length + 1)
.map!(i => item[0..i] ~ (items-1) ~ item[i..$])()
.array();
}
return r;
}
auto r = sPermu(n);
return iota(r.length)
.map!(i => tuple(r[i], i % 2 ? -1 : 1))()
.array();
}
void main() {
import std.stdio;
foreach (n; [3, 4]) {
writefln("\nPermutations and sign of %d items", n);
foreach (tp; sPermutations(n))
writefln("Perm: %s Sign: %2d", tp.tupleof);
}
}</lang>
J
J has a built in mechanism for representing permutations (which is designed around the idea of selecting a permutation uniquely by an integer) but it does not seem seem to have an obvious mapping to Steinhaus–Johnson–Trotter. Perhaps someone with a sufficiently deep view of the subject of permutations can find a direct mapping?
Meanwhile, here's an inductive approach, using negative integers to look left and positive integers to look right:
<lang J>bfsjt0=: _1 - i. lookingat=: 0 >. <:@# <. i.@# + * next=: | >./@:* | > | {~ lookingat bfsjtn=: (((] <@, ] + *@{~) | i. next) C. ] * _1 ^ next < |)^:(*@next)</lang>
Here, bfsjt0 N gives the initial permutation of order N, and bfsjtn^:M bfsjt0 N gives the Mth Steinhaus–Johnson–Trotter permutation of order N. (bf stands for "brute force".)
To convert from the Steinhaus–Johnson–Trotter representation of a permutation to J's representation, use <:@|, or to find J's anagram index of a Steinhaus–Johnson–Trotter representation of a permutation, use A.@:<:@:|
Example use:
<lang J> bfsjtn^:(i.!3) bfjt0 3 _1 _2 _3 _1 _3 _2 _3 _1 _2
3 _2 _1
_2 3 _1 _2 _1 3
<:@| bfsjtn^:(i.!3) bfjt0 3
0 1 2 0 2 1 2 0 1 2 1 0 1 2 0 1 0 2
A. <:@| bfsjtn^:(i.!3) bfjt0 3
0 1 4 5 3 2</lang>
Here's an example of the Steinhaus–Johnson–Trotter representation of 3 element permutation, with sign (sign is the first column):
<lang J> (_1^2|i.!3),. bfsjtn^:(i.!3) bfjt0 3
1 _1 _2 _3
_1 _1 _3 _2
1 _3 _1 _2
_1 3 _2 _1
1 _2 3 _1
_1 _2 _1 3</lang>
Alternatively, J defines C.!.2 as the parity of a permutation:
<lang J> (,.~C.!.2)<:| bfsjtn^:(i.!3) bfjt0 3
1 0 1 2
_1 0 2 1
1 2 0 1
_1 2 1 0
1 1 2 0
_1 1 0 2</lang>
Python
Python: iterative
When saved in a file called spermutations.py it is used in the Python example to the Matrix arithmetic task.
<lang python>from operator import itemgetter
DEBUG = False # like the built-in __debug__
def spermutations(n):
"""permutations by swapping. Yields: perm, sign"""
sign = 1
p = [[i, 0 if i == 0 else -1] # [num, direction]
for i in range(n)]
if DEBUG: print ' #', p yield tuple(pp[0] for pp in p), sign
while any(pp[1] for pp in p): # moving
i1, (n1, d1) = max(((i, pp) for i, pp in enumerate(p) if pp[1]),
key=itemgetter(1))
sign *= -1
if d1 == -1:
# Swap down
i2 = i1 - 1
p[i1], p[i2] = p[i2], p[i1]
# If this causes the chosen element to reach the First or last
# position within the permutation, or if the next element in the
# same direction is larger than the chosen element:
if i2 == 0 or p[i2 - 1][0] > n1:
# The direction of the chosen element is set to zero
p[i2][1] = 0
elif d1 == 1:
# Swap up
i2 = i1 + 1
p[i1], p[i2] = p[i2], p[i1]
# If this causes the chosen element to reach the first or Last
# position within the permutation, or if the next element in the
# same direction is larger than the chosen element:
if i2 == n - 1 or p[i2 + 1][0] > n1:
# The direction of the chosen element is set to zero
p[i2][1] = 0
if DEBUG: print ' #', p
yield tuple(pp[0] for pp in p), sign
for i3, pp in enumerate(p):
n3, d3 = pp
if n3 > n1:
pp[1] = 1 if i3 < i2 else -1
if DEBUG: print ' # Set Moving'
if __name__ == '__main__':
from itertools import permutations
for n in (3, 4):
print '\nPermutations and sign of %i items' % n
sp = set()
for i in spermutations(n):
sp.add(i[0])
print('Perm: %r Sign: %2i' % i)
#if DEBUG: raw_input('?')
# Test
p = set(permutations(range(n)))
assert sp == p, 'Two methods of generating permutations do not agree'</lang>
- Output:
Permutations and sign of 3 items Perm: (0, 1, 2) Sign: 1 Perm: (0, 2, 1) Sign: -1 Perm: (2, 0, 1) Sign: 1 Perm: (2, 1, 0) Sign: -1 Perm: (1, 2, 0) Sign: 1 Perm: (1, 0, 2) Sign: -1 Permutations and sign of 4 items Perm: (0, 1, 2, 3) Sign: 1 Perm: (0, 1, 3, 2) Sign: -1 Perm: (0, 3, 1, 2) Sign: 1 Perm: (3, 0, 1, 2) Sign: -1 Perm: (3, 0, 2, 1) Sign: 1 Perm: (0, 3, 2, 1) Sign: -1 Perm: (0, 2, 3, 1) Sign: 1 Perm: (0, 2, 1, 3) Sign: -1 Perm: (2, 0, 1, 3) Sign: 1 Perm: (2, 0, 3, 1) Sign: -1 Perm: (2, 3, 0, 1) Sign: 1 Perm: (3, 2, 0, 1) Sign: -1 Perm: (3, 2, 1, 0) Sign: 1 Perm: (2, 3, 1, 0) Sign: -1 Perm: (2, 1, 3, 0) Sign: 1 Perm: (2, 1, 0, 3) Sign: -1 Perm: (1, 2, 0, 3) Sign: 1 Perm: (1, 2, 3, 0) Sign: -1 Perm: (1, 3, 2, 0) Sign: 1 Perm: (3, 1, 2, 0) Sign: -1 Perm: (3, 1, 0, 2) Sign: 1 Perm: (1, 3, 0, 2) Sign: -1 Perm: (1, 0, 3, 2) Sign: 1 Perm: (1, 0, 2, 3) Sign: -1
Python: recursive
After spotting the pattern of highest number being inserted into each perm of lower numbers from right to left, then left to right, I developed this recursive function: <lang python>def s_permutations(n):
def s_perm(items):
if items <= 0:
return [[]]
else:
new_items = []
for i, item in enumerate(s_perm(items - 1)):
if i % 2:
# step down
new_items += [item[:i] + [items - 1] + item[i:] \
for i in range(len(item), -1, -1)]
else:
# step up
new_items += [item[:i] + [items - 1] + item[i:] \
for i in range(len(item) + 1)]
return new_items
return [(tuple(item), -1 if i % 2 else 1)
for i, item in enumerate(s_perm(n))]</lang>
- Sample output
The output is the same as before except it is a list of all results rather than yielding each result from a generator function.
Python: simpler
Unrolling the recursion in the example above produces this simpler iterative function: <lang python>def s_permutations(n):
items = [[]]
for j in range(n):
new_items = []
for i, item in enumerate(items):
if i % 2:
# step down
new_items += [item[:i] + [j] + item[i:] \
for i in range(len(item), -1, -1)]
else:
# step up
new_items += [item[:i] + [j] + item[i:] \
for i in range(len(item) + 1)]
items = new_items
return [(tuple(item), -1 if i % 2 else 1)
for i, item in enumerate(items)]</lang>
- Sample output
The output is the same as before and is a list of all results rather than yielding each result from a generator function.