Permutations by swapping: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: elided extraneous text.) |
(Add Nimrod) |
||
Line 744: | Line 744: | ||
Perm: {2,1,4,3} Sign: 1 |
Perm: {2,1,4,3} Sign: 1 |
||
Perm: {2,1,3,4} Sign: -1</pre> |
Perm: {2,1,3,4} Sign: -1</pre> |
||
=={{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> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |