# Computing the Factoradic Rank of a Permutation (N choose K)

Posted on

Computing the Factoradic Rank of a Permutation (N choose K) – Here in this article, we will share some of the most common and frequently asked about PHP problem in programming with detailed answers and code samples. There’s nothing quite so frustrating as being faced with PHP errors and being unable to figure out what is preventing your website from functioning as it should like php and math . If you have an existing PHP-based website or application that is experiencing performance issues, let’s get thinking about Computing the Factoradic Rank of a Permutation (N choose K).

I’ve recently learnt about CNS and FNS, 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 n choose k combinations to a CSN rank and vice-versa but I’m banging my head against the wall trying to do the same with n choose k (unique) permutations.

Thanks to @Joshua I got the unranking (FNS to permutation) method working:

``````function Pr_Unrank(\$n, \$k, \$rank) { // rank starts at 1
if (\$n >= \$k) {
if ((\$rank > 0) && (\$rank <= Pr(\$n, \$k))) {
\$rank--;
\$result = array();

for (\$i = 1; \$i <= (\$n - \$k); ++\$i) {
\$rank *= \$i;
}

for (\$j = 1; \$j <= \$n; ++\$j) {
\$factoriadic[\$n - \$j] = (\$rank % \$j) + 1; \$rank /= \$j;
}

for (\$i = \$n - 1; \$i >= 0; --\$i) {

for (\$j = \$i + 1; \$j < \$n; ++\$j) {
if (\$result[\$j] >= \$result[\$i]) {
++\$result[\$j];
}
}
}

return array_reverse(array_slice(\$result, 0 - \$k));
}
}

return false;
}
``````

This is my current attempt at a ranking (permutation to FNS) method:

``````function Pr_Rank(\$n, \$k, \$permutation) {
if (\$n >= \$k) {
\$result = range(1, \$n);

foreach (\$permutation as \$key => \$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 => \$value) {
\$result += F(\$key) * \$value;
}

return \$result;
}

return false;
}
``````

And these are the helper functions I’m using:

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

The problem is, the `Pr_Rank()` method only returns the correct rank when `n = k` (demo):

``````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
``````

I guided myself using the Wikipedia article I linked above and this MSDN article, I know neither of them contemplate k-sized subsets, but I’m completely in the dark what such logic would look like…

I also tried Googling and searching existing questions / answers but nothing relevant has come up yet.

Solution :

After a good night sleep and a little help from pen & paper, I figured it out. In case anyone is interested:

For instance, the 42nd 5 choose 3 permutation is `4-2-5`, but if you look at `Pr_Unrank()`, where `array_slice()` is called, you’ll notice that the actual permutation (in lexicographic order) is actually `4-2-5[-1-3]`, the last two elements are discarded so that you only end up with `k` elements.

This is very important to compute the decimal representation of the factoriadic (`3-1-2[-0-0]`):

• `4-2-5` = `(2! * 3) + (1! * 1) + (0! * 2)` = `9`
• `4-2-5-1-3` = `(4! * 3) + (3! * 1) + (2! * 2) + (1! * 0) + (0! * 0)` = `82`

Still, `82` is not the right answer. To get it, we must divide it by the result of:

• `Pr(5, 5) / Pr(5, 3)` (=) `(5 - 3)!` = `120 / 60` = `2`

So `82 / 2` is `41`, all that I need to do is add `1` to get the ranking starting at 1.

``````Array // 5 choose 3 permutations
(
 => 1-2-3
 => 1-2-4
 => 1-2-5
 => 1-3-2
 => 1-3-4
 => 1-3-5
 => 1-4-2
 => 1-4-3
 => 1-4-5
 => 1-5-2
 => 1-5-3
 => 1-5-4
 => 2-1-3
 => 2-1-4
 => 2-1-5
 => 2-3-1
 => 2-3-4
 => 2-3-5
 => 2-4-1
 => 2-4-3
 => 2-4-5
 => 2-5-1
 => 2-5-3
 => 2-5-4
 => 3-1-2
 => 3-1-4
 => 3-1-5
 => 3-2-1
 => 3-2-4
 => 3-2-5
 => 3-4-1
 => 3-4-2
 => 3-4-5
 => 3-5-1
 => 3-5-2
 => 3-5-4
 => 4-1-2
 => 4-1-3
 => 4-1-5
 => 4-2-1
 => 4-2-3
 => 4-2-5
 => 4-3-1
 => 4-3-2
 => 4-3-5
 => 4-5-1
 => 4-5-2
 => 4-5-3
 => 5-1-2
 => 5-1-3
 => 5-1-4
 => 5-2-1
 => 5-2-3
 => 5-2-4
 => 5-3-1
 => 5-3-2
 => 5-3-4
 => 5-4-1
 => 5-4-2
 => 5-4-3
)
``````