В этом примере мы научимся вычислять все перестановки строки в Java.
Чтобы понять этот пример, вы должны знать следующие темы программирования Java:
- Строка Java
- Рекурсия Java
- Класс Java Scanner
Под перестановкой строки подразумеваются все возможные новые строки, которые могут быть образованы путем изменения положения символов строки. Например, строка ABC имеет перестановки (ABC, ACB, BAC, BCA, CAB, CBA) .
Пример: программа на Java для получения всех перестановок строки
import java.util.HashSet; import java.util.Scanner; import java.util.Set; class Main ( public static Set getPermutation(String str) ( // create a set to avoid duplicate permutation Set permutations = new HashSet(); // check if string is null if (str == null) ( return null; ) else if (str.length() == 0) ( // terminating condition for recursion permutations.add(""); return permutations; ) // get the first character char first = str.charAt(0); // get the remaining substring String sub = str.substring(1); // make recursive call to getPermutation() Set words = getPermutation(sub); // access each element from words for (String strNew : words) ( for (int i = 0;i<=strNew.length();i++)( // insert the permutation to the set permutations.add(strNew.substring(0, i) + first + strNew.substring(i)); ) ) return permutations; ) public static void main(String() args) ( // create an object of scanner class Scanner input = new Scanner(System.in); // take input from users System.out.print("Enter the string: "); String data = input.nextLine(); System.out.println("Permutations of " + data + ": " + getPermutation(data)); ) )
Вывод
Введите строку: ABC Перестановки ABC: (ACB, BCA, ABC, CBA, BAC, CAB)
В Java мы использовали рекурсию для вычисления всех перестановок строки. Здесь мы храним перестановку в наборе. Таким образом, повторной перестановки не будет.
