Permutations by swapping: Difference between revisions

=={{header|Nimrod}}==

<lang nimrod># iterative Boothroyd method

iterator permutations[T](ys: openarray[T]): tuple[perm: seq[T], sign: int] =

var

d = 1

c = newSeq[int](ys.len)

xs = newSeq[T](ys.len)

sign = 1

for i, y in ys: xs[i] = y

yield (xs, sign)

block outter:

while true:

while d > 1:

dec d

c[d] = 0

while c[d] >= d:

inc d

if d >= ys.len: break outter

let i = if (d and 1) == 1: c[d] else: 0

swap xs[i], xs[d]

sign *= -1

yield (xs, sign)

inc c[d]

for i in permutations([0,1,2]):

echo i

echo ""

for i in permutations([0,1,2,3]):

echo i</lang>

Output:

<pre>(perm: @[0, 1, 2], sign: 1)

(perm: @[1, 0, 2], sign: -1)

(perm: @[2, 0, 1], sign: 1)

(perm: @[0, 2, 1], sign: -1)

(perm: @[1, 2, 0], sign: 1)

(perm: @[2, 1, 0], sign: -1)

(perm: @[0, 1, 2, 3], sign: 1)

(perm: @[1, 0, 2, 3], sign: -1)

(perm: @[2, 0, 1, 3], sign: 1)

(perm: @[0, 2, 1, 3], sign: -1)

(perm: @[1, 2, 0, 3], sign: 1)

(perm: @[2, 1, 0, 3], sign: -1)

(perm: @[3, 1, 0, 2], sign: 1)

(perm: @[1, 3, 0, 2], sign: -1)

(perm: @[0, 3, 1, 2], sign: 1)

(perm: @[3, 0, 1, 2], sign: -1)

(perm: @[1, 0, 3, 2], sign: 1)

(perm: @[0, 1, 3, 2], sign: -1)

(perm: @[0, 2, 3, 1], sign: 1)

(perm: @[2, 0, 3, 1], sign: -1)

(perm: @[3, 0, 2, 1], sign: 1)

(perm: @[0, 3, 2, 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: @[1, 3, 2, 0], sign: 1)

(perm: @[3, 1, 2, 0], sign: -1)

(perm: @[2, 1, 3, 0], sign: 1)

(perm: @[1, 2, 3, 0], sign: -1)</pre>