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



to

public static &lt;T&gt; 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);
}