Optimized Permutation Code in Java

Question

This is a code that I got from internet.

import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Test<T> {
    public static void main(String args[]) {
        Test<Integer> obj = new Test<Integer>();
        Collection<Integer> input = new ArrayList<Integer>();
        for (int i = 0; i < 14; i++) {
                       input.add(i);

        }

        Collection<List<Integer>> output = obj.permute(input);
        int k = 0;
        Set<List<Integer>> pnr = null;
        for (int i = 0; i <= input.size(); i++)
        {
            pnr = new HashSet<List<Integer>>();
            for(List<Integer> integers : output){
            pnr.add(integers.subList(i, integers.size()));
            }
            k = input.size()- i;
            System.out.println("P("+input.size()+","+k+") :"+ 
            "Count ("+pnr.size()+") :- "+pnr);
        }
    }
    public Collection<List<T>> permute(Collection<T> input) {
        Collection<List<T>> output = new ArrayList<List<T>>();
        if (input.isEmpty()) {
            output.add(new ArrayList<T>());
            return output;
        }
        List<T> list = new ArrayList<T>(input);
        T head = list.get(0);
        List<T> rest = list.subList(1, list.size());
        for (List<T> permutations : permute(rest)) {
            List<List<T>> subLists = new ArrayList<List<T>>();
            for (int i = 0; i <= permutations.size(); i++) {
                List<T> subList = new ArrayList<T>();
                subList.addAll(permutations);
                subList.add(i, head);
                subLists.add(subList);
            }
            output.addAll(subLists);
        }
        return output;
    }
}

When I tried executing it, it took long time for the elements of count 7. But when I tried for 14, I got below exception.

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:2219)
    at java.util.ArrayList.toArray(ArrayList.java:329)
    at java.util.ArrayList.addAll(ArrayList.java:530)
    at Test.permute(Test.java:45)
    at Test.permute(Test.java:41)
    at Test.permute(Test.java:41)
    at Test.permute(Test.java:41)
    at Test.main(Test.java:18)
Java Result: 1

My system configuration is 3rd Gen i5, 8GB RAM. While the program was running, CPU consumption was 98-100%.

So my question is:

Is there any jar available for doing permutation efficiently?
What can I do in this code to improve the performance?

My requirement:

Need to permute a group (ie, more than 30) of integer values.

Downvoters please comment reason

Could you please be a little more specific with your problem statement? What is it you're permuting? — , Apr 24 '13 at 07:23

score 3 · Accepted Answer · answered Apr 24 '13 at 07:27

3

Instead of generating all permutations first (as this has an exponentially growing amount of memory required) I suggest you process each permutation as you generate it. This means you only need to store one combination at a time.

You can generate all permutations of size 1 (or zero if that is allowed) and grow up to all permutations of all sizes.

Note: for your output you only need to calculate the number you would generate, you don't have to actually generate them.

answered Apr 24 '13 at 07:27

Peter Lawrey

525,659
79
751
1,130

So editing this code will be enough? Is there any jars available for doing permutation efficiently? – Maximin Apr 24 '13 at 07:35
There could be, but given this is just an exercise I suspect you learn more by doing it yourself. It's just a few lines of code. – Peter Lawrey Apr 24 '13 at 07:39

score 1 · Answer 2 · edited May 23 '17 at 12:28

1

You could increase the heap size a little: in Eclipse, or from the command line.

However, if you want all permutations of 30 elements, you'll need 30! * 30 * 4 bytes of memory, which is 3e+22 TB...

edited May 23 '17 at 12:28

Community

1
1

answered Apr 24 '13 at 07:28

Vincent van der Weele

12,927
1
33
61

score 0 · Answer 3 · answered Apr 24 '13 at 07:51

I think maybe there is a point being missed here. You keep asking if there is a more 'efficient' or 'optimized' way to find all permutations of a set of numbers.

The number of possible permutations for 30 integers is a number with approximately 32 digits. One gigabyte of ram is a number of bytes with 10 digits. If you are talking about storing ALL the answers to this problem in memory at once, it is conceivable that you could not do this even if you literally had all the RAM in the entire world.

Peter's answer recognizes this in stating that while it is impossible to store the entire solution for >30 numbers, (never mind the time to calculate this), it IS possible to calculate a portion of the answer and generate more as needed.

score 0 · Answer 4 · edited May 09 '18 at 00:41

This will work for what you are doing. However I can't see a way of reducing the method to reduce processing. So this is about as efficient as you can get it.

public static ArrayList<Integer> calPermutations (ArrayList<ArrayList<Integer>> n) {
    if (n.size() <= 0 || n == null) {
        return null;
    }
    ArrayList<Integer> Result = new ArrayList<Integer>();
    for (int i = 0; i < n.size(); i++) {
        Integer num = n.get(i).get(0);
        for (int x = 1; x < n.get(i).size(); x++) {
            num *= n.get(i).get(x);
        }
        Result.add(num);
    }
    return Result;
}

However if the Java heap space error continues in Eclipse you can go to:

Run->Run Configurations->Arguments

Go to VM arguments and try:

-Xmx2048M

If this is too large for your RAM just decrease the numbers until you can find something that suits. More information here.

Optimized Permutation Code in Java

4 Answers4