title: Tips implementing permutation algorithm in Java
body: <p>As part of a school project, I need to write a function that will take an integer N and return a two-dimensional array of every permutation of the array {0, 1, ..., N-1}. The declaration would look like public static int[][] permutations(int N).</p>
  
  <p>The algorithm described at <a href="http://www.usna.edu/Users/math/wdj/book/node156.html" rel="nofollow">http://www.usna.edu/Users/math/wdj/book/node156.html</a> is how I've decided to implement this.</p>
  
  <p>I wrestled for quite a while with arrays and arrays of ArrayLists and ArrayLists of ArrayLists, but so far I've been frustrated, especially trying to convert a 2d ArrayList to a 2d array.</p>
  
  <p>So I wrote it in javascript. This works:</p>
  
  <pre><code>function allPermutations(N) {
      // base case
      if (N == 2) return [[0,1], [1,0]];
      else {
          // start with all permutations of previous degree
          var permutations = allPermutations(N-1);
  
          // copy each permutation N times
          for (var i = permutations.length*N-1; i &gt;= 0; i--) {
              if (i % N == 0) continue;
              permutations.splice(Math.floor(i/N), 0, permutations[Math.floor(i/N)].slice(0));
          }
  
          // "weave" next number in
          for (var i = 0, j = N-1, d = -1; i &lt; permutations.length; i++) {
              // insert number N-1 at index j
              permutations[i].splice(j, 0, N-1);
  
              // index j is  N-1, N-2, N-3, ... , 1, 0; then 0, 1, 2, ... N-1; then N-1, N-2, etc.
              j += d;
              // at beginning or end of the row, switch weave direction
              if (j &lt; 0 || j &gt;= N) {
                  d *= -1;
                  j += d;
              }
          }
          return permutations;
      }
  }
  </code></pre>
  
  <p>So what's the best strategy to port that to Java? Can I do it with just primitive arrays? Do I need an array of ArrayLists? Or an ArrayList of ArrayLists? Or is there some other data type that's better? Whatever I use, I need to be able to convert it back into a an array of primitive arrays.</p>
  
  <p>Maybe's there a better algorithm that would simplify this for me...</p>
  
  <p>Thank you in advance for your advice!</p>