在 Java 中查找给定字符串的所有排列
排列是一种数学技术,用于在排列顺序很重要时确定集合中可能排列的数量。
使用递归的字符串排列
函数 permutationFinder(String str)
是递归的,它打印传递的字符串的每个排列。Set
变量用于存储 Java 字符串的排列,以便自动删除重复项。我们砍掉我们的单词,在我们的字符串中一次取一个字母,并分别处理剩余的字母。
insertChar
函数插入第一个字符以获取我们传递的字符串的完整排列列表。
我们从字符串 ABC
开始,我们遍历它,一次一个字母。我们将初始字符 A
分开,其余字符是 BC
。现在我们遍历 rem
并找到剩余字母的排列。下面进一步解释该过程。
permutationFinder()
函数被触发,直到我们没有任何东西可以砍;这就是为什么我们得到 rem = ""
。在这一点上,我们将 ""
添加到 perms
并返回它,它被进一步存储到 Set
变量 words
中。另外,请记住此时我们的初始
字符是 C
。
我们循环遍历 Set
单词中的每个字符串。我们有 strNew
作为""
空字符串,在这种情况下它进入第二个 for 循环,我们有 i=0
,它等于 strNew.length()
;因此,我们使用该点的参数调用 insertChar("",C,0)
方法。此调用返回 C
,将其添加到 perm
。
我们打破循环并检查我们是否有未完成的工作。因此,在这一点上,我们的 initial
值为 B
,而 words
有一个元素,即 C
。现在,循环通过在不同位置添加 B
和 C
来重复。因此,我们将 BC
和 CB
作为 Set
词中的两个元素。
在这一点上,我们退出循环并获得 initial
值作为 A
。我们进一步重复这个过程,并在我们之前的排列中的可能位置插入初始字符 A
。首先,对于 BC
,我们得到 ABC
BAC
和 BCA
。类似地,对于第二个排列 CB
,我们做同样的事情:在可能的位置插入第一个字母并得到 ACB
、CAB
和 CBA
。
import java.util.HashSet;
import java.util.Set;
public class PermutationFinder {
public static Set<String> permutationFinder(String str) {
Set<String> perm = new HashSet<String>();
if (str == null) {
return null;
} else if (str.length() == 0) {
perm.add("");
return perm;
}
char initial = str.charAt(0);
String rem = str.substring(1);
Set<String> words = permutationFinder(rem);
for (String strNew : words) {
for (int i = 0;i<=strNew.length();i++){
perm.add(insertChar(strNew, initial, i));
}
}
return perm;
}
public static String insertChar(String str, char c, int j) {
String begin = str.substring(0, j);
String end = str.substring(j);
return begin + c + end;
}
public static void main(String args[]){
String s1 = "ABC";
System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
}
}
这些是字符串 ABC
的所有可能排列。
输出:
Permutations for ABC are:
[ACB, BCA, ABC, CBA, BAC, CAB]
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedIn