Talk:Steinhaus–Johnson–Trotter algorithm

Origins

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

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)

Indeed. The algorithm is known as the "Johnson-Trotter algorithm". Someone on Wikipedia changed it to "Steinhaus-..." I tried to change it back but a David Eppstein almost immediately reversed it. Onlinetexts (talk) 21:50, 14 May 2015 (UTC)

It is false that all references omit the Steinhaus. The proper response to something that has two names is to list both of them, and to title the article with the more common of the two names. It may be that Johnson-Trotter is more common than Steinhaus–Johnson–Trotter (I'm not sure, and going by search engine hit counts doesn't work well because searches for the shorter of these two names will also count everything that uses the longer of the two). But your approach of removing any mention of the alternative name from the article is categorically incorrect. —David Eppstein (talk) 00:33, 15 May 2015 (UTC)

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

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

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)

It looks like references to Steinhaus is Problem #98 in book... Did somebody read this book? In this puzzle did not mentioned any permutations, swapping positions, no overtakes... It looks like Steinhaus is far-fetched or puzzle had wrong interpretation. Jumpow (talk) 14:18, 5 October 2022 (UTC)

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)

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)

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)

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)

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)

I agree with the implication by Aditsu that the word 'concentrated' has no meaning here. What determines the direction to set is simply whether an element lies between the chosen element and the start of the permutation when the direction should be set to positive or between the chosen element and the end of the permutation when it should be set to negative. (As the article specifies, in both cases, changes should be made only if the element is greater than the chosen one.) I have verified that this interpretation is correct by coding the algorithm and have changed the wording of the article.IanHH (talk) 18:07, 12 October 2013 (UTC)

Knuth reference

Since volume 4A is out, which covers this, should the reference be changed to volume 4A? Bubba73 ^{You talkin' to me?} 02:44, 2 July 2013 (UTC)

Please go ahead and do so. —David Eppstein (talk) 03:00, 2 July 2013 (UTC)

Edit request

After being informed by MrOllie about a potential conflict of interest, I am now formally requesting to make the following additions to the page. The Combinatorial Object Server is a collection of open source software tools I frequently use to create this kind of illustrations, and to which I am a frequent contributor.

Add the following diagram to the page:

---

Wheel diagram of all permutations of length $n=4$ generated by the Steinhaus-Johnson-Trotter algorithm, where each permutation is color-coded (1=blue, 2=green, 3=yellow, 4=red).

---

Torsten Mütze (talk) 16:24, 29 May 2019 (UTC)

References

Pinging @David Eppstein: for their input on this edit (and my apologies if you are already watchlisted for this page). Regards,  Spintendo  22:52, 29 May 2019 (UTC)

The diagram is still on the article (and I agree that it's a good one, clearer than the other two earlier diagrams). What MrOllie did was to remove the footnote giving the credit for the diagram. That sort of thing usually lives on the image page, and is not copied over into captions where the image is used. So if you want to edit the description of Commons:File:Wheel diagram of Steinhaus-Johnson-Trotter algorithm for n=4.svg to include this credit, that would make more sense to me than putting it here. —David Eppstein (talk) 22:59, 29 May 2019 (UTC)

Ok. Will do as suggested. Torsten Mütze (talk) 14:30, 30 May 2019 (UTC)

Cyclicality

Someone else must have observed this difference between two permutation schemes, but I didn't see it mentioned in either article.

The 4-place example here on [Steinhaus–Johnson–Trotter algorithm] starts with 1-2-3-4 and ends with 2-1-3-4. One more swap changes the last state to the first state. That makes a cyclical sequence or cycle of 24 states with 24 swaps, which could be written on a cylindrical strip.

The 4-place example for Heap's algorithm starts with A-B-C-D and ends with D-C-B-A. The 24-state sequence with 23 swaps is not a cycle. (Therefore less impressive?) But its last state is the reflection of its first state. Discarding the last state makes a 23-state sequence with 23 swaps, which could be written on (or punched through) a Möbius strip. Or, two copies of the 23-state strip (one reflected) could be concatenated, making a 46-state cycle that returns from the reversed state to the original state via a different route. -A876 (talk) 23:20, 6 September 2022 (UTC)