Permutations by swapping: Difference between revisions

* [[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]

* [http://www.gutenberg.org/files/18567/18567-h/18567-h.htm#ch7] Tintinnalogia

 

*   [[Gray code]]

<br><br>

 

=={{header|AutoHotkey}}==

ch := SubStr(str, 1, 1) ; get left-most charachter of str

for i, line in StrSplit(list, "`n") ; for each line in list

return list ; done if str is empty

return Permutations_By_Swapping(str, list) ; else recurse

result .= line "`tSign: " (mod(A_Index,2)? 1 : -1) "`n"

MsgBox, 262144, , % result

Outputs:<pre>1234 Sign: 1

1243 Sign: -1

2143 Sign: 1

2134 Sign: -1</pre>

 

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

{{works with|BBC BASIC for Windows}}

PRINT

PROCperms(4)

ENDIF

UNTIL k% = 0

{{out}}

<pre>

=={{header|C}}==

Implementation of Heap's Algorithm, array length has to be passed as a parameter for non character arrays, as sizeof() will not give correct results when malloc is used. Prints usage on incorrect invocation.

#include<stdlib.h>

#include<string.h>

return 0;

}

Output:

<pre>

=={{header|C++}}==

Direct implementation of Johnson-Trotter algorithm from the reference link.

#include <iostream>

#include <vector>

} while (!state.IsComplete());

}

{{out}}

<pre>

=={{header|Clojure}}==

===Recursive version===

(defn permutation-swaps

"List of swap indexes to generate all permutations of n elements"

(doseq [n [2 3 4]]

(dorun (map println (permutations n))))

 

{{out}}

===Modeled After Python version===

{{trans|Python}}

(ns test-p.core)

 

(println (format "Permutations and sign of %d items " n))

(doseq [q (spermutations n)] (println (format "Perm: %s Sign: %2d" (first q) (second q))))))

 

{{out}}

 

=={{header|Common Lisp}}==

(number nil :type integer)

(direction nil :type (member :left :right)))

 

(permutations 3)

{{out}}

<pre>#(<1 <2 <3) sign: +1

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:

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

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

</pre>

 

=={{header|EchoLisp}}==

The function '''(in-permutations n)''' returns a stream which delivers permutations according to the Steinhaus–Johnson–Trotter algorithm.

(lib 'list)

 

perm: (1 0 3 2) count: 22 sign: 1

perm: (1 0 2 3) count: 23 sign: -1

 

=={{header|Elixir}}==

{{trans|Ruby}}

def by_swap(n) do

p = Enum.to_list(0..-n) |> List.to_tuple

Permutation.by_swap(n)

IO.puts ""

 

{{out}}

=={{header|F_Sharp|F#}}==

See [http://www.rosettacode.org/wiki/Zebra_puzzle#F.23] for an example using this module

(*Implement Johnson-Trotter algorithm

Nigel Galloway January 24th 2017*)

yield! _Ni gel 0 1

}

A little code for the purpose of this task demonstrating the algorithm

for n in Ring.PlainChanges [|1;2;3;4|] do printfn "%A" n

{{out}}

<pre>

{{works with|gforth|0.7.9_20170308}}

{{trans|BBC BASIC}}

S" fsl/dynmem.seq" REQUIRED

 

 

3 ' .perm perms CR

 

=={{header|FreeBASIC}}==

{{trans|BBC BASIC}}

' compile with: fbc -s console

 

Sleep

End

{{out}}

<pre>output is edited to show results side by side

 

=={{header|Go}}==

 

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

}

}

 

import (

fmt.Println(p, sign)

}

{{out}}

<pre>

 

=={{header|Haskell}}==

sPermutations = flip zip (cycle [-1, 1]) . foldr aux [[]]

where

mapM_ print $ sPermutations [1 .. 3]

putStrLn "\n4 items:"

{{Out}}

<pre>3 items:

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

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

 

=={{header|Java}}==

Heap's Algorithm, recursive and looping implementations

 

 

import java.util.Arrays;

}

}

{{out}}

<pre>

input array. This array may contain any JSON entities, which are regarded as distinct.

 

# versions of jq with TCO (tail call optimization) there is no

# overhead associated with the recursion.

| .[1] = reduce range(0; $n) as $i ([]; . + [$in[$p[$i] - 1]]) ;

 

'''Examples:'''

{{out}}

[1,["a","b","c"]]

[-1,["a","c","b"]]

[-1,["b","a","c"]]

 

 

=={{header|Julia}}==

Nonrecursive (interative):

function johnsontrottermove!(ints, isleft)

len = length(ints)

end

johnsontrotter(1,4)

Recursive (note this uses memory of roughtly (n+1)! bytes, where n is the number of elements, in order to store the accumulated permutations in a list, and so the above, iterative solution is to be preferred for numbers of elements over 9 or so):

function johnsontrotter(low, high)

function permutelevel(vec)

println("""$sequence, $(i & 1 == 1 ? "+1" : "-1")""")

end

 

=={{header|Kotlin}}==

This is based on the recursive Java code found at http://introcs.cs.princeton.edu/java/23recursion/JohnsonTrotter.java.html

 

fun johnsonTrotter(n: Int): Pair<List<IntArray>, List<Int>> {

val (perms2, signs2) = johnsonTrotter(4)

printPermsAndSigns(perms2, signs2)

 

{{out}}

=={{header|Lua}}==

{{trans|C++}}

function JT(dim)

local n={ values={}, positions={}, directions={}, sign=1 }

repeat

print(unpack(perm.values))

{{out}}

<pre>1 2 3 4

===Coroutine Implementation===

This is adapted from the [https://www.lua.org/pil/9.3.html Lua Book ].

local function perm(n)

local r = {}

end)

end

 

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

 

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

This is based on the Raku recursive version, but without recursion.

 

use strict;

use warnings;

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

}

{{out}}

The output is the same as the first perl solution.

Only once finished did I properly grasp that odd/even permutation idea, and that it is very nearly the same algorithm.<br>

Only difference is my version directly calculates where to insert p, without using the parity (which I added in last).

{{out}}

<pre>

==1==

==2==

==3==

==4==

</pre>

 

=={{header|PicoLisp}}==

(N 4

L

(printsp (car I)) )

(prinl) ) )

 

=={{header|PowerShell}}==

}

}

}

}

}

}

}

<b>Output:</b>

 

 

=={{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}}

=== Recursive ===

{{works with|rakudo|2015-09-25}}

sub order($sg, @xs) { $sg > 0 ?? @xs !! @xs.reverse }

}

 

{{out}}

 

=={{header|REXX}}==

parse arg things bunch . /*obtain optional arguments from the CL*/

if things=='' | things=="," then things=4 /*Not specified? Then use the default.*/

end /*k*/

end /*$*/

{{out|output|text=&nbsp; when using the default input:}}

<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|Scala}}==

 

private def perm(n: Int): Unit = {

perm(4)

 

{{Out}}See it in running in your browser by [https://scastie.scala-lang.org/DdM4xnUnQ2aNGP481zwcrw Scastie (JVM)].

 

=={{header|Sidef}}==

{{trans|Perl}}

var perms = [[+1]]

for x in (1..n) {

s > 0 && (s = '+1')

say "#{p} => #{s}"

 

{{out}}

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

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

</pre>

 

=={{header|Tcl}}==

proc swap {listvar i1 i2} {

upvar 1 $listvar l

}

}

Demonstrating:

puts "$s\t$p"

{{out}}

<pre>

=={{header|Wren}}==

{{trans|Kotlin}}

var p = List.filled(n, 0) // permutation

var q = List.filled(n, 0) // inverse permutation

perms = res[0]

signs = res[1]

 

{{out}}

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