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.

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

        Collection&lt;List&lt;Integer&gt;&gt; output = obj.permute(input);
        int k = 0;
        Set&lt;List&lt;Integer&gt;&gt; pnr = null;
        for (int i = 0; i &lt;= input.size(); i++) {
            pnr = new HashSet&lt;List&lt;Integer&gt;&gt;();
            for(List&lt;Integer&gt; 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&lt;List&lt;T&gt;&gt; permute(Collection&lt;T&gt; input) {
        Collection&lt;List&lt;T&gt;&gt; output = new ArrayList&lt;List&lt;T&gt;&gt;();
        if (input.isEmpty()) {
            output.add(new ArrayList&lt;T&gt;());
            return output;
        }
        List&lt;T&gt; list = new ArrayList&lt;T&gt;(input);
        T head = list.get(0);
        List&lt;T&gt; rest = list.subList(1, list.size());
        for (List&lt;T&gt; permutations : permute(rest)) {
            List&lt;List&lt;T&gt;&gt; subLists = new ArrayList&lt;List&lt;T&gt;&gt;();
            for (int i = 0; i &lt;= permutations.size(); i++) {
                List&lt;T&gt; subList = new ArrayList&lt;T&gt;();
                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.
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.