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;
}
}