k-я перестановка n: как работает деление факториала на n - i, а затем деление k на него дает индекс? - PullRequest
Новая
       91

k-я перестановка n: как работает деление факториала на n - i, а затем деление k на него дает индекс?

0 голосов
/ 21 июня 2020

Набор [1,2,3,...,n] содержит всего n! уникальные перестановки.

Путем перечисления и маркировки всех перестановок по порядку мы получаем следующую последовательность для n = 3:

"123" "132" "213" "231" "312 "" 321 "Для заданных n и k, вернуть k-ю последовательность перестановок.

Примечание:

Заданное n будет от 1 до 9 включительно.

Данное k будет между 1 и n! включительно. 

public class Solution {
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }

        ArrayList < Integer > num = new ArrayList < Integer > ();
        for (int i = 1; i <= n; i++) {
            num.add(i);
        }

        // calculate the factorial
        int factorial = 1;
        for (int i = 1; i <= n; i++) {
            factorial *= i;
        }

        k--;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            factorial /= (n - i);
            int index = k / factorial;
            sb.append(num.get(index));

            num.remove(index);

            // update current k
            k %= factorial;
        }

        return sb.toString();
    }
}
...