CODEWITHSUNDEEP
javaalgorithmoptimizationpermutation
dharam
dharam

Reputation: 8106

Java Code for permutations of a list of numbers

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.

Upvotes: 8

Views: 37624

Answers (4)

Kees van Dieren
Kees van Dieren

Reputation: 1290

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

Upvotes: 7

Louis Wasserman
Louis Wasserman

Reputation: 198491

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.)

Upvotes: 16

Buhb
Buhb

Reputation: 7149

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.

Upvotes: 8

Scott Hunter
Scott Hunter

Reputation: 49920

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.

Upvotes: 2

Related Questions