Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

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 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 it if anyone can help me write more efficient code.

share|improve this question
    
2  
You might want to write an Iterator class instead - your method fills up memory with every possible permutation - an iterator would only ever store one permutation at once, and find the next permutation from the previous every time you need it. Have a look at Wikipedia for some algorithms to do this. –  Eric May 8 '12 at 20:26
1  
Signed up just to comment. This is the only code on the internt that I can find to do nPr on anything besides strings. This saved me days of work. Thanks! I am using this code as the main piece in my brute-force exhaustive tree search. Like you were complaining about, the time it takes to perform my search blows up with anything larger than 10 entities. This is to be expected, as the number of possible permutations increase factorally. Good news though...if you solve this issue, you win a nobel prize. –  dberm22 Nov 1 '13 at 20:01
    
@dberm22 thanks for the Nobel prize though :) –  dharam Nov 1 '13 at 20:21

2 Answers 2

up vote 8 down vote accepted

The number of permutations typically increases factorially. Since 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5040, 8! = 40,320, 9! = 362,880, 10! = 3,628,800, 11! = 39,916,800, 12! = 479,001,600.

You can see that it get very large, very quickly. The output would be similarly huge.

The bottom line is, that past a certain point, there's just no way to keep the entire set in memory. A couple of numbers later, you wouldn't be able to afford a disk drive large enough to store it. A couple of number after that, there isn't enough paper on the planet to be able to print it. Somewhere in the 30's or 40's, there wouldn't be enough atoms in the entire universe to represent the results in an atomic scale computer.

share|improve this answer
    
Thank you sir. Does that mean the algorithm to find permutation does suffer a performance hit at larger magnitude and there is no much scope of improvement? –  dharam May 8 '12 at 17:57
    
Yes, that's exactly what it means. Sorry. –  Donald.McLean May 8 '12 at 19:07
private static void permute(char[] a, int n) {
    if (n == 1) {
        count++;
        System.out.println(a);
        return;
    }
    for (int i = 0; i < n; i++) {
        swap(a, i, n-1);
        permute(a, n-1);
        swap(a, i, n-1);
    }
}

This is an improved version which works using primitive data types so that memory used is in check.

share|improve this answer
1  
This is much less useful than the original code. You want to return the results, not just write them to the console. –  svick Jan 26 '13 at 20:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.