Estoy usando este código Java para tratar de calcular las permutaciones de 20: (esto es solo una parte del código que se usa para calcular la permutación)
int[] myArray = new int[20]; for (int i = 0; i < a; i++) myArray[i] = i + 1; List<Integer> intList = new ArrayList<Integer>(); for (int index = 0; index < myArray.length; index++) { intList.add(myArray[index]); } List<Integer> vals = intList; Collection<List<Integer>> orderPerm = Collections2.permutations(vals);pero, por supuesto, no hay suficiente memoria para eso;
¿alguna sugerencia?
Habría 2432902008176640000 de esas permutaciones. http://www.calculatorsoup.com/calculators/discretemathematics/permutations.php?n=20&r=20&action=solve
Si pudiera producir 100 000 permutaciones por segundo, tardaría 2432902008176640000/100000/60/60/24/365 = 771468 años en hacerlo
100 millones de permutaciones por segundo sería más rápido y tomaría solo 771 años
El número de permutaciones de tamaño 20 es 20 factorial, que resulta ser alrededor de 10^18. 8 gigabytes de RAM son aproximadamente 8 * 10 ^ 9 bytes, lo que, como puede comprender, está muy por debajo de la cantidad de almacenamiento necesaria para almacenar todas las permutaciones posibles de los 10 ^ 18.
Bueno, el enfoque de menos memoria implicará calcular un número fijo pero manejable de permutaciones bajo demanda. Por lo tanto, necesitará un método como getNextPermutation().
Encontré el método de Collection2.java de la fuente de Guava (la que está usando actualmente en su código): https://github.com/google/guava/blob/master/guava/src/com/google/common/ recoger/Colecciones2.java
Tú tienes,
@Override protected List<E> computeNext() { if (nextPermutation == null) { return endOfData(); } ImmutableList<E> next = ImmutableList.copyOf(nextPermutation); calculateNextPermutation(); return next; } void calculateNextPermutation() { int j = findNextJ(); if (j == -1) { nextPermutation = null; return; } int l = findNextL(j); Collections.swap(nextPermutation, j, l); int n = nextPermutation.size(); Collections.reverse(nextPermutation.subList(j + 1, n)); }Puede llamar a este cálculo a continuación, digamos 100 o 1000 veces a la vez y almacenar los resultados.
Por su parte, tendrá que bifurcar la fuente y modificar un poco la llamada de los métodos aquí y allá para que quede como desee.