Recursive permutation of an array

Question

Basically, this is a recursive function to generate all of the permutations of an array.

The idea is this:

recursive case: start at the specified array index, and make a case for starting the next index (incremented one) for each of the indexes that come after the specified index by swapping the index with the next if not the same.

base case: the array has has no indexes greater than the current index. store the array, and increment the number of permutations found.

Here's what I thought would work:

public static void <T> permute (T[][] permutations, T[] array)
{
    if (permutations.length != factorial(array.length))
        throw new IllegalArgumentException();
    permute(permutations, array, 0, 0);
}
private static int <T> permute(
        T[][] permutations,
        T[] array,
        int midStart,
        int count) 
{
    if (midStart == array.length) 
    {
        permutations[count] = Arrays.copyOf(array, array.length);
        return count + 1;
    } 
    else 
    {
        for (int i = midStart; i < array.length; i++) 
        {
            T temp = array[i];
            array[i] = array[midStart];
            array[midStart] = temp;
            count = permute(permutations, array, midStart + 1, count);
        }
        return count;
    }
}

But this doesn't work because array being passed on the recursive call is being altered before the caller swaps the values again.

What's an efficient way to do this without needing to change it to something like so (without the extra space to store another array at each function call)?

private static <T> int permute(
        T[][] permutations,
        T[] array,
        int midStart,
        int count) 
{
    if (midStart == array.length) 
    {
        permutations[count] = Arrays.copyOf(array, array.length);
        return count + 1;
    } 
    else 
    {
        for (int i = midStart; i < array.length; i++) 
        {
            T temp = array[i];
            array[i] = array[midStart];
            array[midStart] = temp;
            count = permute(
                        permutations, 
                        Arrays.copyOf(array, array.length), 
                        midStart + 1, 
                        count);
        }
        return count;
    }
}

Answer 1

        permutations[count] = Arrays.copyOf(array, array.length);
        return count + 1;

Here you are copying the array into the permutations array after permuting the array itself. This is why you have to keep making copies of the array.

        return count;

If you instead do nothing in this case, you can change

    else 
    {
        for (int i = midStart; i < array.length; i++) 
        {
            T temp = array[i];
            array[i] = array[midStart];
            array[midStart] = temp;
            count = permute(permutations, array, midStart + 1, count);
        }
        return count;
    }

to copy the array before recursing instead.

        count = permute(permutations, array, midStart + 1, count);
        for (int i = midStart+1; i < array.length; i++) 
        {
            permutations[count] = Arrays.copyOf(array, array.length);
            permutations[count][i] = array[midStart];
            permutations[count][midStart] = array[i];
            count = permute(permutations, permutations[count], midStart + 1, count + 1);
        }

        return count;

Now you never change the original array and you don't have to do any extraneous copies. A side effect of this is that you don't need a temporary variable to do the swap either.

Note that I also changed the for loop not to do the no-op swap at the beginning. This was necessary since we don't want to copy in that case.

We're now one copy short, so change

public static void <T> permute (T[][] permutations, T[] array)
{
    if (permutations.length != factorial(array.length))
        throw new IllegalArgumentException();
    permute(permutations, array, 0, 0);
}

to

public static <T> void permute (T[][] permutations, T[] array)
{
    if (permutations.length != factorial(array.length)) {
        throw new IllegalArgumentException();
    }

    permutations[0] = Arrays.copyOf(array, array.length);
    permute(permutations, array, 0, 1);
}

Answer 2

Creating the Array

Rather than require a permutations array to be passed in with the correct length, I think it would be nicer if your permute function actually created the permutations array of the correct length and returned it.

End condition

The recursive end condition can be moved back by 1 element. A 1 element array doesn't need to recurse again:

if (midStart >= array.length - 1) 

Restoring the array

Instead of copying the array, all you have to do is to restore the array after recursing. In other words, you just need to swap back the item you just swapped, like this:

        for (int i = midStart; i < array.length; i++)
        {
            T temp = array[i];
            array[i] = array[midStart];
            array[midStart] = temp;
            count = permute(permutations, array, midStart + 1, count);
            // Swap back to restore array for caller.
            temp = array[i];
            array[i] = array[midStart];
            array[midStart] = temp;
        }