7 ms·
SEPA: A Simple, Efficient Permutation Algorithm
- mattnewport 8y agoThis sounds like what next_permutation does in the C++ STL. https://en.cppreference.com/w/cpp/algorithm/next_permutation https://en.cppreference.com/w/cpp/algorithm/next_permutation
- swingline-747 8y agoBtw, XOR swap... probably slower than register-aliased swap, but it swaps two registers without using a third: void swap(char *s, int a, int b) { s[b] ^= s[a]; s[a] ^= s[b]; s[b] ^= s[a]; }
- ur-whale 8y agoYou'd better hope that a!=b
- scj 8y agoWhy would a==b be a problem with the XOR swap trick? function xorSwapTest(min, max) { for (var i = min; i < max; i++) { var a = i, b = i; b ^= a; a ^= b; b ^= a; if (a != i || b != i) throw Error("Problem with " + i); } return true; }
- saagarjha 8y agoThe issue is that if a == b, &s[a] == &s[b]; i.e. you're writing to the same address.
- and-then 8y agoEdge-case FUD.
- saagarjha 8y agoMost compilers will optimize this to whatever is faster even if you use the clearer version.
- and-then 8y agoYou're making a sweeping, laughably-false assertion. Clearly you don't understand how compilers work. C compilers are not miraculous magic boxes. They have limited information and limited optimizations. It's very likely an obscure implementation of an algorithm will more-or-less translate one-to-one to nearly equivalent assembly because the compiler can't analyze it.
- saagarjha 8y agoI think you've misrepresented what I said, which was that the compiler is good enough to pick between a register or XOR-swap (in the comment I was replying to), based on the architecture and calling sites.
- foota 8y agoThe "Clearly you don't understand how compilers work" portion of this comment is unnecessary.
- ur-whale 8y agoWhile this is very cool, I'm having a hard time believing it is a new development.
- pharrington 8y agoStandard procedure is to do something like requesting the mods add "2001" to the title.
- FabHK 8y agoOr, in this case, "(<1400)".
- chrisweekly 8y agolol -- would likely want to include "A.D." to be clear it's a date!
- mauricioc 8y agoAccording 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