Для заданных n и k вернуть k-ю последовательность перестановок

Итак, если я правильно читаю вопрос, вы хотите найти k-ю перестановку, желательно без использования BigInteger, при условии, что k недостаточно велик, чтобы требовать BigInteger.

Если мы посмотрим на последовательность

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Мы можем переписать его так, чтобы число в каждой позиции было индексом в списке чисел, которые до сих пор не появлялись в строке:

0 0 0
0 1 0
1 0 0
1 1 0
2 0 0
2 1 0

Так, например, «2, 0, 0» означает начало со списка «1, 2, 3», затем возьмите третью (потому что мы индексируем с нуля), то есть 3, затем возьмите первую из оставшихся цифр » 1, 2 ", то есть 1, затем первая из оставшихся цифр, то есть" 2 ". Таким образом, получается «3, 1, 2».

Чтобы сгенерировать эти индексы, идите справа налево и разделите k на 1! для крайних правых двух мест, то 2! потом 3! потом 4! и т. д., а затем модулируем результат с количеством возможных индексов в этой позиции: 1 для крайнего правого, 2 для крайнего правого и т. д. Вам не нужно вычислять факториал каждый раз, потому что вы можете сохранить работающий продукт .

Вы можете выйти из цикла, как только k, разделенное на факториал, станет равным нулю, поэтому вам нужно только вычислить факториалы до примерно размера k, умноженного на последнее место, в котором k, разделенное на факториал, не равно нулю. Если k слишком велико, вам нужно переключиться на BigIntegers.

Когда у вас есть индексы, их довольно просто использовать для генерации перестановки.

Код (k начинается с 0, поэтому для поиска первого прохода 0, а не 1):

static public void findPermutation(int n, int k)
{
    int[] numbers = new int[n];
    int[] indices = new int[n];

    // initialise the numbers 1, 2, 3...
    for (int i = 0; i < n; i++)
        numbers[i] = i + 1;

    int divisor = 1;
    for (int place = 1; place <= n; place++)
    {
        if((k / divisor) == 0)
            break;  // all the remaining indices will be zero

        // compute the index at that place:
        indices[n-place] = (k / divisor) % place;
        divisor *= place;
    }

    // print out the indices:
    // System.out.println(Arrays.toString(indices));

    // permute the numbers array according to the indices:
    for (int i = 0; i < n; i++)
    {
        int index = indices[i] + i;

        // take the element at index and place it at i, moving the rest up
        if(index != i)
        {
            int temp = numbers[index];
            for(int j = index; j > i; j--)
               numbers[j] = numbers[j-1];
            numbers[i] = temp;
        }
    }

    // print out the permutation:
    System.out.println(Arrays.toString(numbers));
}

Демо

вывод:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

10000000-я перестановка для n = 100:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 92, 98, 96, 90, 91, 100, 94, 97, 95, 99, 93]

Индексы для k-й перестановки (использованные в ответе на этот вопрос) - это factoradic представление k и может быть вычислен без использования факториала или текущего произведения.

public static List<Integer> toFactoradic(int x) {
    List<Integer> result = new ArrayList<>();

    for(int i = 1; x > 0; x /= i++) {
        result.add(x % i);
    }

    Collections.reverse(result);
    return result;
}

Конечно, массив индексов должен быть дополнен 0 слева, чтобы длина массива индексов была равна количеству элементов для получения фактических индексов. В качестве альтернативы перестановка может быть применена с правого конца.

Конечно, bigints с таким интерфейсом нужен

когда у вас есть n = 100, у вас есть n! перестановки, что означает, что k находится в диапазоне k=<1,n!>

100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

что не вписывается в стандарт unsigned int

2^32=          4294967296
2^64=18446744073709551616

см. Быстрый точный факториал bigint

если вы немного измените интерфейс, вам вдруг больше не понадобятся bigint

просто измените API, чтобы он последовательно возвращал 1-ю, 2-ю, 3-ю, ... перестановку без указания k, поэтому вам понадобится что-то вроде:

• Обобщенная перестановка (без повторений) в C ++

конечно, это можно использовать, только если вы используете перестановку также последовательно. Вы также можете сделать функцию previous() для обработки почти последовательных алгоритмов. Для произвольного или непоследовательного доступа вам необходимо использовать bigints

Сначала мы можем создать фактологическое представление k, а затем использовать его для создания необходимой перестановки. Дополнительные сведения см. На странице https://en.wikipedia.org/wiki/Factorial_number_system.

public String getPermutation(int n, int k) {
    LinkedList<Integer> factoradic = new LinkedList<>();
    k=k-1; // because factoradic representation and its mapping to permutation starts from 0
    for(int i=1;i<=n; i++){ // get radix digits for n digits
        factoradic.addFirst(k%i);
        k=k/i;
    }
    
    //System.out.println(factoradic.size());
    List<Integer> numbers = new LinkedList<>();
    for(int i=1;i<=n;i++){
        numbers.add(i);
    }
    StringBuilder str = new StringBuilder();
    for(int x: factoradic){
        // System.out.println(x);
        str.append(String.valueOf(numbers.get(x)));
        numbers.remove(x);
    }
    return str.toString();
}