{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:49:57Z","timestamp":1780822197764,"version":"3.54.1"},"reference-count":36,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T00:00:00Z","timestamp":1637107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1162196"],"award-info":[{"award-number":["CCF-1162196"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1439084"],"award-info":[{"award-number":["CCF-1439084"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1553510"],"award-info":[{"award-number":["CNS-1553510"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,3,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present two simple, intuitive and general algorithmic frameworks that can be used to design a wide variety of permutation generation algorithms. The frameworks can be used to produce 19 existing permutation algorithms, including the well-known algorithms of Heap, Wells, Langdon, Zaks, Tompkins and Lipski. We use the frameworks to design two new sorting-based permutation generation algorithms, one of which is optimal.<\/jats:p>","DOI":"10.1093\/comjnl\/bxab181","type":"journal-article","created":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T03:20:20Z","timestamp":1634872820000},"page":"603-614","source":"Crossref","is-referenced-by-count":3,"title":["A Unified Framework to Discover Permutation Generation Algorithms"],"prefix":"10.1093","volume":"66","author":[{"given":"Pramod","family":"Ganapathi","sequence":"first","affiliation":[{"name":"State University of New York at Stony Brook , New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rezaul","family":"Chowdhury","sequence":"additional","affiliation":[{"name":"State University of New York at Stony Brook , New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,11,17]]},"reference":[{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/356689.356692","article-title":"Permutation generation methods","volume":"9","author":"Sedgewick","year":"1977","journal-title":"ACM Computing Surveys"},{"key":"2023031708555359200_","first-page":"987","article-title":"Loopless generation of multiset permutations using a constant number of variables by prefix shifts","author":"Williams","year":"2009","journal-title":"Proc. Symposium on Discrete Algorithms"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1090\/S0025-5718-1961-0127507-2","article-title":"Generation of permutations by transposition","volume":"15","author":"Wells","year":"1961","journal-title":"Mathematics of Computation"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1093\/comjnl\/6.3.293","article-title":"Permutations by interchanges","volume":"6","author":"Heap","year":"1963","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/359997.360002","article-title":"Permutation enumeration: four new permutation algorithms","volume":"19","author":"Ives","year":"1976","journal-title":"Communications of the ACM"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1093\/comjnl\/18.1.21","article-title":"A permutation generation method","volume":"18","author":"Fike","year":"1975","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1093\/comjnl\/19.2.156","article-title":"Programming improvements to Fike\u2019s algorithm for generating permutations","volume":"19","author":"Rohl","year":"1976","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02254864","article-title":"More on permutation generation methods","volume":"23","author":"Lipski","year":"1979","journal-title":"Computing"},{"key":"2023031708555359200_","volume-title":"Introduction to the Design and Analysis of Algorithms","author":"Levitin","year":"2012"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1090\/S0025-5718-1963-0159764-2","article-title":"Generation of permutations by adjacent transposition","volume":"17","author":"Johnson","year":"1963","journal-title":"Mathematics of Computation"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1145\/368637.368660","article-title":"Algorithm 115: Perm","volume":"5","author":"Trotter","year":"1962","journal-title":"Communications of the ACM"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/BF01932689","article-title":"A simplified loop-free algorithm for generating permutations","volume":"15","author":"Dershowitz","year":"1975","journal-title":"BIT Numerical Mathematics"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/BF01937486","article-title":"A new algorithm for generation of permutations","volume":"24","author":"Zaks","year":"1984","journal-title":"BIT Numerical Mathematics"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1093\/comjnl\/21.4.302","article-title":"Generating permutations by choosing","volume":"21","author":"Rohl","year":"1978","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1145\/363282.363315","article-title":"An algorithm for generating permutations","volume":"10","author":"Langdon","year":"1967","journal-title":"Communications of the ACM"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0020-0190(01)00141-7","article-title":"Ranking and unranking permutations in linear time","volume":"79","author":"Myrvold","year":"2001","journal-title":"Information Processing Letters"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1090\/S0025-5718-1962-0144828-9","article-title":"Generation of permutations by addition","volume":"16","author":"Howell","year":"1962","journal-title":"Mathematics of Computation"},{"key":"2023031708555359200_","volume-title":"Matters Computational: Ideas, Algorithms, Source Code","author":"Arndt","year":"2010"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1093\/comjnl\/13.2.152","article-title":"Generation of permutation sequences: Part 1","volume":"13","author":"Ord-Smith","year":"1970","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1093\/comjnl\/14.2.136","article-title":"Generation of permutation sequences: Part 2","volume":"14","author":"Ord-Smith","year":"1971","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1093\/comjnl\/21.4.296","article-title":"Evaluation of permutation algorithms","volume":"21","author":"Roy","year":"1978","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/comjnl\/26.2.97","article-title":"Parallel generation of permutations","volume":"26","author":"Gupta","year":"1983","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","first-page":"496","article-title":"An optimal parallel algorithm for integer sorting","author":"Reif","year":"1985","journal-title":"Foundations of Computer Science"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01933707","article-title":"Parallel generation of permutations and combinations","volume":"26","author":"Chen","year":"1986","journal-title":"BIT Numerical Mathematics"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1093\/comjnl\/30.5.433","article-title":"Adaptive and optimal parallel algorithms for enumerating permutations and combinations","volume":"30","author":"Akl","year":"1987","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","first-page":"95","article-title":"Parallel algorithms for generating random permutations on a shared memory machine","volume-title":"Proc. Symposium on Parallel Algorithms and Architectures","author":"Anderson","year":"1990"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1006\/jagm.1997.0889","article-title":"Generating multiset permutations in constant time","volume":"25","author":"Korsh","year":"1997","journal-title":"Journal of Algorithms"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1093\/comjnl\/47.5.612","article-title":"Loopless array generation of multiset permutations","volume":"47","author":"Korsh","year":"2004","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3125632","article-title":"Autogen: Automatic Discovery of Efficient Recursive Divide-&-Conquer Algorithms for Solving Dynamic Programming Problems","volume":"4","author":"Chowdhury","year":"2017","journal-title":"ACM Transactions on Parallel Computing"},{"key":"2023031708555359200_","article-title":"Automatic Discovery of Efficient Divide-&-Conquer Algorithms for Dynamic Programming Problems","volume-title":"PhD thesis Department of Computer Science","author":"Ganapathi","year":"2016"},{"key":"2023031708555359200_","volume-title":"The Art of Computer Programming Volume 4A: Combinatorial Algorithms, Part 1","author":"Knuth","year":"2011"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"1214","DOI":"10.1137\/1.9781611975994.74","article-title":"Combinatorial generation via permutation languages","author":"Hartung","year":"2020","journal-title":"Proc. Symposium on Discrete Algorithms"},{"key":"2023031708555359200_","author":"OEIS Sequence A055881","year":"2020"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1093\/comjnl\/34.6.569","article-title":"Ord Smith\u2019s pseudo-lexicographical permutation procedure is the Tompkins-Paige algorithm","volume":"34","author":"Rohl","year":"1991","journal-title":"The Computer Journal"},{"key":"2023031708555359200_","first-page":"1","article-title":"Combinatorial generation","volume":"11","author":"Ruskey","year":"2003","journal-title":"Working draft. University of Victoria"},{"key":"2023031708555359200_","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1145\/321765.321781","article-title":"Loopless algorithms for generating permutations, combinations, and other combinatorial configurations","volume":"20","author":"Ehrlich","year":"1973","journal-title":"Journal of the ACM"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/3\/603\/49531064\/bxab181.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/3\/603\/49531064\/bxab181.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,11]],"date-time":"2023-11-11T14:41:42Z","timestamp":1699713702000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/3\/603\/6429743"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,17]]},"references-count":36,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,11,17]]},"published-print":{"date-parts":[[2023,3,15]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxab181","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,3]]},"published":{"date-parts":[[2021,11,17]]}}}