316:
306:
338:
328:
582:
71:
53:
22:
554:
447:
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
394:
496:
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.
495:
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
479:
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
187:
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
462:
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.
573:
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.
480:
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.
188:
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. —
262:
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.
389:
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.
242:
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)
708:
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
385:
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.
315:
710:
765:. (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)
170:
Indeed. The algorithm is known as the "Johnson-Trotter algorithm". Someone on
Knowledge changed it to "Steinhaus-..." I tried to change it back but a David Eppstein almost immediately reversed it.
424:
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
156:
Why does
Knowledge 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?
358:
769:. 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. -
337:
327:
448:
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. —
305:
668:
393:
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
609:
750:
The 4-place example here on 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
797:
119:
382:
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.
125:
792:
374:
Consecutive permutations in the sequence generated by the
Steinhaus–Johnson–Trotter algorithm have numbers of inversions that differ by one,
581:
807:
416:
In one phase of Even's algorithm, it says "all elements greater than the chosen element have their directions set to positive or negative,
95:
157:
211:
747:
Someone else must have observed this difference between two permutation schemes, but I didn't see it mentioned in either article.
505:
441:
420:
respectively". I don't understand what this is supposed to mean, especially the word "concentrated". If those elements should be
354:
802:
611:
generated by the
Steinhaus-Johnson-Trotter algorithm, where each permutation is color-coded (1=blue, 2=green, 3=yellow, 4=red).
78:
58:
428:
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
704:
The diagram is still on the article (and I agree that it's a good one, clearer than the other two earlier diagrams). What
778:
737:
722:
698:
624:
538:
519:
489:
472:
457:
406:
272:
256:
234:
219:
197:
179:
165:
151:
33:
733:
620:
718:
534:
453:
252:
230:
193:
21:
161:
560:
350:
215:
91:
729:
616:
175:
39:
688:
for their input on this edit (and my apologies if you are already watchlisted for this page). Regards,
171:
207:
714:
690:
683:
530:
449:
248:
226:
189:
94:
on Knowledge. If you would like to participate, please visit the project page, where you can join
497:
770:
758:
662:
402:
485:
468:
437:
295:
268:
515:
Since volume 4A is out, which covers this, should the reference be changed to volume 4A?
501:
291:
588:
774:
526:
786:
418:
according to whether they are concentrated at the start or the end of the permutation
148:
705:
570:
516:
398:
287:
761:
starts with A-B-C-D and ends with D-C-B-A. The 24-state sequence with 23 swaps is
432:
in the middle? Or if the statement means something else, then what does it mean?
713:
to include this credit, that would make more sense to me than putting it here. —
481:
464:
433:
264:
70:
52:
711:
Commons:File:Wheel diagram of Steinhaus-Johnson-Trotter algorithm for n=4.svg
87:
754:
of 24 states with 24 swaps, which could be written on a cylindrical strip.
83:
331:
Permutations form a Gray code. The swapped elements are always adjacent.
341:
Permutations, inversion vectors and inversion sets form a Gray code.
580:
336:
326:
314:
304:
147:
Does anyone have a reference for the origins of this algorithm?
563:
by an editor with a conflict of interest has now been answered.
548:
15:
225:
Yes, as the article now says in the new history section. —
643:
367:
591:
353:. The smaller numbers below the permutations are the
82:, a collaborative effort to improve the coverage of
376:
forming a Gray code for the factorial number system
603:
124:This article has not yet received a rating on the
397:). Maybe this could be mentioned in the article.
349:Permutations with green or orange background are
298:permutations define a path in the permutohedron:
642:Mütze, Torsten; Sawada, Joe; Williams, Aaron.
357:vectors. Red marks indicate swapped elements.
286:The algorithm defines a Hamiltonian path in a
281:
370:the article contains the following sentence:
8:
667:: CS1 maint: multiple names: authors list (
585:Wheel diagram of all permutations of length
19:
47:
590:
278:Gray code for the factorial number system
247:Ok, fixed. Thanks for letting me know. —
634:
577:Add the following diagram to the page:
49:
660:
412:Unclear description for Even's speedup
204:Is this the method of plain changes?
798:Unknown-importance Computing articles
7:
76:This article is within the scope of
38:It is of interest to the following
14:
552:
69:
51:
20:
104:Knowledge:WikiProject Computing
793:Start-Class Computing articles
359:Compare list in natural order.
107:Template:WikiProject Computing
1:
779:23:20, 6 September 2022 (UTC)
257:16:11, 13 February 2012 (UTC)
98:and see a list of open tasks.
506:18:07, 12 October 2013 (UTC)
166:23:04, 20 January 2010 (UTC)
152:18:35, 28 January 2006 (UTC)
808:Implemented requested edits
648:Combinatorial Object Server
273:14:18, 5 October 2022 (UTC)
235:06:29, 2 October 2011 (UTC)
220:06:14, 2 October 2011 (UTC)
824:
728:Ok. Will do as suggested.
490:21:00, 16 April 2013 (UTC)
473:21:11, 16 April 2013 (UTC)
458:20:48, 16 April 2013 (UTC)
442:20:38, 16 April 2013 (UTC)
126:project's importance scale
347:
284:
123:
64:
46:
757:The 4-place example for
738:14:30, 30 May 2019 (UTC)
723:22:59, 29 May 2019 (UTC)
699:22:52, 29 May 2019 (UTC)
625:16:24, 29 May 2019 (UTC)
569:After being informed by
539:03:00, 2 July 2013 (UTC)
520:02:44, 2 July 2013 (UTC)
407:16:19, 1 June 2012 (UTC)
198:00:33, 15 May 2015 (UTC)
180:21:50, 14 May 2015 (UTC)
644:"Generate permutations"
411:
803:All Computing articles
612:
605:
342:
332:
320:
310:
92:information technology
28:This article is rated
606:
584:
340:
330:
318:
308:
79:WikiProject Computing
589:
604:{\displaystyle n=4}
613:
601:
527:go ahead and do so
343:
333:
321:
311:
110:Computing articles
34:content assessment
567:
566:
365:
364:
361:
299:
210:comment added by
140:
139:
136:
135:
132:
131:
815:
759:Heap's algorithm
697:
695:
687:
673:
672:
666:
658:
656:
654:
639:
610:
608:
607:
602:
556:
555:
549:
348:
285:
282:
222:
112:
111:
108:
105:
102:
73:
66:
65:
55:
48:
31:
25:
24:
16:
823:
822:
818:
817:
816:
814:
813:
812:
783:
782:
745:
691:
689:
681:
678:
677:
676:
659:
652:
650:
641:
640:
636:
587:
586:
553:
547:
513:
511:Knuth reference
414:
292:symmetric group
280:
205:
145:
109:
106:
103:
100:
99:
32:on Knowledge's
29:
12:
11:
5:
821:
819:
811:
810:
805:
800:
795:
785:
784:
767:a Möbius strip
744:
741:
726:
725:
715:David Eppstein
684:David Eppstein
675:
674:
633:
632:
628:
614:
600:
597:
594:
579:
565:
564:
557:
546:
543:
542:
541:
531:David Eppstein
512:
509:
493:
492:
477:
476:
475:
450:David Eppstein
413:
410:
380:
379:
363:
362:
345:
344:
334:
323:
322:
312:
301:
300:
279:
276:
260:
259:
249:David Eppstein
240:
239:
238:
237:
227:David Eppstein
202:
201:
200:
190:David Eppstein
144:
141:
138:
137:
134:
133:
130:
129:
122:
116:
115:
113:
96:the discussion
74:
62:
61:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
820:
809:
806:
804:
801:
799:
796:
794:
791:
790:
788:
781:
780:
776:
772:
768:
764:
760:
755:
753:
748:
742:
740:
739:
735:
731:
730:Torsten Mütze
724:
720:
716:
712:
707:
703:
702:
701:
700:
696:
694:
685:
670:
664:
649:
645:
638:
635:
631:
627:
626:
622:
618:
617:Torsten Mütze
598:
595:
592:
583:
578:
575:
572:
562:
558:
551:
550:
544:
540:
536:
532:
528:
524:
523:
522:
521:
518:
510:
508:
507:
503:
499:
491:
487:
483:
478:
474:
470:
466:
461:
460:
459:
455:
451:
446:
445:
444:
443:
439:
435:
431:
427:
423:
419:
409:
408:
404:
400:
396:
395:magnification
391:
387:
383:
377:
373:
372:
371:
369:
368:At the moment
360:
356:
352:
346:
339:
335:
329:
325:
324:
319:Permutohedron
317:
313:
307:
303:
302:
297:
293:
289:
283:
277:
275:
274:
270:
266:
258:
254:
250:
246:
245:
244:
236:
232:
228:
224:
223:
221:
217:
213:
209:
203:
199:
195:
191:
186:
185:
184:
183:
182:
181:
177:
173:
168:
167:
163:
159:
158:87.194.117.80
154:
153:
150:
142:
127:
121:
118:
117:
114:
97:
93:
89:
85:
81:
80:
75:
72:
68:
67:
63:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
766:
762:
756:
751:
749:
746:
727:
692:
679:
651:. Retrieved
647:
637:
629:
615:
576:
568:
561:edit request
545:Edit request
514:
494:
429:
425:
421:
417:
415:
392:
388:
384:
381:
375:
366:
309:Cayley graph
288:Cayley graph
261:
241:
212:82.139.87.39
206:— Preceding
169:
155:
146:
77:
40:WikiProjects
763:not a cycle
743:Cyclicality
426:distance to
172:Onlinetexts
30:Start-class
787:Categories
630:References
693:Spintendo
355:inversion
101:Computing
88:computing
84:computers
59:Computing
680:Pinging
663:cite web
208:unsigned
149:Resistor
706:MrOllie
653:May 28,
571:MrOllie
525:Please
517:Bubba73
430:exactly
399:Lipedia
296:inverse
290:of the
143:Origins
482:aditsu
465:aditsu
434:aditsu
422:at the
294:. The
265:Jumpow
90:, and
36:scale.
752:cycle
559:This
498:IanHH
775:talk
771:A876
734:talk
719:talk
669:link
655:2019
621:talk
535:talk
502:talk
486:talk
469:talk
454:talk
438:talk
403:talk
269:talk
253:talk
231:talk
216:talk
194:talk
176:talk
162:talk
529:. —
351:odd
120:???
789::
777:)
736:)
721:)
665:}}
661:{{
646:.
623:)
537:)
504:)
488:)
471:)
456:)
440:)
405:)
271:)
255:)
233:)
218:)
196:)
178:)
164:)
86:,
773:(
732:(
717:(
686::
682:@
671:)
657:.
619:(
599:4
596:=
593:n
533:(
500:(
484:(
467:(
452:(
436:(
401:(
378:.
267:(
251:(
229:(
214:(
192:(
174:(
160:(
128:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
