Permutations by swapping: Difference between revisions

=={{header|J}}==

J's built in mechanism for [http://www.jsoftware.com/help/dictionary/dacapdot.htm generating permutations] (which is designed around the idea of selecting a permutation uniquely by an integer) 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>bfjt0=: _1 - i.

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

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

bfjtn=: (((] <@, ] + *@{~) | i. next) C. ] * _1 ^ next < |)^:(*@next)</lang>

Here, bfjt0 N gives the initial permutation of order N, and bfjtn^:M bfjt0M gives the Mth Steinhaus–Johnson–Trotter permutation of order N.

To convert from the Steinhaus–Johnson–Trotter representation of a permutation to J's representation, use <:@|, or to find J's permutation index of a Steinhaus–Johnson–Trotter representation of a permutation, use A.<:@|

Example use:

<lang J> bfjtn^:(i.!3) bfjt0 3

_1 _2 _3

_1 _3 _2

_3 _1 _2

3 _2 _1

_2 3 _1

_2 _1 3

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

0 1 2

0 2 1

2 0 1

2 1 0

1 2 0

1 0 2

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

0 1 4 5 3 2</lang>