Talk:Steinhaus–Johnson–Trotter algorithm

Computing Stub‑class

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.
	This article has been automatically rated by a bot or other tool as Stub-class because it uses a stub template. Please ensure the assessment is correct before removing the `\|auto=` parameter.

Does anyone have a reference for the origins of this algorithm? Resistor 18:35, 28 January 2006 (UTC)[reply]

Why does Wikipedia list this algorithm as "Steinhaus-", when all the references to the article use the shorter name and either omit Steinhaus altogether or list the longer form as the variant? 87.194.117.80 (talk) 23:04, 20 January 2010 (UTC)[reply]

Is this the method of plain changes? — Preceding unsigned comment added by 82.139.87.39 (talk) 06:14, 2 October 2011 (UTC)[reply]

Yes, as the article now says in the new history section. —David Eppstein (talk) 06:29, 2 October 2011 (UTC)[reply]

The image associated with the page goes awry at permutation number 14 stating (3,4,3,2). Whoever made the image did a good job but ideally this mistake would be fixed. Before anyone says sofixit...no time. Sorry. 11:35, 13th February 2012 (GMT)

Ok, fixed. Thanks for letting me know. —David Eppstein (talk) 16:11, 13 February 2012 (UTC)[reply]

Gray code for the factorial number system

The algorithm defines a Hamiltonian path in a Cayley graph of the symmetric group. The inverse permutations define a path in the permutohedron:
Cayley graph	Permutohedron
Permutations form a Gray code. The swapped elements are always adjacent.	Permutations, inversion vectors and inversion sets form a Gray code.
Permutations with green or orange background are odd. The smaller numbers below the permutations are the inversion vectors. Red marks indicate swapped elements. Compare list in natural order.

At the moment the article contains the following sentence:

Consecutive permutations in the sequence generated by the Steinhaus–Johnson–Trotter algorithm have numbers of inversions that differ by one, forming a Gray code for the factorial number system.

Something is a Gray code because the digit sums of consecutive tuples differ by one?! I don't believe that Dijkstra (1976) and Knuth (2004) claimed that.

In the tables I have included it can be seen that only for the inverse permutations (the path in the permutohedron, right table) the inversion vectors form a Gray code, i.e. always one digit is changing by one.

In the sequence generated by the algorithm (the path in the Cayley graph, left table) we have e.g. permutation 12 followed by permutation 2, i.e. inversion vector (0,0,0,2) followed by (0,0,1,0). I don't believe that fits any definition of Gray code.

By the way: In the sequence of inverse permutations (right table) the swapped positions correspond to the changing element in the inversion sets (better seen in the magnification). Maybe this could be mentioned in the article. Lipedia (talk) 16:19, 1 June 2012 (UTC)[reply]

Unclear description for Even's speedup

In one phase of Even's algorithm, it says "all elements greater than the chosen element have their directions set to positive or negative, according to whether they are concentrated at the start or the end of the permutation respectively". I don't understand what this is supposed to mean, especially the word "concentrated". If those elements should be at the start or end of the permutation (i.e. first or last position) then what happens if an element greater than the chosen element is somewhere in the middle? If those elements are rather assessed by the distance to the start or end of the permutation (i.e. whether they are closer to the start than to the end) then what if an element is exactly in the middle? Or if the statement means something else, then what does it mean? aditsu (talk) 20:38, 16 April 2013 (UTC)[reply]

I believe that all the elements greater than the chosen element can only be found in two contiguous subsequences, one at the start of the sequence and one at the end of the sequence. It's not true that an individual element is "at" the start or end, because these subsequences might have more than one element in them. But it's also not possible for an element to be "somewhere in the middle" because the algorithm never leaves elements there while moving smaller elements. —David Eppstein (talk) 20:48, 16 April 2013 (UTC)[reply]

That still doesn't really clarify how to identify the direction to set. If I'm not mistaken, it could be done by the position relative to the smallest element (or possibly to the chosen element too). But if the other description I found (below) is correct, then it makes everything easier. aditsu (talk) 21:11, 16 April 2013 (UTC)[reply]

Hmm, in fact I found a couple of descriptions of the Johnson–Trotter algorithm elsewhere on the net, with no mention of Shimon Even, but very similar to "Even's speedup", but with one ESSENTIAL difference: they use non-zero directions. Instead of that, they talk about mobile elements - which have a smaller element adjacent in their current direction. The step that I'm confused about becomes simply "change the direction of all elements greater than the chosen element", which is perfectly clear. From what I understand, it's the same algorithm, but put in a much simpler way. aditsu (talk) 21:00, 16 April 2013 (UTC)[reply]