假设我们有一个字母“abcdefghiklimnop”。我怎样才能以一种有效的方式递归地生成排列,以五组为一组重复这个字母表?
这几天我一直在为这个问题苦苦挣扎。任何反馈都会有所帮助。
本质上这与:Generating all permutations of a given string 相同
但是,我只想要整个字符串长度为 5 的排列。我一直无法弄清楚这一点。
因此,对于“abcdefghiklimnop”的所有长度为 5 的子串,找到子串的排列。例如,如果子字符串是 abcdef,我会想要它的所有排列,或者如果子字符串是 defli,我会想要该子字符串的所有排列。下面的代码给了我一个字符串的所有排列,但我想用它来查找一个字符串的所有大小为 5 的子字符串的所有排列。
public static void permutation(String str) {
permutation("", str);
}
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, n));
}
}
最佳答案
为了递归地从字符串中选取五个字符,请遵循一个简单的算法:
- 到目前为止,您的方法应该已经填充了一部分,并且需要一个字符的五字符排列中的第一个位置
- 如果需要字符的第一个位置在五个以上,你就完成了;打印你目前的组合,然后返回
- 否则,将每个字符放入排列中的当前位置,并进行递归调用
这在 Java 中要短得多:
private static void permutation(char[] perm, int pos, String str) {
if (pos == perm.length) {
System.out.println(new String(perm));
} else {
for (int i = 0 ; i < str.length() ; i++) {
perm[pos] = str.charAt(i);
permutation(perm, pos+1, str);
}
}
}
调用者通过改变 perm
中的元素数量来控制所需的排列长度:
char[] perm = new char[5];
permutation(perm, 0, "abcdefghiklimnop");
关于java - 生成一定长度的所有排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35323412/