Вычисление факторического ранга перестановки (N выберите K)

Question

Я недавно узнал о CNS и FNS, и поскольку они выглядят настолько изящными для меня, я решил попробовать и реализовать методы генерации комбинаций и перестановок с использованием этих методов. Я закончил свой метод, чтобы преобразовать из n выбрать k комбинации с рейтингом CSN и наоборот, но я ударяю головой о стену, пытаясь сделать то же самое с n выбрать k (уникальные) перестановки.

Благодаря @Joshua я получил unranking (FNS перестановочной) метод работы:

function Pr_Unrank($n, $k, $rank) { // rank starts at 1 
    if ($n >= $k) { 
     if (($rank > 0) && ($rank <= Pr($n, $k))) { 
      $rank--; 
      $result = array(); 
      $factoriadic = 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) { 
       $result[$i] = $factoriadic[$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; 
} 

Это моя текущая попытка рейтинг (перестановку FNS) Метод:

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

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

И вот вспомогательные функции, которые я использую:

Не

---

Проблема заключается в том, метод Pr_Rank() только возвращает правильный ранг, когда 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 

Я проводил сам, используя статью Википедии я связан выше, и this MSDN article, я знаю, что ни из них созерцают подмножества k-размера, но я полностью в темноте, какая бы такая логика выглядела бы ...

Я также пробовал поиск в Google и поиск e xisting вопросы/ответы, но ничего существенного не появилось.

Answer 1

После хорошей ночи спать и немного помогать от пера & бумага, я это понял. В случае, если кому-то интересно:

---

Например, сорок второй 5 выбирают 3 перестановка 4-2-5, но если вы посмотрите на Pr_Unrank(), где array_slice() называется, вы заметите, что фактическое перестановка (в лексикографическом порядке) на самом деле 4-2-5[-1-3], последние два элемента отбрасываются, так что вы получаете только k элементов.

Это очень важно, чтобы вычислить десятичное представление 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

Тем не менее, 82 это не правильный ответ.Чтобы получить его, мы должны разделить его на результат:

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

Так 82/2 это 41, все, что мне нужно сделать, это добавить 1 для получения ранжирования начиная с 1.

---

Array // 5 choose 3 permutations 
(
    [1] => 1-2-3 
    [2] => 1-2-4 
    [3] => 1-2-5 
    [4] => 1-3-2 
    [5] => 1-3-4 
    [6] => 1-3-5 
    [7] => 1-4-2 
    [8] => 1-4-3 
    [9] => 1-4-5 
    [10] => 1-5-2 
    [11] => 1-5-3 
    [12] => 1-5-4 
    [13] => 2-1-3 
    [14] => 2-1-4 
    [15] => 2-1-5 
    [16] => 2-3-1 
    [17] => 2-3-4 
    [18] => 2-3-5 
    [19] => 2-4-1 
    [20] => 2-4-3 
    [21] => 2-4-5 
    [22] => 2-5-1 
    [23] => 2-5-3 
    [24] => 2-5-4 
    [25] => 3-1-2 
    [26] => 3-1-4 
    [27] => 3-1-5 
    [28] => 3-2-1 
    [29] => 3-2-4 
    [30] => 3-2-5 
    [31] => 3-4-1 
    [32] => 3-4-2 
    [33] => 3-4-5 
    [34] => 3-5-1 
    [35] => 3-5-2 
    [36] => 3-5-4 
    [37] => 4-1-2 
    [38] => 4-1-3 
    [39] => 4-1-5 
    [40] => 4-2-1 
    [41] => 4-2-3 
    [42] => 4-2-5 
    [43] => 4-3-1 
    [44] => 4-3-2 
    [45] => 4-3-5 
    [46] => 4-5-1 
    [47] => 4-5-2 
    [48] => 4-5-3 
    [49] => 5-1-2 
    [50] => 5-1-3 
    [51] => 5-1-4 
    [52] => 5-2-1 
    [53] => 5-2-3 
    [54] => 5-2-4 
    [55] => 5-3-1 
    [56] => 5-3-2 
    [57] => 5-3-4 
    [58] => 5-4-1 
    [59] => 5-4-2 
    [60] => 5-4-3 
)