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

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

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.

StackExchange Code Review Q#11598, answer score: 11