8
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ codereview.stackexchange.com/a/6991/9390 \$\endgroup\$
    – Adam
    Commented May 8, 2012 at 18:23
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Eric
    Commented May 8, 2012 at 20:26
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – dberm22
    Commented Nov 1, 2013 at 20:01
  • \$\begingroup\$ @dberm22 thanks for the Nobel prize though :) \$\endgroup\$
    – dharam
    Commented Nov 1, 2013 at 20:21
  • 1
    \$\begingroup\$ 2 years later, and I just published a github repo with a whole bunch of different search algorithms for solving bipartite graphs. github.com/dberm22/Bipartite-Solver . This entire project started with just your code, so I wanted to thank you again. If you take a close look, you can still see most of the original code (a bit tweaked) here: github.com/dberm22/Bipartite-Solver/blob/master/src/com/dberm22/… \$\endgroup\$
    – dberm22
    Commented Apr 17, 2015 at 3:51

2 Answers 2

11
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$
    – dharam
    Commented May 8, 2012 at 17:57
  • \$\begingroup\$ Yes, that's exactly what it means. Sorry. \$\endgroup\$ Commented May 8, 2012 at 19:07
  • \$\begingroup\$ ... and factorial growth is less then exponential growth ... like a certain Corona-Virus ... \$\endgroup\$ Commented Apr 14, 2021 at 9:48
2
\$\begingroup\$
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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is much less useful than the original code. You want to return the results, not just write them to the console. \$\endgroup\$
    – svick
    Commented Jan 26, 2013 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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