Перестановка без повторения основана на теореме, что количество результатов является факториалом количества элементов (в данном случае чисел). В вашем случае 10! равно 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. Доказательство того, что оно совершенно верно, является правильным решением и для генерации.
Ну так как. В первой позиции, т.е. слева, вы можете иметь 10 цифр, во второй позиции вы можете иметь только 9 цифр, потому что одна цифра находится в позиции слева, и мы не можем повторить ту же цифру и т. Д. (Доказательство выполняется с помощью математической индукции. ).
Итак, как получить первые десять результатов? Согласно моим знаниям, он проще всего использует циклический сдвиг. Это означает порядок смещения числа влево на одну позицию (или вправо, если хотите) и число, которое переполняется, чтобы поставить на пустое место.
Это означает для первых десяти результатов:
10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1 10
8 7 6 5 4 3 2 1 10 9
7 6 5 4 3 2 1 10 9 8
6 5 4 3 2 1 10 9 8 7
5 4 3 2 1 10 9 8 7 6
...
Первая строка - это базовый образец, поэтому рекомендуется создать его перед началом генерации. Преимущество заключается в том, что на следующем шаге вам придется решить ту же проблему, чтобы избежать нежелательных дубликатов.
На следующем шаге рекурсивно вращайте только 10-1 числа 10-1 раз и т. Д.
Это означает для первых 9 результатов на втором шаге:
10 9 8 7 6 5 4 3 2 1
10 8 7 6 5 4 3 2 1 9
10 7 6 5 4 3 2 1 9 8
10 6 5 4 3 2 1 9 8 7
10 5 4 3 2 1 9 8 7 6
...
и т. Д. Обратите внимание, что первая строка присутствует на предыдущем шаге, поэтому ее нельзя добавлять в сгенерированный набор снова.
Алгоритм рекурсивно делает именно то, что объяснено выше. Можно сгенерировать все 3628800 комбинаций для 10 !, потому что количество вложений совпадает с количеством элементов в массиве (это означает, что в вашем случае для 10 чисел на моем компьютере оно задерживается на 5 минут), и вам нужно иметь достаточно памяти если вы хотите сохранить все комбинации в массиве.
Есть решение.
package permutation;
/** Class for generation amount of combinations (factorial)
* !!! this is generate proper permutations without repeating and proper amount (počet) of rows !!!
*
* @author hariprasad
*/
public class TestForPermutationII {
private static final String BUMPER = "*";
private static int counter = 0;
private static int sumsum = 0;
// definitoin of array for generation
//int[] testsimple = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int[] testsimple = {1, 2, 3, 4, 5};
private int ELEMNUM = testsimple.length;
int[][] shuff;
private String gaps(int len) {
String addGap = "";
for(int i=0; i <len; i++)
addGap += " ";
return addGap;
}
/** Factorial computing */
private int fact(int num) {
if (num > 1) {
return num * fact(num - 1);
} else {
return 1;
}
}
/** Cyclic shift position to the left */
private int[] lShiftPos(int[] arr, int pos) {
int[] work = new int[ELEMNUM];
int offset = -1;
for (int jj = 0; jj < arr.length; jj++) {
if (jj < pos) {
work[jj] = arr[jj];
} else if (jj <= arr.length - 1) {
if (jj == pos) {
offset = arr[pos]; // last element
}
if (jj != (arr.length - 1)) {
work[jj] = arr[jj + 1];
} else {
work[jj] = offset;
}
}
}
return work;
}
private String printBuff(int[] buffer) {
String res = "";
for (int i= 0; i < buffer.length; i++) {
if (i == 0)
res += buffer[i];
else
res += ", " + buffer[i];
}
return res;
};
/** Recursive generator for arbitrary length of array */
private String permutationGenerator(int pos, int level) {
String ret = BUMPER;
int templen = counter;
int[] work = new int[ELEMNUM];
int locsumread = 0;
int locsumnew = 0;
//System.out.println("\nCalled level: " + level);
for (int i = 0; i <= templen; i++) {
work = shuff[i];
sumsum++;
locsumread++;
for (int ii = 0; ii < pos; ii++) {
counter++;
sumsum++;
locsumnew++;
work = lShiftPos(work, level); // deep copy
shuff[counter] = work;
}
}
System.out.println("locsumread, locsumnew: " + locsumread + ", " + locsumnew);
// if level == ELEMNUM-2, it means no another shift
if (level < ELEMNUM-2) {
ret = permutationGenerator(pos-1, level+1);
ret = "Level " + level + " end.";
//System.out.println(ret);
}
return ret;
}
public static void main(String[] argv) {
TestForPermutationII test = new TestForPermutationII();
counter = 0;
int len = test.testsimple.length;
int[] work = new int[len];
test.shuff = new int[test.fact(len)][];
//initial
test.shuff[counter] = test.testsimple;
work = test.testsimple; // shalow copy
test.shuff = new int[test.fact(len)][];
counter = 0;
test.shuff[counter] = test.testsimple;
test.permutationGenerator(len-1, 0);
for (int i = 0; i <= counter; i++) {
System.out.println(test.printBuff(test.shuff[i]));
}
System.out.println("Counter, cycles: " + counter + ", " + sumsum);
}
}
Интенсивность (число циклов) алгоритма - это сумма неполных факториалов числа членов. Таким образом, при повторном чтении частичного набора возникает свес, чтобы создать следующее подмножество, поэтому интенсивность равна:
п! + n! / 2! + n! / 3! + ... + n! / (n-2)! + n! (n-1)!