I am using this java code to try to calculate the permutations of 20: (this is just code part used for calculating permutation)
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);
but of course there is no enough memory for that;
any suggestions?
There would be 2432902008176640000 of those permutations. http://www.calculatorsoup.com/calculators/discretemathematics/permutations.php?n=20&r=20&action=solve
If you could output 100 000 of permutations per second it would take 2432902008176640000 / 100000 / 60 / 60 / 24 / 365 = 771468 years to do it
100M permutations per second would be faster and take just 771 years
The number of permutations of size 20 is 20 factorial, which turns out to be around 10^18. 8 gigabytes of ram are approximately 8 * 10^9 bytes, which as you might understand, is much below the amount of storage needed to store every possible permutations out of the 10^18.
Well the less memory approach will involve calculating a fixed but manageable number of permutations on demand. So, you will require a method like getNextPermutation().
I found the method from Collection2.java from Guava's source(the one that you are currently using in your code): https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/Collections2.java
You have,
@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));
}
You can call this compute next say 100 or 1000 times at once and store the results.
On your part, you will have to fork the source and modify calling of methods here and there a bit to make it as you want.