生成一定长度的所有排列 [英] Generating all permutations of a certain length

问题描述

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

Suppose we have an alphabet "abcdefghiklimnop". How can I recursively generate permutations with repetition of this alphabet in groups of FIVE in an efficient way?

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

I have been struggling with this a few days now. Any feedback would be helpful.

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

Essentially this is the same as: Generating all permutations of a given string

然而，我只想要整个长度为五的整数排列串。我无法弄清楚这一点。

However, I just want the permutations in lengths of FIVE of the entire string. And I have not been able to figure this out.

对于abcdefghiklimnop长度为5的所有子串，找到子串的排列。例如，如果子字符串是abcdef，我希望它的所有排列，或者如果子字符串是defli，我会想要该子字符串的所有排列。下面的代码给出了字符串的所有排列，但我想用它来查找字符串大小为5的所有子字符串的所有排列。

SO for all substrings of length 5 of "abcdefghiklimnop", find the permutations of the substring. For example, if the substring was abcdef, I would want all of the permutations of that, or if the substring was defli, I would want all of the permutations of that substring. The code below gives me all permutations of a string but I would like to use to find all permutations of all substrings of size 5 of a string.

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

推荐答案

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

In order to pick five characters from a string recursively, follow a simple algorithm:

• 到目前为止，您的方法应该填写一部分，并且


• 如果第一个需要一个角色的位置超过五个，那么你就完成了;打印到目前为止的组合，并返回


• 否则，将每个字符放入排列中的当前位置，并进行递归调用

这在Java中要短得多：

This is a lot shorter in 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中元素的数量进行排列：

The caller controls the desired length of permutation by changing the number of elements in perm:

char[] perm = new char[5];
permutation(perm, 0, "abcdefghiklimnop");

演示。

这篇关于生成一定长度的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！