title: Java Code for permutations of a list of numbers
body: <p>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</p>
  
  <p>Below is the code:
  <code></p>
  
  <pre><code>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;
      }
  }
  </code></pre>
  
  <p></code>   </p>
  
  <p><strong>Output</strong></p>
  
  <pre><code>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) :- [[]]
  </code></pre>
  
  <p>My problem is, as I go 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.</p>
  
  <p>I am running this on a machine having 8GB RAM and i5 processor, so the speed and space is not a problem. </p>
  
  <p>I would appreciate, if anyone can help me writing a more efficient code.</p>