This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
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)
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)
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)
The algorithm defines a Hamiltonian path in a Cayley graph of the symmetric group. The inverse permutations define a path in the permutohedron: | |
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:
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)
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 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)
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)
This edit request by an editor with a conflict of interest has now been answered. |
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:
Torsten MĂŒtze ( talk) 16:24, 29 May 2019 (UTC)
References
{{
cite web}}
: CS1 maint: multiple names: authors list (
link)
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)
Ok. Will do as suggested. Torsten MĂŒtze ( talk) 14:30, 30 May 2019 (UTC)
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)
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
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)
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)
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)
The algorithm defines a Hamiltonian path in a Cayley graph of the symmetric group. The inverse permutations define a path in the permutohedron: | |
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:
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)
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 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)
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)
This edit request by an editor with a conflict of interest has now been answered. |
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:
Torsten MĂŒtze ( talk) 16:24, 29 May 2019 (UTC)
References
{{
cite web}}
: CS1 maint: multiple names: authors list (
link)
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)
Ok. Will do as suggested. Torsten MĂŒtze ( talk) 14:30, 30 May 2019 (UTC)
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)