Recursive permutation of an array

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  permute (T[][] permutations, T[] array)
{
    if (permutations.length != factorial(array.length))
        throw new IllegalArgumentException();
    permute(permutations, array, 0, 0);
}
private static 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, 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 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];

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  permute (T[][] permutations, T[] array)
{
    if (permutations.length != factorial(array.length))
        throw new IllegalArgumentException();
    permute(permutations, array, 0, 0);
}

to

public static  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);
}

StackExchange Code Review Q#93434, answer score: 3