Ответ 1
Итак, если я правильно читаю вопрос, вы хотите найти k-ю перестановку, желательно, не используя BigIntegers, если 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, 99, 93]