生成特定长度的所有排列

Question

假设我们有一个字母表 "abcdefghiklimnop"。如何以递归的方式高效地生成该字母表中长度为五的重复排列？

我已经苦苦思索了几天，任何反馈都将是有帮助的。

本质上，这与 生成给定字符串的所有排列 相同。

然而，我只想要整个字符串中长度为五的排列。但我一直没有能够解决这个问题。

因此，对于 "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));
    }
}

- TheHumblePedestrian

---

你能不能不生成它们所有，然后循环遍历它们所有并取前5个字符？ - OneCricketeer

@cricket_007 这样会产生很多重复的内容。另外，楼主也希望找到一种高效的方法来生成它们。 - Sergey Kalinichenko

@dasblinkenlight - 啊，我漏掉了“高效”这个词。 - OneCricketeer

使用您找到的算法，但首先生成长度为5的所有子字符串。 - OneCricketeer

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

演示。

- Sergey Kalinichenko

---

我认为这只会给出一个排列。 - cdaiga

请点击演示链接并向下滚动，以查看运行此程序的结果。 @cdaiga - Sergey Kalinichenko

点赞 @dasblinkenlight。结果完美。 - cdaiga

非常出色！非常感谢dasblinkenlight。 - TheHumblePedestrian

一个超级聪明的解决方案！ - Keerthi

Answer 2

每个排列的前五个字符集合中都包含五个字符的所有排列。例如，如果您想获得一个四个字符字符串'abcd'的所有两个字符的排列，可以从所有排列中获得它们： 'abcd'、'abdc'、'acbd'、'acdb' ... 'dcba'

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

- Luke Caswell Samuel

Answer 3

class StringPermutationOfKLength
{
    // The main recursive method
    // to print all possible
    // strings of length k
    static void printAllKLengthRec(char[] set,String prefix,
                                   int n, int k)
    {

        // Base case: k is 0,
        // print prefix
        if (k == 0)
        {
            System.out.println(prefix);
            return;
        }

        // One by one add all characters
        // from set and recursively
        // call for k equals to k-1
        for (int i = 0; i < n; i++)
        {

            // Next character of input added
            String newPrefix = prefix + set[i];

            // k is decreased, because
            // we have added a new character
            printAllKLengthRec(set, newPrefix,
                n, k - 1);
        }
    }

    // Driver Code
    public static void main(String[] args)
    {
        System.out.println("First Test");
        char[] set1 = {'a', 'b','c', 'd'};
        int k = 2;
        printAllKLengthRec(set1, "", set1.length, k);

        System.out.println("\nSecond Test");
        char[] set2 = {'a', 'b', 'c', 'd'};
        k = 1;
        printAllKLengthRec(set2, "", set2.length, k);
    }

- Ravi Raj

Answer 4

这可以很容易地使用位操作完成。

private void getPermutation(String str, int length)
        {
            if(str==null)
                return;
            Set<String> StrList = new HashSet<String>();
            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;
    }

- Krishna Kant

---

这个问题要求排列组合，但是这段代码会给出组合。 - midhun mathew