Permutations by swapping: Difference between revisions
J draft
(More clear?) |
(J draft) |
||
Line 12:
;Cf.:
* [[Matrix arithmetic]]
=={{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>
=={{header|Python}}==
| |||