生成一定长度的所有排列

假设我们有一个字母“abcdefghiklimnop”。 如何以有效的方式以五组为单位递归地重复生成这种字母表的排列？

我几天来一直在努力解决这个问题。 任何反馈都会有所帮助。

基本上这与以下内容相同： 生成给定字符串的所有排列

但是，我只想要整个字符串的FIVE长度排列。 我无法弄清楚这一点。

对于“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)); } } 

Answer 1

为了从递归的字符串中选择五个字符，请遵循一个简单的算法：

• 你的方法到目前为止应该填充一部分，并且五个字符排列中的第一个位置需要一个字符
• 如果第一个需要角色的位置超过五个，你就完成了; 打印到目前为止的组合，然后返回
• 否则，将每个字符放入置换中的当前位置，并进行递归调用

这在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"); 

演示。

Answer 2

五个字符的所有排列将包含在每个排列的前五个字符的集合中。 例如，如果你想要四个字符串’abcd’的所有两个字符排列，你可以从所有排列中获得它们：’abcd’，’abdc’，’acbd’，’acdb’…’dcba’

因此，在检查是否已存储该排列之后，您可以将它们存储到列表中，而不是在方法中打印它们。 列表可以传递给函数或静态字段，具体取决于您的规范。

Answer 3

这可以使用位操作轻松完成。

 private void getPermutation(String str, int length) { if(str==null) return; Set StrList = new HashSet(); StringBuilder strB= new StringBuilder(); for(int i = 0;i < (1 << str.length()); ++i) { strB.setLength(0); //clear the StringBuilder if(getNumberOfOnes(i)==length){ for(int j = 0;j < str.length() ;++j){ if((i & (1 << j))>0){ // to check whether jth bit is set (is 1 or not) strB.append(str.charAt(j)); } } StrList.add(strB.toString()); } } System.out.println(Arrays.toString(StrList.toArray())); } private int getNumberOfOnes (int n) // to count how many numbers of 1 in binary representation of n { int count=0; while( n>0 ) { n = n&(n-1); count++; } return count; }