Permutations by swapping: Difference between revisions

{{task}}

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''.

 

 

Note: The Steinhaus–Johnson–Trotter algorithm generates successive permutations where ''adjacent'' items are swapped, but from [[wp:Parity_of_a_permutation#Example|this]] discussion adjacency is not a requirement.

 

;References:

* [[wp:Steinhaus–Johnson–Trotter algorithm|Steinhaus–Johnson–Trotter algorithm]]

* [http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml Johnson-Trotter Algorithm Listing All Permutations]

 

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

PRINT

PROCperms(4)

ENDIF

UNTIL k% = 0

{{out}}

<pre>

</pre>

 

 

 

int i;

 

}

 

 

{

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

{{out}}

<pre>

</pre>

 

 

 

 

 

=={{header|D}}==

This isn't a Range yet.

{{trans|Python}}

 

struct Spermutations(bool doCopy=true) {

}

}

Compile with version=permutations_by_swapping1 to see the demo output.

{{out}}

===Recursive Version===

{{trans|Python}}

 

auto sPermutations(in uint n) pure nothrow @safe {

writeln;

}

{{out}}

<pre>Permutations and sign of 2 items:

[3, 2, 0, 1] Sign: -1

</pre>

 

=={{header|Go}}==

 

// Iter takes a slice p and returns an iterator function. The iterator

}

}

 

import (

fmt.Println(p, sign)

}

{{out}}

<pre>

 

=={{header|Haskell}}==

 

main :: IO ()

main = do

putStrLn "3 items:"

4 items:

 

=={{header|Icon}} and {{header|Unicon}}==

{{trans|Python}}

 

every write("Permutations of length ",n := !A) do

every p := permute(n) do write("\t",showList(p[1])," -> ",right(p[2],2))

every (s := "[") ||:= image(!A)||", "

return s[1:-2]||"]"

 

Sample run:

 

=={{header|J}}==

 

Meanwhile, here's an inductive approach, using negative integers to look left and positive integers to look right:

 

lookingat=: 0 >. <:@# <. i.@# + *

next=: | >./@:* | > | {~ lookingat

 

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".)

Example use:

 

_1 _2 _3

_1 _3 _2

1 0 2

A. <:@| bfsjtn^:(i.!3) bfjt0 3

 

Here's an example of the Steinhaus–Johnson–Trotter representation of 3 element permutation, with sign (sign is the first column):

 

1 _1 _2 _3

_1 _1 _3 _2

_1 3 _2 _1

1 _2 3 _1

 

Alternatively, J defines [http://www.jsoftware.com/help/dictionary/dccapdot.htm C.!.2] as the parity of a permutation:

 

1 0 1 2

_1 0 2 1

_1 2 1 0

1 1 2 0

 

===Recursive Implementation===

This is based on the python recursive implementation:

 

if. 2>y do. i.2#y

else. ((!y)$(,~|.)-.=i.y)#inv!.(y-1)"1 y#rsjt y-1

end.

 

Example use (here, prefixing each row with its parity):

 

1 0 1 2

_1 0 2 1

_1 2 1 0

1 1 2 0

 

=== Recursive ===

perms[n_] :=

Flatten[If[#2 == 1, Reverse, # &]@

Table[{Insert[#1, n, i], (-1)^(n + i) #2}, {i, n}] & @@@

Example:

{{out}}

<pre>Perm: {1,2,3,4} Sign: 1

 

=={{header|Nim}}==

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

var

inc c[d]

 

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

echo i

 

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

{{out}}

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

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

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

 

=={{header|Perl}}==

 

===S-J-T Based===

use warnings;

 

# while demonstrating some common perl idioms.

 

my $callback = shift;

my @perm = map [$_, -1], @_;

print $sign < 0 ? " => -1\n" : " => +1\n";

} 1 .. $n;

{{out}}<pre>

[1, 2, 3, 4] => +1

 

=== Alternative Iterative version ===

 

use strict;

use warnings;

print "[", join(", ", @$_), "] => $s\n";

}

{{out}}

The output is the same as the first perl solution.

 

{{out}}

<pre>

</pre>

 

=={{header|PicoLisp}}==

(N 4

L

(printsp (car I)) )

(prinl) ) )

 

=={{header|Python}}==

When saved in a file called spermutations.py it is used in the Python example to the [[Matrix arithmetic#Python|Matrix arithmetic]] task and so any changes here should also be reflected and checked in that task example too.

 

DEBUG = False # like the built-in __debug__

# Test

p = set(permutations(range(n)))

{{out}}

<pre>Permutations and sign of 3 items

===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:

def s_perm(seq):

if not seq:

 

return [(tuple(item), -1 if i % 2 else 1)

 

{{out|Sample output}}

===Python: Iterative version of the recursive===

Replacing the recursion in the example above produces this iterative version function:

items = [[]]

for j in seq:

 

return [(tuple(item), -1 if i % 2 else 1)

 

{{out|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.

 

=={{header|Racket}}==

#lang racket

 

 

(for ([n (in-range 3 5)]) (show-permutations (range n)))

 

{{out}}

</pre>

 

 

 

 

 

<pre>

 

 

 

=={{header|Ruby}}==

{{trans|BBC BASIC}}

p = Array.new(n+1){|i| -i}

s = 1

perms(i){|perm, sign| puts "Perm: #{perm} Sign: #{sign}"}

puts

{{out}}

<pre>

Perm: [2, 1, 4, 3] Sign: 1

Perm: [2, 1, 3, 4] Sign: -1

</pre>

 

=={{header|Tcl}}==

proc swap {listvar i1 i2} {

upvar 1 $listvar l

}

}

Demonstrating:

puts "$s\t$p"

{{out}}

<pre>

1 1 0 3 2

-1 1 0 2 3

</pre>

 

=={{header|XPL0}}==

Translation of BBC BASIC example, which uses the Johnson-Trotter algorithm.

 

proc PERMS(N);

CrLf(0);

PERMS(4);

 

{{out}}

{{trans|Python}}

{{trans|Haskell}}

{

insertEverywhere := fcn(x,list){ //(x,(a,b))-->((x,a,b),(a,x,b),(a,b,x))

T.fp(Void.Write,Void.Write));

},T(T));

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

p.println();

 

p := permute([1..4]);

p.len().println();

{{out}}

<pre>

</pre>

An iterative, lazy version, which is handy as the number of permutations is n!. Uses "Even's Speedup" as described in the Wikipedia article:

N:=seq.len(); NM1:=N-1;

ds:=(0).pump(N,List,T(Void,-1)).copy(); ds[0]=0; // direction to move e: -1,0,1

}

 

{{out}}

<pre>