In this answer I will walk through how I solved this problem to find an algorithm that works for an array of any length for words which can be any length and are not required to all be the same length.
I will first make a recursive solution, and then transorm it into an iterative one.
The easiest way to answer problems like this is to think of them recursively:
Generating all permutations of [] should return [""]
Generating all permutations of a non-empty list means, for each letter c in the first word in the list, return all permutations of the rest of the list with c prepended on the front.
This can be written in Java as follows:
public static List<String> generatePermutationsRecursiveSlow(String[] words) {
if (words.length == 0)
// base case
return Collections.singletonList("");
else {
// recursive case
// result list
ArrayList<String> permutations = new ArrayList<>();
// split array into item 0 and items [1..end]
String firstWord = words[0];
String[] otherWords = new String[words.length - 1];
System.arraycopy(words, 1, otherWords, 0, words.length - 1);
// recurse to find permutations for items [1..end]
List<String> otherWordsPermutations = generatePermutationsRecursiveSlow(otherWords);
// for each character in the first word
for (char c : firstWord.toCharArray()) {
// for each permutation from the recursive call's results
for (String otherWordsPermutation : otherWordsPermutations) {
// prepend this character onto the permutation and add it to the results
permutations.add(c + otherWordsPermutation);
}
}
return permutations;
}
}
- Calling
generatePermutationsRecursiveSlow(new String[0]) returns [""].
- Calling
generatePermutationsRecursiveSlow(new String[]{"cd"}) will cause the local c variable to be equal to 'c', and it will recurse with an empty array as the argument, making otherWordsPermutations equal to [""], so it will add 'c' + "" (which is "c") to the results, then it will do the same for 'd', adding "d" to the results.
- Calling
generatePermutationsRecursiveSlow(new String[]{"ab", "cd"}) will mean that when c is 'a', it will add to the results list 'a'+"c", then 'a'+"d", and whencis'b', it will add'b'+"c"and'b'+"d"`
A similar but better optimised version which works in the same way can be written like this:
public static List<String> generatePermutationsRecursive(String[] words) {
ArrayList<String> permutations = new ArrayList<>();
int wordLen = words.length;
generatePermutationsRecursive(words, permutations, new char[wordLen], 0);
return permutations;
}
public static void generatePermutationsRecursive(String[] words, ArrayList<String> permutations, char[] word, int i) {
if (i == word.length) {
// base case
permutations.add(new String(word));
} else {
for (int j = 0; j < words[i].length(); j++) {
// equivalent of prepending
word[i] = words[i].charAt(j);
// recurse
generatePermutationsRecursive(words, permutations, word, i + 1);
}
}
}
This is better optimised since it uses the word parameter to avoid the O(n) prepending to the string by instead modifying a character array. It also introduces the parameter i which is the effective start index of the array, making it possible to avoid copying parts of the input array.
This can be transformed into an iterative approach by tracking the variables that change between different recursive calls using a stack (in place of the call stack):
private static List<String> generatePermutationsIterative(String[] words) {
// in the recursive version, each recursive function call would have its own local copy of `i` and `j`
// simulate that here with 2 stacks
ArrayDeque<Integer> i_stack = new ArrayDeque<>(words.length);
ArrayDeque<Integer> j_stack = new ArrayDeque<>(words.length);
i_stack.add(0);
j_stack.add(0);
char[] word = new char[words.length];
ArrayList<String> permutations = new ArrayList<>();
while (!i_stack.isEmpty()) {
int i = i_stack.removeLast();
int j = j_stack.removeLast();
if (i == words.length) {
// base case
permutations.add(new String(word));
continue;
}
if (!(j < words[i].length())) {
// reached end of loop `for (int j = 0; j < words[i].length(); j++)`
continue;
}
// if not reached end of loop `for (int j = 0; j < words[i].length(); j++)` yet,
// then increment `j` and allow next iteration to happen
i_stack.add(i);
j_stack.add(j + 1);
word[i] = words[i].charAt(j);
// recurse
i_stack.add(i + 1);
j_stack.add(0);
}
return permutations;
}
Code here
As a sidenote, look how cool Haskell is with this 2-line solution to the problem here (admittedly its not iterative, but it should have tail-call optimisation, making it as fast as an iterative solution).
