title: Computing the Factoradic Rank of a Permutation (N choose K)
body: <p>I've recently learnt about <a href="http://en.wikipedia.org/wiki/Combinatorial_number_system" rel="nofollow noreferrer">CNS</a> and <a href="http://en.wikipedia.org/wiki/Factorial_number_system" rel="nofollow noreferrer">FNS</a>, and since they look so elegant to me, I decided to try and implement methods to generate combinations and permutations using those techniques. I finished my method to convert from <em>n choose k</em> combinations to a CSN rank and vice-versa but I'm banging my head against the wall trying to do the same with <em>n choose k</em> (unique) permutations.</p>
  
  <p>Thanks to <a href="https://stackoverflow.com/questions/4120743/how-to-generate-a-permutation/4120772#4120772">@Joshua</a> I got the <em>unranking</em> (FNS to permutation) method working:</p>
  
  <pre><code>function Pr_Unrank($n, $k, $rank) { // rank starts at 1
      if ($n &gt;= $k) {
          if (($rank &gt; 0) &amp;&amp; ($rank &lt;= Pr($n, $k))) {
              $rank--;
              $result = array();
              $factoriadic = array();
  
              for ($i = 1; $i &lt;= ($n - $k); ++$i) {
                  $rank *= $i;
              }
  
              for ($j = 1; $j &lt;= $n; ++$j) {
                  $factoriadic[$n - $j] = ($rank % $j) + 1; $rank /= $j;
              }
  
              for ($i = $n - 1; $i &gt;= 0; --$i) {
                  $result[$i] = $factoriadic[$i];
  
                  for ($j = $i + 1; $j &lt; $n; ++$j) {
                      if ($result[$j] &gt;= $result[$i]) {
                          ++$result[$j];
                      }
                  }
              }
  
              return array_reverse(array_slice($result, 0 - $k));
          }
      }
  
      return false;
  }
  </code></pre>
  
  <p>This is my current attempt at a <em>ranking</em> (permutation to FNS) method:</p>
  
  <pre><code>function Pr_Rank($n, $k, $permutation) {
      if ($n &gt;= $k) {
          $result = range(1, $n);
          $factoriadic = array();
  
          foreach ($permutation as $key =&gt; $value) {
              $factoriadic[$k - $key - 1] = array_search($value, $result);
              array_splice($result, $factoriadic[$k - $key - 1], 1);
          }
  
          $result = 1;
  
          foreach (array_filter($factoriadic) as $key =&gt; $value) {
              $result += F($key) * $value;
          }
  
          return $result;
      }
  
      return false;
  }
  </code></pre>
  
  <p>And these are the helper functions I'm using:</p>
  
  <pre><code>function F($n) { // Factorial
      return array_product(range($n, 1));
  }
  
  function Pr($n, $k) { // Permutations (without Repetitions)
      return array_product(range($n - $k + 1, $n));
  }
  </code></pre>
  
  <hr>
  
  <p>The problem is, <strong>the <code>Pr_Rank()</code> method only returns the correct rank when <code>n = k</code></strong> (<a href="http://codepad.org/2Is9oM3a" rel="nofollow noreferrer">demo</a>):</p>
  
  <pre><code>var_dump(Pr_Rank(5, 2, Pr_Unrank(5, 2, 10))); // 3, should be 10
  var_dump(Pr_Rank(5, 3, Pr_Unrank(5, 3, 10))); // 4, should be 10
  var_dump(Pr_Rank(5, 5, Pr_Unrank(5, 5, 10))); // 10, it's correct
  </code></pre>
  
  <p>I guided myself using the Wikipedia article I linked above and <a href="http://msdn.microsoft.com/en-us/library/aa302371.aspx" rel="nofollow noreferrer">this MSDN article</a>, I know neither of them contemplate k-sized subsets, but I'm completely in the dark what such logic would look like...</p>
  
  <p>I also tried Googling and searching existing questions / answers but nothing relevant has come up yet.</p>