Строковые перестановки с использованием рекурсии в Java
Я наткнулся на ЭТО сообщение, которое очень старалось объяснить рекурсивное решение для печати всей строки.
public class Main {
private static void permutation(String prefix, String str){
int n = str.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i),
str.substring(0, i) + str.substring(i+1));
}
}
public static void main(String[] args) {
permutation("", "ABCD");
}
}
Но все же я не могу получить роль, когда мы начинаем выталкивать из стека. Например, рекурсия проходит весь путь до перестановки ("ABCD",""), где встречается базовый случай и печатается ABCD. Но что происходит сейчас? мы извлекаем перестановку ("ABC","D") из стека вызовов функций... что мы делаем с этим и так далее.
Может кто-нибудь, пожалуйста, помогите объяснить немного.
Кроме того, мне нужно несколько указателей на временной сложности этого? Не как полный расчет, но некоторые подсказки.
3 ответа
Более простой пример: permutation("", "ABC"), представляющий пустую строку как *:
* ABC + A BC + AB C - ABC *
| |
| ` AC B - ACB *
|
+ B AC + BA C - BAC *
| |
| ` BC A - BCA *
|
` C AB + CA B - CAB *
|
` CB A - CBA *
Обратите внимание, что это выглядит как дерево, лежащее на боку. Действительно, это называется деревом. Когда мы начнем, мы войдем ("A", "BC") государство; приступаем к звонку ("AB", "C"), и наконец ("ABC", ""), Здесь мы печатаем наш вывод. Затем мы вспоминаем, что у нас есть незаконченное дело, мы возвращаемся к циклу, но цикл на предыдущем уровне имел только один цикл. Итак, мы также закончили и вернемся к ("A", "BC") уровень; есть два элемента в "BC" и мы только сделали "B"так что теперь "C"черед: звоним ("AC", "B"), который затем вызывает ("ACB", ""), Теперь все петли под ("A", "BC") готово... Но подождите, все еще работа, чтобы сделать! Так как ("", "ABC") еще осталось обработать еще две буквы. И так далее, ветвление за ветвью, в том, что мы обычно называем "поиск в глубину".
На каждом уровне есть петля. Цикл сжимается (мы повторяем 3 раза в толстой ветви слева, затем 2 на следующем уровне, затем только один), но цикл все равно есть. Итак, в общем, мы делаем n * (n - 1) * (n - 2) * ... * 2 * 1 итераций. O(N!)?
В качестве разновидности рекурсии вы можете использовать Stream.reduce метод.
// original string
String str = "𝗔𝗕𝗖𝗗";
// array of characters of the string
int[] codePoints = str.codePoints().toArray();
// contents of the array
System.out.println(Arrays.toString(codePoints));
//[120276, 120277, 120278, 120279]
// list of permutations of characters
List<Map<Integer, String>> permutations = IntStream.range(0, codePoints.length)
// Stream<List<Map<Integer,String>>>
.mapToObj(i -> IntStream.range(0, codePoints.length)
// represent each character as Map<Integer,String>
.mapToObj(j -> Map.of(j, Character.toString(codePoints[j])))
// collect a list of maps
.collect(Collectors.toList()))
// intermediate output
//[{0=𝗔}, {1=𝗕}, {2=𝗖}, {3=𝗗}]
//[{0=𝗔}, {1=𝗕}, {2=𝗖}, {3=𝗗}]
//[{0=𝗔}, {1=𝗕}, {2=𝗖}, {3=𝗗}]
//[{0=𝗔}, {1=𝗕}, {2=𝗖}, {3=𝗗}]
.peek(System.out::println)
// reduce a stream of lists to a single list
.reduce((list1, list2) -> list1.stream()
// summation of pairs of maps from two lists
.flatMap(map1 -> list2.stream()
// filter out those keys that are already present
.filter(map2 -> map2.keySet().stream()
.noneMatch(map1::containsKey))
// join entries of two maps
.map(map2 -> {
Map<Integer, String> map = new LinkedHashMap<>();
map.putAll(map1);
map.putAll(map2);
return map;
}))
// collect into a single list
.collect(Collectors.toList()))
// List<Map<Integer,String>>
.orElse(List.of(Map.of(0, str)));
// number of permutations
System.out.println(permutations.size()); // 24
// number of rows (factorial of string length - 1)
int rows = IntStream.range(1, codePoints.length)
.reduce((a, b) -> a * b).orElse(1);
// column-wise output
IntStream.range(0, rows)
.mapToObj(i -> IntStream.range(0, permutations.size())
.filter(j -> j % rows == i)
.mapToObj(permutations::get)
.map(map -> map.toString().replace(" ", ""))
.collect(Collectors.joining(" ")))
.forEach(System.out::println);
//{0=𝗔,1=𝗕,2=𝗖,3=𝗗} {1=𝗕,0=𝗔,2=𝗖,3=𝗗} {2=𝗖,0=𝗔,1=𝗕,3=𝗗} {3=𝗗,0=𝗔,1=𝗕,2=𝗖}
//{0=𝗔,1=𝗕,3=𝗗,2=𝗖} {1=𝗕,0=𝗔,3=𝗗,2=𝗖} {2=𝗖,0=𝗔,3=𝗗,1=𝗕} {3=𝗗,0=𝗔,2=𝗖,1=𝗕}
//{0=𝗔,2=𝗖,1=𝗕,3=𝗗} {1=𝗕,2=𝗖,0=𝗔,3=𝗗} {2=𝗖,1=𝗕,0=𝗔,3=𝗗} {3=𝗗,1=𝗕,0=𝗔,2=𝗖}
//{0=𝗔,2=𝗖,3=𝗗,1=𝗕} {1=𝗕,2=𝗖,3=𝗗,0=𝗔} {2=𝗖,1=𝗕,3=𝗗,0=𝗔} {3=𝗗,1=𝗕,2=𝗖,0=𝗔}
//{0=𝗔,3=𝗗,1=𝗕,2=𝗖} {1=𝗕,3=𝗗,0=𝗔,2=𝗖} {2=𝗖,3=𝗗,0=𝗔,1=𝗕} {3=𝗗,2=𝗖,0=𝗔,1=𝗕}
//{0=𝗔,3=𝗗,2=𝗖,1=𝗕} {1=𝗕,3=𝗗,2=𝗖,0=𝗔} {2=𝗖,3=𝗗,1=𝗕,0=𝗔} {3=𝗗,2=𝗖,1=𝗕,0=𝗔}
См. Также: Как проверить, есть ли у слова анаграмма, которая является палиндромом?
Вы можете сгенерировать массив перестановок строки, используя
map и методы.
Это решение предполагает, что исходная строка не содержит повторяющихся символов, в противном случае перестановка отображает
Map<Integer,String>следует использовать вместо массивов перестановок
String[].
В
reduceМетод берет пару массивов перестановок и попарно суммирует их элементы , накапливая результаты. Например, четыре шага сокращения для пятисимвольной строки
𝖠𝖡𝖢𝖣𝖤:
0 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
1 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
---
sum1: [𝖠𝖡, 𝖠𝖢, 𝖠𝖣, 𝖠𝖤, ...]
2 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
---
sum2: [𝖠𝖡𝖢, 𝖠𝖡𝖣, 𝖠𝖡𝖤, ...]
3 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
---
sum3: [𝖠𝖡𝖢𝖣, 𝖠𝖡𝖢𝖤, ...]
4 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
---
total: [𝖠𝖡𝖢𝖣𝖤, 𝖠𝖡𝖢𝖤𝖣, ...]
// original string
String str = "𝖠𝖡𝖢𝖣𝖤";
// array of characters of the string
int[] codePoints = str.codePoints().toArray();
String[] permutations = IntStream.range(0, codePoints.length)
// intermediate output, character-position
.peek(i -> System.out.print(i + " "))
// prepare an array of possible permutations for each character-position
.mapToObj(i -> Arrays.stream(codePoints).mapToObj(Character::toString)
// array of characters as strings
.toArray(String[]::new))
// intermediate output, array of possible permutations
.peek(arr -> System.out.println(Arrays.deepToString(arr)))
// reduce a stream of arrays to a single array
.reduce((arr1, arr2) -> Arrays.stream(arr1)
// summation of pairs of strings from two arrays
.flatMap(str1 -> Arrays.stream(arr2)
// filter out those characters that are already present
.filter(str2 -> !str1.contains(str2))
// concatenate two strings
.map(str2 -> str1 + str2))
// collect into a single array
.toArray(String[]::new))
// otherwise an empty array
.orElse(new String[0]);
// final output
System.out.println("Number of permutations: " + permutations.length);
// number of rows
int rows = permutations.length / 10;
// permutations by columns
IntStream.range(0, rows).forEach(i -> System.out.println(
IntStream.range(0, permutations.length)
.filter(j -> j % rows == i)
.mapToObj(j -> permutations[j])
.collect(Collectors.joining(" "))));
Промежуточный вывод, массивы возможных перестановок для каждой позиции символа:
0 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
1 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
2 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
3 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
4 [𝖠, 𝖡, 𝖢, 𝖣, 𝖤]
Окончательный вывод, перестановки по столбцам:
Number of permutations: 120
𝖠𝖡𝖢𝖣𝖤 𝖠𝖣𝖡𝖢𝖤 𝖡𝖠𝖢𝖣𝖤 𝖡𝖣𝖠𝖢𝖤 𝖢𝖠𝖡𝖣𝖤 𝖢𝖣𝖠𝖡𝖤 𝖣𝖠𝖡𝖢𝖤 𝖣𝖢𝖠𝖡𝖤 𝖤𝖠𝖡𝖢𝖣 𝖤𝖢𝖠𝖡𝖣
𝖠𝖡𝖢𝖤𝖣 𝖠𝖣𝖡𝖤𝖢 𝖡𝖠𝖢𝖤𝖣 𝖡𝖣𝖠𝖤𝖢 𝖢𝖠𝖡𝖤𝖣 𝖢𝖣𝖠𝖤𝖡 𝖣𝖠𝖡𝖤𝖢 𝖣𝖢𝖠𝖤𝖡 𝖤𝖠𝖡𝖣𝖢 𝖤𝖢𝖠𝖣𝖡
𝖠𝖡𝖣𝖢𝖤 𝖠𝖣𝖢𝖡𝖤 𝖡𝖠𝖣𝖢𝖤 𝖡𝖣𝖢𝖠𝖤 𝖢𝖠𝖣𝖡𝖤 𝖢𝖣𝖡𝖠𝖤 𝖣𝖠𝖢𝖡𝖤 𝖣𝖢𝖡𝖠𝖤 𝖤𝖠𝖢𝖡𝖣 𝖤𝖢𝖡𝖠𝖣
𝖠𝖡𝖣𝖤𝖢 𝖠𝖣𝖢𝖤𝖡 𝖡𝖠𝖣𝖤𝖢 𝖡𝖣𝖢𝖤𝖠 𝖢𝖠𝖣𝖤𝖡 𝖢𝖣𝖡𝖤𝖠 𝖣𝖠𝖢𝖤𝖡 𝖣𝖢𝖡𝖤𝖠 𝖤𝖠𝖢𝖣𝖡 𝖤𝖢𝖡𝖣𝖠
𝖠𝖡𝖤𝖢𝖣 𝖠𝖣𝖤𝖡𝖢 𝖡𝖠𝖤𝖢𝖣 𝖡𝖣𝖤𝖠𝖢 𝖢𝖠𝖤𝖡𝖣 𝖢𝖣𝖤𝖠𝖡 𝖣𝖠𝖤𝖡𝖢 𝖣𝖢𝖤𝖠𝖡 𝖤𝖠𝖣𝖡𝖢 𝖤𝖢𝖣𝖠𝖡
𝖠𝖡𝖤𝖣𝖢 𝖠𝖣𝖤𝖢𝖡 𝖡𝖠𝖤𝖣𝖢 𝖡𝖣𝖤𝖢𝖠 𝖢𝖠𝖤𝖣𝖡 𝖢𝖣𝖤𝖡𝖠 𝖣𝖠𝖤𝖢𝖡 𝖣𝖢𝖤𝖡𝖠 𝖤𝖠𝖣𝖢𝖡 𝖤𝖢𝖣𝖡𝖠
𝖠𝖢𝖡𝖣𝖤 𝖠𝖤𝖡𝖢𝖣 𝖡𝖢𝖠𝖣𝖤 𝖡𝖤𝖠𝖢𝖣 𝖢𝖡𝖠𝖣𝖤 𝖢𝖤𝖠𝖡𝖣 𝖣𝖡𝖠𝖢𝖤 𝖣𝖤𝖠𝖡𝖢 𝖤𝖡𝖠𝖢𝖣 𝖤𝖣𝖠𝖡𝖢
𝖠𝖢𝖡𝖤𝖣 𝖠𝖤𝖡𝖣𝖢 𝖡𝖢𝖠𝖤𝖣 𝖡𝖤𝖠𝖣𝖢 𝖢𝖡𝖠𝖤𝖣 𝖢𝖤𝖠𝖣𝖡 𝖣𝖡𝖠𝖤𝖢 𝖣𝖤𝖠𝖢𝖡 𝖤𝖡𝖠𝖣𝖢 𝖤𝖣𝖠𝖢𝖡
𝖠𝖢𝖣𝖡𝖤 𝖠𝖤𝖢𝖡𝖣 𝖡𝖢𝖣𝖠𝖤 𝖡𝖤𝖢𝖠𝖣 𝖢𝖡𝖣𝖠𝖤 𝖢𝖤𝖡𝖠𝖣 𝖣𝖡𝖢𝖠𝖤 𝖣𝖤𝖡𝖠𝖢 𝖤𝖡𝖢𝖠𝖣 𝖤𝖣𝖡𝖠𝖢
𝖠𝖢𝖣𝖤𝖡 𝖠𝖤𝖢𝖣𝖡 𝖡𝖢𝖣𝖤𝖠 𝖡𝖤𝖢𝖣𝖠 𝖢𝖡𝖣𝖤𝖠 𝖢𝖤𝖡𝖣𝖠 𝖣𝖡𝖢𝖤𝖠 𝖣𝖤𝖡𝖢𝖠 𝖤𝖡𝖢𝖣𝖠 𝖤𝖣𝖡𝖢𝖠
𝖠𝖢𝖤𝖡𝖣 𝖠𝖤𝖣𝖡𝖢 𝖡𝖢𝖤𝖠𝖣 𝖡𝖤𝖣𝖠𝖢 𝖢𝖡𝖤𝖠𝖣 𝖢𝖤𝖣𝖠𝖡 𝖣𝖡𝖤𝖠𝖢 𝖣𝖤𝖢𝖠𝖡 𝖤𝖡𝖣𝖠𝖢 𝖤𝖣𝖢𝖠𝖡
𝖠𝖢𝖤𝖣𝖡 𝖠𝖤𝖣𝖢𝖡 𝖡𝖢𝖤𝖣𝖠 𝖡𝖤𝖣𝖢𝖠 𝖢𝖡𝖤𝖣𝖠 𝖢𝖤𝖣𝖡𝖠 𝖣𝖡𝖤𝖢𝖠 𝖣𝖤𝖢𝖡𝖠 𝖤𝖡𝖣𝖢𝖠 𝖤𝖣𝖢𝖡𝖠