(Java) Permutation of N Lists with flushing to Disk

Question

I'm referring to this question/answer: Permutation of N Lists (permutation of N lists to create all combinations of a search space). I implemented this for my case but having the problem to run out of memory as I work with a huge search space (currently millions or billions of combinations, increasing). This is my current code:

private void permute(List<List<T>> listOfLists, int index, Deque<T> tokens, boolean inMemory) {
    if (index == listOfLists.size()) {
        List<T> output = new LinkedList<>();
        for (T item : tokens) {
            output.add(item);
        }
        if (inMemory)
            results.add(output);
        else
            writeToDisk(output);

    } else {
        List<T> types = listOfLists.get(index);
        for (T l : types) {
            tokens.addLast(l);
            permute(listOfLists, index + 1, tokens, inMemory);
            tokens.removeLast();
        }
    }
}

Where 'T' in my case is an Enum like

public enum LinkType implements Permutable { // Permutable -> Serializable Marker
    L1(0.95f, 20), L2(0.85f, 12), L3(0.75f, 8);

    protected final float reliability;
    protected final int cost;

    private LinkType(float reliability, int cost) {
        this.reliability = reliability;
        this.cost = cost;
    }

    public float getReliability() {
        return reliability;
    }

    public int getCost() {
         return cost;
    }
}

My current problem is that the objects get written to disk but still reside in memory as it is necessary for the recursion. Any ideas to solve this problem? Increasing heap size is not a (permanent) solution as search space in my applications will definitely increase over time. Thank you very much for your help!

Edit: I know that I will never reach values above ~25 but I do not want to stuck already at 10!

Answer 1

If you don't want to store all permutations, but only to have possibility to iterate over all permutations, then you can expand the recursion. Consider the following class which implements Iterator<int[]> interface:

public class IntPermutationsGenerator implements Iterator<int[]> {
    final int[] permutation;
    private boolean onFirst = true;
    private final int size;

    public IntPermutationsGenerator(int dimension) {
        permutation = new int[dimension];
        for (int i = 0; i < dimension; ++i)
            permutation[i] = i;
        this.size = dimension;
    }


    @Override
    public boolean hasNext() {
        return !isLast() || onFirst;
    }

    private boolean isLast() {
        for (int i = 0; i < size; i++)
            if (permutation[i] != size - 1 - i)
                return false;
        return true;
    }


    @Override
    public int[] next() {
        if (onFirst) {
            onFirst = false;
            return permutation;
        }
        final int end = size - 1;
        int p = end, low, high, med, s;
        while ((p > 0) && (permutation[p] < permutation[p - 1]))
            p--;
        if (p > 0) //if p==0 then it's the last one
        {
            s = permutation[p - 1];
            if (permutation[end] > s)
                low = end;
            else {
                high = end;
                low = p;
                while (high > low + 1) {
                    med = (high + low) >> 1;
                    if (permutation[med] < s)
                        high = med;
                    else
                        low = med;
                }
            }
            permutation[p - 1] = permutation[low];
            permutation[low] = s;
        }
        high = end;
        while (high > p) {
            med = permutation[high];
            permutation[high] = permutation[p];
            permutation[p] = med;
            p++;
            high--;
        }
        return permutation;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported yet.");
    }
}

This class allows to iterate over all permutations without storing them:

public void main(String[] args) throws Exception {
    IntPermutationsGenerator g = new IntPermutationsGenerator(3);
    while (g.hasNext()){
        System.out.println(Arrays.toString(g.next()));
    }

    //gives
    //[0, 1, 2]
    //[0, 2, 1]
    //[1, 0, 2]
    //[1, 2, 0]
    //[2, 0, 1]
    //[2, 1, 0]
}

In the above code each subsequent permutation will be generated on the invocation of next() while all other permutations will not be stored. Having such iterator you can just apply int[] permutation to your array or list of objects.

You also can find the implementation of such iterator in redberry-core package which available from Maven Central (see IntPermutationsGenerator).

The algorithm implemented in next() generates permutations in lexicographic order. You can read more about this algorithm for example here.

Answer 2

This is my solution based on this Answer of Stanislav Poslavsky. I used an Iterator to iterate over a domain for specific places of the permutation. I added, just for clarification, an int[] with the maximum values (borders) at a specific place. I count up until I reach the limit for certain border, then I continue with the next place.

public class IntegerDomainPermutation implements Iterator<int[]> {
private int[] permutation;
private int[] domainBorders;
private List<List<Integer>> domain;
private boolean hasNext = true;

public IntegerDomainPermutation(List<List<Integer>> domain) {
    this.domain = domain;
    permutation = new int[domain.size()];
    domainBorders = new int[domain.size()];

    for (int i = 0; i < domain.size(); i++) {
        domainBorders[i] = domain.get(i).get(domain.get(i).size() - 1);
    }
    for (int i = 0; i < domain.size(); i++) {
        permutation[i] = domain.get(i).get(0);
    }
}

@Override
public boolean hasNext() {
    return hasNext;
}

@Override
public int[] next() {
    int[] perm = Arrays.copyOf(permutation, permutation.length);
    if(checkNext()){
        hasNext = true;
        increment();
    }else{
        hasNext = false;
    }
    return perm;
}

@Override
public void remove() {
    throw new UnsupportedOperationException("Not supported yet.");
}

public boolean checkNext(){
    for (int i = permutation.length - 1; i >= 0; i--) {
        if (!(permutation[i] == domainBorders[i])) {
            return true;
        }
    }
    return false;
}

private void increment() {
    for (int i = permutation.length - 1; i >= 0; i--) {
        if (!(permutation[i] == domainBorders[i])) {
            permutation[i] = domain.get(i).get(domain.get(i).indexOf(permutation[i]) + 1);
            return;
        } else {
            permutation[i] = domain.get(i).get(0);
        }
    }
}

}

In the end, one can use the code like this:

public static void main(String[] args) {
    List<List<Integer>> domain = new LinkedList<>();
    List<Integer> place0 = new LinkedList<>(Arrays.asList(1,2));
    List<Integer> place1 = new LinkedList<>(Arrays.asList(3,7));
    List<Integer> place2 = new LinkedList<>(Arrays.asList(5,2));
    domain.add(place0);
    domain.add(place1);
    domain.add(place2);
    IntegerDomainPermutation perm = new IntegerDomainPermutation(domain);
    while(perm.hasNext())
        System.out.println(Arrays.toString(perm.next()));
}

Which leads to the following output:

[1, 3, 5]
[1, 3, 2]
[1, 7, 5]
[1, 7, 2]
[2, 3, 5]
[2, 3, 2]
[2, 7, 5]
[2, 7, 2]

There is, of course, space for improvement like error handling, replace the java.util.Lists with an appropriate type (e.g. Sets or Arrays) or dynamic types, but this code already does what I expect. Thank you very much for your help!