3 ms·
According to Donald Knuth, "This algorithm goes back to Nārāyaṇa Paṇḍita in 14th-century India; it also appeared in C. F. Hindenburg's preface to _Specimen Anal
by mauricioc 8y ago
According to Donald Knuth, "This algorithm goes back to Nārāyaṇa Paṇḍita in 14th-century India; it also appeared in C. F. Hindenburg's preface to _Specimen Analyticum de Lineis Curvis Secundi Ordinis_ by C. F. Rudiger (Leipzig: 1784), xlvi--xlvii, and it has been frequently rediscovered ever since". (Volume 4A, Section 7.2.1.2, Algorithm L)
- svat 8y agoIndeed this is precisely Algorithm L of section 7.2.1.2 “Generating all permutations” (described on its very first page [1]), and is also what is used by C++'s `next_permutation`, among others. There are a few expositions of it online [2] (including this 2008 StackOverflow answer of mine: [3]). [1] Draft version of Knuth's Fascicle 2B: http://www.cs.utsa.edu/~wagner/knuth/fasc2b.pdf#page=5 http://www.cs.utsa.edu/~wagner/knuth/fasc2b.pdf#page=5 (now page 319 of Volume 4A) [2]: https://www.quora.com/How-would-you-explain-an-algorithm-that-generates-permutations-using-lexicographic-ordering https://www.quora.com/How-would-you-explain-an-algorithm-tha... [3]: https://stackoverflow.com/a/353248/4958 https://stackoverflow.com/a/353248/4958