{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T23:50:30Z","timestamp":1769212230094,"version":"3.49.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T00:00:00Z","timestamp":1573776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>\n            Knuth assigned the following open problem a difficulty rating of 48\/50 in\n            <jats:italic>The Art of Computer Programming Volume 4A<\/jats:italic>\n            :\n          <\/jats:p>\n          <jats:p>\n            For odd\n            <jats:italic>n<\/jats:italic>\n            \u2265 3, can the permutations of { 1,2,\u2026 ,\n            <jats:italic>n<\/jats:italic>\n            } be ordered in a cyclic list so that each permutation is transformed into the next by applying either the operation \u03c3, a rotation to the left, or \u03c4, a transposition of the first two symbols?\n          <\/jats:p>\n          <jats:p>\n            The Sigma-Tau problem is equivalent to finding a Hamilton cycle in the directed Cayley graph generated by \u03c3 = (1 2 \u22c5\n            <jats:italic>n<\/jats:italic>\n            ) and \u03c4 = (1 2). In this article, we solve the Sigma-Tau problem by providing a simple\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )-time successor rule to generate successive permutations of a Hamilton cycle in the aforementioned Cayley graph.\n          <\/jats:p>","DOI":"10.1145\/3359589","type":"journal-article","created":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T21:16:57Z","timestamp":1573852617000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Solving the Sigma-Tau Problem"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7364-2993","authenticated-orcid":false,"given":"Joe","family":"Sawada","sequence":"first","affiliation":[{"name":"University of Guelph, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aaron","family":"Williams","sequence":"additional","affiliation":[{"name":"Williams College"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Tecnologia, Negocios y Ocios. Retrieved","author":"Asenjo I. R.","year":"2019","unstructured":"I. R. Asenjo . n.d. HPC MARKET Ciencia , Tecnologia, Negocios y Ocios. Retrieved March 1, 2019 from https:\/\/ireneses.wordpress.com\/. I. R. Asenjo. n.d. HPC MARKET Ciencia, Tecnologia, Negocios y Ocios. Retrieved March 1, 2019 from https:\/\/ireneses.wordpress.com\/."},{"key":"e_1_2_1_2_1","first-page":"266","article-title":"Method for solving optimization problems in structured combinatorial objects","volume":"8","author":"Asenjo I. R.","year":"2012","unstructured":"I. R. Asenjo . 2012 . Method for solving optimization problems in structured combinatorial objects . U.S. Patent 8 , 266 ,089. I. R. Asenjo. 2012. Method for solving optimization problems in structured combinatorial objects. U.S. Patent 8,266,089.","journal-title":"U.S. Patent"},{"key":"e_1_2_1_3_1","first-page":"697","article-title":"Method for solving optimization problems in structured combinatorial objects","volume":"9","author":"Asenjo I. R.","year":"2018","unstructured":"I. R. Asenjo . 2018 . Method for solving optimization problems in structured combinatorial objects . U.S. Patent 9 , 697 ,464. I. R. Asenjo. 2018. Method for solving optimization problems in structured combinatorial objects. U.S. Patent 9,697,464.","journal-title":"U.S. Patent"},{"key":"e_1_2_1_4_1","volume-title":"Handbook of Combinatorics","author":"Babai L.","unstructured":"L. Babai . 1996. Automorphism groups, isomorphism, reconstruction . In Handbook of Combinatorics , R. L. Graham, Martin Grotschel, and L\u00e1szl\u00f3 Lov\u00e1sz (Eds.). Vol. 2 . Elsevier , 1447--1540. L. Babai. 1996. Automorphism groups, isomorphism, reconstruction. In Handbook of Combinatorics, R. L. Graham, Martin Grotschel, and L\u00e1szl\u00f3 Lov\u00e1sz (Eds.). Vol. 2. Elsevier, 1447--1540."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-007-9094-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081089308818261"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.159045"},{"key":"e_1_2_1_8_1","unstructured":"R. Duckworth and F. Stedman. 1667. Tintinnalogia. Self-published.  R. Duckworth and F. Stedman. 1667. Tintinnalogia. Self-published."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2018.07.010"},{"key":"e_1_2_1_10_1","volume-title":"Algebraic Graph Theory. Graduate Texts in Mathematics","volume":"207","author":"Godsil C.","unstructured":"C. Godsil and G. Royle . 2001 . Algebraic Graph Theory. Graduate Texts in Mathematics , Vol. 207 . Springer. C. Godsil and G. Royle. 2001. Algebraic Graph Theory. Graduate Texts in Mathematics, Vol. 207. Springer."},{"key":"e_1_2_1_11_1","first-page":"632","article-title":"Pulse code communication","volume":"2","author":"Gray F.","year":"1947","unstructured":"F. Gray . 1947 . Pulse code communication . U.S. Patent 2 , 632 ,058. F. Gray. 1947. Pulse code communication. U.S. Patent 2,632,058.","journal-title":"U.S. Patent"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9544-z"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00314-9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1963-0159764-2"},{"key":"e_1_2_1_15_1","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","unstructured":"D. E. Knuth . 2011. The Art of Computer Programming , Volume 4A Combinatorial Algorithms, Part 1 . Addison-Wesley . D. E. Knuth. 2011. The Art of Computer Programming, Volume 4A Combinatorial Algorithms, Part 1. Addison-Wesley."},{"key":"e_1_2_1_16_1","first-page":"362","article-title":"Sequential generation of arrangements by means of a basis of transpositions","volume":"11","author":"Kompel\u2019makher V. L.","year":"1975","unstructured":"V. L. Kompel\u2019makher and V. A. Liskovets . 1975 . Sequential generation of arrangements by means of a basis of transpositions . Kibernetica 11 , 3 (1975), 362 -- 366 . V. L. Kompel\u2019makher and V. A. Liskovets. 1975. Sequential generation of arrangements by means of a basis of transpositions. Kibernetica 11, 3 (1975), 362--366.","journal-title":"Kibernetica"},{"key":"e_1_2_1_17_1","volume-title":"Combinatorial Structures and Their Applications: Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications. 243--246","author":"Lov\u00e1sz L.","year":"1970","unstructured":"L. Lov\u00e1sz . 1970 . Problem 11 . In Combinatorial Structures and Their Applications: Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications. 243--246 . L. Lov\u00e1sz. 1970. Problem 11. In Combinatorial Structures and Their Applications: Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications. 243--246."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdw004"},{"key":"e_1_2_1_19_1","unstructured":"A. Nijenhuis and H. S. Wilf. 1975. Combinatorial Algorithms. Academic Press New York NY.  A. Nijenhuis and H. S. Wilf. 1975. Combinatorial Algorithms. Academic Press New York NY."},{"key":"e_1_2_1_20_1","unstructured":"A. Nijenhuis and H. S. Wilf. 1978. Combinatorial Algorithms (2nd ed.). Academic Press New York NY.  A. Nijenhuis and H. S. Wilf. 1978. Combinatorial Algorithms (2nd ed.). Academic Press New York NY."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2009.02.018"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002394X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90036-3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00078-R"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/100808782"},{"key":"e_1_2_1_26_1","volume-title":"COCOON 2005: Computing and Combinatorics. Lecture Notes in Computer Science","volume":"3595","author":"Ruskey F.","unstructured":"F. Ruskey and A. Williams . 2005. Generating combinations by prefix shifts . In COCOON 2005: Computing and Combinatorics. Lecture Notes in Computer Science , Vol. 3595 . Springer, 570--576. F. Ruskey and A. Williams. 2005. Generating combinations by prefix shifts. In COCOON 2005: Computing and Combinatorics. Lecture Notes in Computer Science, Vol. 3595. Springer, 570--576."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.11.048"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798598"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 13th International Conference on Language and Automata Theory and Applications (LATA\u201919)","author":"Rytter W.","unstructured":"W. Rytter and W. Zuba . 2019. Syntactic view of Sigma-Tau generation of permutations . In Proceedings of the 13th International Conference on Language and Automata Theory and Applications (LATA\u201919) . W. Rytter and W. Zuba. 2019. Syntactic view of Sigma-Tau generation of permutations. In Proceedings of the 13th International Conference on Language and Automata Theory and Applications (LATA\u201919)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144595295272"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.02.005"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Sawada J.","unstructured":"J. Sawada and A. Williams . 2018. A Hamilton path for the Sigma-Tau problem . In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918) . J. Sawada and A. Williams. 2018. A Hamilton path for the Sigma-Tau problem. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/356689.356692"},{"key":"e_1_2_1_34_1","unstructured":"Fabian Stedman. 1677. Campanalogia. Self-published.  Fabian Stedman. 1677. Campanalogia. Self-published."},{"key":"e_1_2_1_35_1","volume-title":"One Hundred Problems in Elementary Mathematics","author":"Steinhaus H.","unstructured":"H. Steinhaus . 1963. One Hundred Problems in Elementary Mathematics . Pergamon Press . H. Steinhaus. 1963. One Hundred Problems in Elementary Mathematics. Pergamon Press."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00278"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1999.12005023"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/368637.368660"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.107"},{"key":"e_1_2_1_41_1","series-title":"Lecture Notes in Computer Science","volume-title":"WADS 2013: Algorithms and Data Structures Symposium","author":"Williams A.","unstructured":"A. Williams . 2013. The greedy gray code algorithm . In WADS 2013: Algorithms and Data Structures Symposium . Lecture Notes in Computer Science , Vol. 8037 . Springer , 525--536. A. Williams. 2013. The greedy gray code algorithm. In WADS 2013: Algorithms and Data Structures Symposium. Lecture Notes in Computer Science, Vol. 8037. Springer, 525--536."},{"key":"e_1_2_1_42_1","unstructured":"A. Williams. 2013. Hamiltonicity of the Cayley digraph on the symmetric group generated by &sigma; &equals; (12 &sdots; n) and \u03c4 &equals;(12) . arxiv:math.CO\/1307.2549v3.  A. Williams. 2013. Hamiltonicity of the Cayley digraph on the symmetric group generated by &sigma; &equals; (12 &sdots; n ) and \u03c4 &equals;(12) . arxiv:math.CO\/1307.2549v3."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3359589","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3359589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:06Z","timestamp":1750202586000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3359589"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,15]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3359589"],"URL":"https:\/\/doi.org\/10.1145\/3359589","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,15]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}