В этом ответе я расскажу, как я решил эту проблему, чтобы найти алгоритм, который работает для массива любой длины для слов, которые могут быть любой длины и не обязательно должны быть одинаковой длины.
Сначала я сделаю рекурсивное решение, а затем преобразовываю его в итеративное.
Самый простой способ ответить на подобные проблемы - подумать о них рекурсивно:
Генерация всех перестановок [] должна вернуть [""] Генерация всех перестановок непустого списка означает, для каждой буквы c в первом слове в списке вернуть все перестановки в остальной части списка с добавлением c впереди.
Это можно записать в Java следующим образом:
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;
}
}
- Вызов
generatePermutationsRecursiveSlow(new String[0]) возвращает [""]. - Вызов
generatePermutationsRecursiveSlow(new String[]{"cd"}) приведет к тому, что локальная переменная c будет равна 'c', и она будет рекурсивна с пустым массивом в качестве аргумента, что делает otherWordsPermutations равным [""], поэтому он добавит 'c' + "" (что составляет "c") к результатам, затем он сделает то же самое для 'd', добавив "d" к результатам. - Вызов
generatePermutationsRecursiveSlow(new String[]{"ab", "cd"}) будет означать, что когда c равно 'a', он добавит в список результатов 'a'+"c", затем 'a'+"d", and whencis 'b ', it will add' b '+ "c" and' b '+ "d" `
Аналогичная, но лучше оптимизированная версия, которая работает в таким же образом можно записать так:
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);
}
}
}
Это лучше оптимизировать, поскольку он использует параметр word, чтобы избежать добавления O(n) к строке, вместо этого изменяя массив символов. Он также вводит параметр i, который является эффективным начальным индексом массива, что позволяет избежать копирования частей входного массива.
Это можно преобразовать в итерационный подход, отслеживая переменные, которые изменяются между различными рекурсивными вызовами с использованием стека (вместо стека вызовов):
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;
}
Код здесь
В качестве примечания, посмотрите, насколько круто Haskell с этим двухстрочным решением проблемы здесь (по общему признанию, это не итеративное решение, но оно должно иметь оптимизацию хвостового вызова, что делает его таким же быстрым, как итеративное решение).