Sequentially Indexing Permutations O(n)

linear.cpp

#include <array>
using std::array;
#include <bitset>
using std::bitset;
#include <iostream>
using std::cout;
using std::endl;

unsigned factorial(unsigned n)
{
  return n <= 1 ? 1 : n * factorial(n - 1);
}

int main(int argc, char* argv[])
{
  // Precomputed table containing the number of ones in the binary
  // representation of each number.  The largest 3-bit number is
  // 2^3-1=7.
  array<unsigned, 3> onesCountLookup;

  for (unsigned i = 0; i < 7; ++i)
  {
    bitset<3> bits(i);
    onesCountLookup[i] = bits.count();
  }

  // Precomputed table of factorials, in reverse order.
  array<unsigned, 3> factorials = {factorial(2), factorial(1), factorial(0)};

  array<unsigned, 3> perm = {2, 0, 1};
  array<unsigned, 3> lehmer;
  bitset<3> seen;

  // The first digit of the Lehmer code is always the first digit of
  // the permutation.
  lehmer[0] = perm[0];

  // Mark the digit as seen (bitset uses right-to-left indexing).
  seen[perm.size() - 1 - perm[0]] = 1;

  // The last digit of the Lehmer code is always 0.
  lehmer[perm.size() - 1] = 0;

  for (unsigned i = 1; i < perm.size() - 1; ++i)
  {
    seen[perm.size() - 1 - perm[i]] = 1;

    // The number of "seen" digits to the left of this digit is the
    // count of ones left of this digit.
    unsigned numOnes = onesCountLookup[seen.to_ulong() >> (perm.size() - perm[i])];

    lehmer[i] = perm[i] - numOnes;
  }

  // Convert the Lehmer code to base-10.  The last digit is always 0
  // (excluded), and the 1! = 1;
  unsigned index =
    lehmer[0] * factorials[0] +
    lehmer[1];

  cout << "Permutation: ";
  for (unsigned i : perm)
    cout << i;
  cout << '\n';

  cout << "Lehmer code: ";
  for (unsigned i : lehmer)
    cout << i;
  cout << '\n';

  cout << "Index: " << index << endl;

  return 0;
}