Sequentially Indexing Permutations O(n^2)

quadratic.cpp

#include <array>
using std::array;
#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[])
{
  array<unsigned, 3> perm = {2, 0, 1};

  // Calculate the Lehmer code of the permutation.
  array<unsigned, 3> lehmer = perm;

  for (unsigned i = 1; i < perm.size(); ++i)
  {
    unsigned j = i;

    // Note the post-decrement (from i-1 to 0, inclusive).
    while (j--)
    {
      if (perm[j] < perm[i])
        --lehmer[i];
    }
  }

  // Convert the Lehmer code to base-10.
  unsigned index =
    lehmer[0] * factorial(2) +
    lehmer[1] * factorial(1) +
    lehmer[2] * factorial(0);

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