Java Code for permutations of a list of numbers

Question

I have written a program to find all the possible permutations of a given list of items. This precisely means that my program prints all possible P(n,r) values for r=0 to n

Below is the code:

package com.algorithm;

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 Permutations<T> {
    public static void main(String args[]) {
        Permutations<Integer> obj = new Permutations<Integer>();
        Collection<Integer> input = new ArrayList<Integer>();
        input.add(1);
        input.add(2);
        input.add(3);

        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;
    }
}

Output

P(3,3) : Count (6) :- [[1, 2, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2], [2, 1, 3], [1, 3, 2]]
P(3,2) : Count (6) :- [[3, 1], [2, 1], [3, 2], [1, 3], [2, 3], [1, 2]]
P(3,1) : Count (3) :- [[3], [1], [2]]
P(3,0) : Count (1) :- [[]]

My problem is, as I go increasing the numbers in the input list. Running time increases and after 11 numbers in the input list, the program almost dies. Takes around 2 GB memory to run.

I am running this on a machine having 8GB RAM and i5 processor, so the speed and space is not a problem.

I would appreciate, if anyone can help me writing a more efficient code.

Solution 1

If you want all permutations of 15-ish or more elements, write them to disk or a db or something, since they won't fit in memory. Edit: Steinhaus–Johnson–Trotter algorithm. This is probably what you're looking for.

Solution 2

If you're not storing it -- if you're just iterating through it -- then consider using Heap's algorithm (#3 on http://www.cut-the-knot.org/do_you_know/AllPerm.shtml) -- or, just to make your life easier, use Guava's Collections2.permutations, which doesn't actually construct the whole list of permutations -- it walks through them on the fly. (Disclosure: I contribute to Guava.)

Solution 3

Java library of Google (Guava) has a utility method for this: Collections2#permutations(Collection)

Solution 4

You do realize that you are generating very large lists, and that running time will increase as the list length does. Have you determined how long the lists that are giving you trouble should be?

One thing that might help some would be to print each permutation as you find it, instead of gathering them all up into a list and THEN printing them. Of course, if the point is to actually store the whole list, and not just print them, that won't help.

View more solutions

Comments

[dharam]

Thanks for the response. Even in case where I print it the number of permutations generated for 10 number is of order 100000. Let's say I am not storing it, even in that case the order is not going to change. Moreover the problem with my code is that the recursion tree is one sided. If by some means I can find an algorithm which divides the input at each recursion into two equal parts and then find the permutations of the smaller lists and merge them at the end. Just wanted to know if anyone can refer me a book for advanced algorithms.

[dharam]

I believe what you said is true. The problem is not storage. The problem is running time. It's taking more than a minute for permutation of around 13 numbers.

[dharam]

The link is truly great. Even's speedup can help I guess. Thanks for the pointer. Would try and post it here