Приведенные n и k, возвращаем k-ю последовательность перестановок

Question

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

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

1. "123"
2. "132"
3. «213 "
4. "231"
5. "312"
6. "321" Учитывая, п и к, возвращают последовательность KTH перестановки.

Например, если n = 3, k = 4, ans = "231".

Существует несколько решений. Но все они используют либо факториал, либо сложность больше O (n), такая как O (n!). Если вы используете факториал и находите число в позиции через k/(n-1) !, тогда проблема возникает, когда n велико (n = 100). Здесь при больших n (n-1)! переполняется и становится 0. В результате я получаю деление на нулевую ошибку ... любое решение или алгоритм для этого?

Вот мой код:

public class KthPermutation { 
    public String getPermutation(int n, int k) { 
     // initialize all numbers 
     ArrayList<Integer> numberList = new ArrayList<Integer>(); 

     for (int i = 1; i <= n; i++) { 
      numberList.add(i); 
     } 
     int fact = 1; // set factorial of n-1 

     for (int i = 1; i <= n-1; i++) { 
      fact = fact * i; 
     } 

     if ((long) k > (long) fact * n) { 
      k = (int) ((long) k - (long) (fact * n)); 
     } 
     k--; // set k to base 0 

     StringBuilder result = new StringBuilder(); 
     result = getP(result, numberList, n, k, fact); 
     return result.toString(); 
    } 
    public static StringBuilder getP(StringBuilder result, 
       ArrayList<Integer> numberList, int n, int k, int fact) {  
     if (numberList.size() == 1 || n == 1) { 
      result.append(numberList.get(0)); 
      return result; // return condition 
     } 
     int number = (k/fact) + 1 ; 
     result.append(numberList.get(number - 1)); 
     numberList.remove(number - 1); 
     k = k % fact; // update k 
     fact = fact/(n - 1); 
     n--; 
     return getP(result, numberList, n, k, fact); 
    } 
} 

Answer 1

Так что, если я правильно читал этот вопрос, вы хотите найти -ю перестановку, предпочтительно без использования BigIntegers, при условии, к не достаточно большой, чтобы требуют 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.

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

код (к начинается с 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)); 
} 

Demo

выхода:

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

десятимиллионной перестановка при п = 100 :

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 2 2, 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]

Answer 2

крупнозерни существует необходимость bigints с таким интерфейсом

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

100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 

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

2^32=   4294967296 
2^64=18446744073709551616 

см Fast exact bigint factorial

если вы изменить интерфейс немного вы вдруг не нужны никакие bigints больше

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

• Generalized Permutation (without repetitions) in C++

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