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

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

Благодаря@Джошуа Я получилunranking (ФНС к перестановке) метод работает:

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

Это моя нынешняя попыткаranking (перестановка в 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));
}

Проблема в,the Pr_Rank() method only returns the correct rank when n = k (демонстрация):

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

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

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

Ответы на вопрос(1)

Решение Вопроса

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

Например,42nd 5 choose 3 перестановка4-2-5, но если вы посмотрите наPr_Unrank(), гдеarray_slice() Вы заметите, что фактическая перестановка (в лексикографическом порядке) на самом деле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
)
 17 июл. 2012 г., 03:19
Рад, что вы смогли понять это! Я просто не успел в это разобраться ...

Ваш ответ на вопрос