I am trying to iterate over all possible combinations of integers with a given sum and size, in order to find the item with the lowest standard deviation.
For example, if sum=4 and the size=2 then these are all the possible combinations of integers:
[4,0], [3,1], [2,2], [1,3], [0,4]
I already have a recursive method in which 'remainingFacilities' is the sum and 'numberOfTransformers' is the size, and where all 'allPossibleFacilityCombinations' should contain all possible combinations:
private ArrayList<ArrayList<Integer>> allPossibleFacilityCombinations = new ArrayList<>();;
private void distributeFacilities(int remainingFacilities, int numberOfTransformers,
ArrayList<Integer> facilitiesPerTransformer, int currentIndex) {
if (currentIndex == numberOfTransformers) {
if (remainingFacilities == 0) {
// Create a new ArrayList based on facilitiesPerTransformer
ArrayList<Integer> copy = new ArrayList<>(facilitiesPerTransformer);
allPossibleFacilityCombinations.add(copy);
}
return;
}
for (int i = 0; i <= remainingFacilities; i++) {
facilitiesPerTransformer.add(i);
distributeFacilities(remainingFacilities - i, numberOfTransformers, facilitiesPerTransformer,
currentIndex + 1);
facilitiesPerTransformer.remove(facilitiesPerTransformer.size() - 1);
}
}
public static void main(String[] args) {
//some code where I get totalNumberOfFacilities and numberOfTransformers
ArrayList<Integer> facilitiesPerTransformer = new ArrayList<>();
mainInstance.distributeFacilities(remainingFacilities, numberOfTransformers, facilitiesPerTransformer, 0);
}
The problem with this method is it runs out of memory if the number of possible combinations is too large. I specifically need these inputs to work:
totalNumberOfFacilities: 213
numberOfTransformers: 6
In this case the total possible number of collections is 3917788308. The method runs out of memory before it even gets 1% of the results.
How can I find the optimum combination without running out of memory?
The OutOfMemory issue occurs because you are trying to store all the combinations in a list, before evaluating them. Instead, you should first generate partitions (combinations of addends that have a common sum). of the 'totalNumberOfFacilities' value. For each of those partitions generate all the permutations of it. For each permutation, immediatly evaluate it's fitness, and keep track of the best candidate only. This will eliminate the need to store partitions and/or permutations in a list.
There is a neat (recursive) algorithm (source, credits) to partition a number.
To find the distinct permutations efficiently you can use 'Pandita's algorithm' which keeps the characters in lexicographical order.
I also included an algorithm to find the standard deviation, although I am not sure this is exactly the evaluation function you mean, since the end result seems rather trivial.
The solution below does not store any of the partitions or permutations, but uses the visitor pattern to visit each value in turn. This avoids any memory issues.
import java.io.IOException;
import java.util.*;
import java.util.function.Consumer;
public class FixedSumPermutations {
private PermutationProcessor processor;
private long partitionCount;
private long permutationCount;
private class PermutationProcessor implements Consumer<int[]> {
private double bestScore;
private String bestPermutation;
@Override
public void accept(int[] permutation) {
double standardDeviation = calculateStandardDeviation(permutation);
if (bestPermutation == null || standardDeviation < bestScore) {
bestScore = standardDeviation;
bestPermutation = Arrays.toString(permutation);
System.out.printf("\rpartitions:%s permutations:%s %s", partitionCount, permutationCount, this);
}
}
@Override
public String toString() {
return String.format("bestPermutation:%s standardDeviation:%s", bestPermutation, bestScore);
}
public double calculateStandardDeviation(int[] array) {
double sum = 0.0;
for (int i : array) {
sum += i;
}
int length = array.length;
double mean = sum / length;
double standardDeviation = 0.0;
for (double num : array) {
standardDeviation += Math.pow(num - mean, 2);
}
return Math.sqrt(standardDeviation / length);
}
}
private void findPartitions(int targetSum, int size) {
processor = new PermutationProcessor();
partitionCount = 0;
permutationCount = 0;
findPartitions(size, targetSum, targetSum, new ArrayList<>());
}
private void findPartitions(int positions, int remaining, int max, List<Integer> result) {
if (remaining == 0) {
List<Integer> partition = new ArrayList<>(result);
while (partition.size() < positions) {
partition.add(0, 0);
}
partitionCount++;
findPermutations(partition);
return;
}
if (result.size() == positions) {
return;
}
for (int i = Math.min(max, remaining); i >= 1; i--) {
List<Integer> next = new ArrayList<>(result);
next.add(i);
findPartitions(positions, remaining - i, i, next);
}
}
private void findPermutations(List<Integer> value) {
int[] permutation = value.stream().mapToInt(i -> i).toArray();
Arrays.sort(permutation);
int changePos;
do {
processor.accept(permutation);
permutationCount++;
changePos = walkDown(permutation.length - 2, permutation);
if (changePos >= 0) {
int swapPos = walkUp(changePos + 1, permutation, changePos);
swap(permutation, changePos, swapPos);
for (int i = changePos + 1, j = permutation.length - 1; i < j; ++i, --j) {
swap(permutation, i, j);
}
}
} while (changePos >= 0);
}
private int walkUp(int swapPos, int[] chars, int changePos) {
while (swapPos + 1 < chars.length && chars[swapPos + 1] > chars[changePos]) {
++swapPos;
}
return swapPos;
}
private int walkDown(int changePos, int[] chars) {
while (changePos >= 0 && chars[changePos] >= chars[changePos + 1]) {
--changePos;
}
return changePos;
}
private void swap(int[] chars, int changePos, int swapPos) {
Integer temp = chars[changePos];
chars[changePos] = chars[swapPos];
chars[swapPos] = temp;
}
public static void main(String[] args) throws IOException {
FixedSumPermutations partitions = new FixedSumPermutations();
partitions.findPartitions(213, 6);
}
}
Output:
partitions:6444809 permutations:3917788288 bestPermutation:[35, 35, 35, 36, 36, 36] standardDeviation:0.5
Thanks to Konstantin Makarov for pointing out that we are looking for integers, not digits.