SEPA: A Simple, Efficient Permutation Algorithm | Hacker News Reader

SEPA: A Simple, Efficient Permutation Algorithm

quickperm.org

55 pointsnavigaid16 comments

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)

Indeed 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 (now page 319 of Volume 4A)

[2]: https://www.quora.com/How-would-you-explain-an-algorithm-tha...

[3]: https://stackoverflow.com/a/353248/4958

This sounds like what next_permutation does in the C++ STL. https://en.cppreference.com/w/cpp/algorithm/next_permutation

Btw, 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];
    }

You'd better hope that a!=b

Why 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;
  }

The issue is that if a == b, &s[a] == &s[b]; i.e. you're writing to the same address.

Edge-case FUD.

Most compilers will optimize this to whatever is faster even if you use the clearer version.

You'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.

I 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.

The "Clearly you don't understand how compilers work" portion of this comment is unnecessary.

While this is very cool, I'm having a hard time believing it is a new development.

Standard procedure is to do something like requesting the mods add "2001" to the title.

Or, in this case, "(<1400)".

lol -- would likely want to include "A.D." to be clear it's a date!

Reply on news.ycombinator.com