Недавно я узнал о CNS и FNS , и поскольку они выглядят настолько изящными для меня, я решил попробовать и реализовать методы генерации комбинаций и перестановок с использованием этих методов. Я закончил свой метод, чтобы преобразовать из n выбрать k комбинаций в ранг CSN и наоборот, но я ударяю головой о стену, пытаясь сделать то же самое с n выбором k (уникальных) перестановок.
Благодаря @Joshua я получил метод разукрупнения (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; }
И это вспомогательные функции, которые я использую:
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)); }
Проблема заключается в том, что 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
Я руководствовался тем, что использовал статью Wikipedia, связанную выше, и эту статью MSDN. Я знаю, что ни один из них не рассматривает подмножества k-размера, но я полностью в темноте, как бы выглядела такая логика …
Я также попробовал Googling и искал существующие вопросы / ответы, но ничего существенного не появилось.
После хорошего ночного сна и небольшой помощи от ручки и бумаги я понял это. В случае, если кто-то заинтересован:
Например, 42-я 5 выбирает 3 перестановки 4-2-5 , но если вы посмотрите на Pr_Unrank() , где array_slice() , вы заметите, что фактическая перестановка (в лексикографическом порядке) на самом деле равна 4-2-5[-1-3] , последние два элемента отбрасываются, так что вы 4-2-5[-1-3] только k элементов.
Это очень важно для вычисления десятичного представления факториада ( 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 )