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>();

        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.add(i, head);
        return output;

P(3,3) : Count (6) :- [[1, 2, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2], [2, 1, 3], [1, 3,  
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
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
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
No problem. I was trying to make modifications to compute nPr directly (without having to compute ALL permutations and then extract only the ones I'm interested in afterwards), but with the recursive nature of your class, I can't seem to figure out how I would do that without screwing up more stuff. In other words, if I have 10 objects and I'm only interested in 10P5, I don't want to calculate 10P10, 10P9, 10P8 .... just so that I can then take only the 10P5 sublist. I know that is not the point of your class/post, but it would be a huge help for the rest of us. Still, great job! Thanks again. –  dberm22 Nov 20 '13 at 13:08

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


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.