Tips implementing permutation algorithm in Java

As you know the number of permutations beforehand (it's N!) and also you want/have to return an int[][] I would go for an array directly. You can declare it right at the beginning with correct dimensions and return it at the end. Thus you don't have to worry about converting it afterwards at all.

Since you pretty much had it completed on your own in javascript, I'll go ahead and give you the Java code for implementing Steinhaus' permutation algorithm. I basically just ported your code to Java, leaving as much of it the same as I could, including comments.

I tested it up to N = 7. I tried to have it calculate N = 8, but it's been running for almost 10 minutes already on a 2 GHz Intel Core 2 Duo processor, and still going, lol.

I'm sure if you really worked at it you could speed this up significantly, but even then you're probably only going to be able to squeeze maybe a couple more N-values out of it, unless of course you have access to a supercomputer ;-).

Warning - this code is correct, NOT robust. If you need it robust, which you usually don't for homework assignments, then that would be an exercise left to you. I would also recommend implementing it using Java Collections, simply because it would be a great way to learn the in's and out's of the Collections API.

There's several "helper" methods included, including one to print a 2d array. Enjoy!

Update: N = 8 took 25 minutes, 38 seconds.

Edit: Fixed N == 1 and N == 2.

public class Test
{
  public static void main (String[] args)
  {
    printArray (allPermutations (8));
  }

  public static int[][] allPermutations (int N)
  {
    // base case
    if (N == 2)
    {
      return new int[][] {{1, 2}, {2, 1}};
    }
    else if (N > 2)
    {
      // start with all permutations of previous degree
      int[][] permutations = allPermutations (N - 1);

      for (int i = 0; i < factorial (N); i += N)
      {
        // copy each permutation N - 1 times
        for (int j = 0; j < N - 1; ++j)
        {
          // similar to javascript's array.splice
          permutations = insertRow (permutations, i, permutations [i]);
        }
      }

      // "weave" next number in
      for (int i = 0, j = N - 1, d = -1; i < permutations.length; ++i)
      {
        // insert number N at index j
        // similar to javascript's array.splice
        permutations = insertColumn (permutations, i, j, N);

        // 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 < 0 || j > N - 1)
        {
          d *= -1;
          j += d;
        }
      }

      return permutations;
    }
    else
    {
      throw new IllegalArgumentException ("N must be >= 2");
    }
  }

  private static void arrayDeepCopy (int[][] src, int srcRow, int[][] dest,
                                     int destRow, int numOfRows)
  {
    for (int row = 0; row < numOfRows; ++row)
    {
      System.arraycopy (src [srcRow + row], 0, dest [destRow + row], 0,
                        src[row].length);
    }
  }

  public static int factorial (int n)
  {
    return n == 1 ? 1 : n * factorial (n - 1);
  }

  private static int[][] insertColumn (int[][] src, int rowIndex,
                                       int columnIndex, int columnValue)
  {
    int[][] dest = new int[src.length][0];

    for (int i = 0; i < dest.length; ++i)
    {
      dest [i] = new int [src[i].length];
    }

    arrayDeepCopy (src, 0, dest, 0, src.length);

    int numOfColumns = src[rowIndex].length;

    int[] rowWithExtraColumn = new int [numOfColumns + 1];

    System.arraycopy (src [rowIndex], 0, rowWithExtraColumn, 0, columnIndex);

    System.arraycopy (src [rowIndex], columnIndex, rowWithExtraColumn,
                      columnIndex + 1, numOfColumns - columnIndex);

    rowWithExtraColumn [columnIndex] = columnValue;

    dest [rowIndex] = rowWithExtraColumn;

    return dest;
  }

  private static int[][] insertRow (int[][] src, int rowIndex,
                                    int[] rowElements)
  {
    int srcRows = src.length;
    int srcCols = rowElements.length;

    int[][] dest = new int [srcRows + 1][srcCols];

    arrayDeepCopy (src, 0, dest, 0, rowIndex);
    arrayDeepCopy (src, rowIndex, dest, rowIndex + 1, src.length - rowIndex);

    System.arraycopy (rowElements, 0, dest [rowIndex], 0, rowElements.length);

    return dest;
  }

  public static void printArray (int[][] array)
  {
    for (int row = 0; row < array.length; ++row)
    {
      for (int col = 0; col < array[row].length; ++col)
      {
        System.out.print (array [row][col] + " ");
      }

      System.out.print ("\n");
    }

    System.out.print ("\n");
  }
}

The java arrays are not mutable (in the sense, you cannot change their length). For direct translation of this recursive algorithm you probably want to use List interface (and probably LinkedList implementation as you want put numbers in the middle). That is List<List<Integer>>.

Beware the factorial grows rapidly: for N = 13, there is 13! permutations that is 6 227 020 800. But I guess you need to run it for only small values.

The algorithm above is quite complex, my solution would be:

• create List<int[]> to hold all permutations
• create one array of size N and fill it with identity ({1,2,3,...,N})
• program function that in place creates next permutation in lexicographical ordering
• repeat this until you get the identity again:
  • put a copy of the array at the end of the list
  • call the method to get next permutation.

If your program just needs to output all permutations, I would avoid to store them and just print them right away.

The algorithm to compute next permutation can be found on internet. Here for example

Use whatever you want, arrays or lists, but don't convert them - it just makes it harder. I can't tell what's better, probably I'd go for ArrayList<int[]>, since the outer List allows me to add the permutation easily and the inner array is good enough. That's just a matter of taste (but normally prefer lists, since they're much more flexible).