打印所有可能的长度为k的字符串，这些字符串由n个字符组成，没有重复的结构

Question

打印所有可能的由n个字符组成的长度为k的字符串是一个常见问题，并且已经有解决方法。但是，我希望知道问题：有没有办法打印出所有可能的字符串而无需重复的结构？重复结构示例[k = 3，n = {a，b，c}]：AAA = BBB = CCCABB = ACC = BAA = BCC = CAA = CBBABC = ACB = BAC = BCA = CAB = CBAABA = ACA = BAB = BCB = CAC = CBCAAB = AAC = BBA = BBC = CCA = CCB例如：输入： k=3，n={a,b,c}输出：aaa aab aba abb abc对于复杂度要求：不应大于O(n^k)。

Answer 1

您可以调整现有解决方案。您需要添加的限制是，一个字符只能在列表中的所有其他字符至少出现一次之后才能出现在字符串中。之所以起作用，是因为对于具有相同重复结构的每组字符串，每个字符的首次出现均以它们在列表中出现的顺序出现，因此这是您输出的字符串。您可以使用额外的参数来强制执行此限制：

static void printAllKLengthRec(char[] set, 

                            String prefix, 

                            int n, int k, int validCount)

{

    // Base case: k is 0, print prefix

    if (k == 0) 

    {

        System.out.println(prefix);

        return;

    }

    // One by one add all valid characters and recursively call for k equals to k-1

    for (int i = 0; i < validCount; ++i)

    {

        // Next character of input added

        String newPrefix = prefix + set[i]; 

        // increment the valid count if all characters up till then have already

        // appeared and there are characters that have not yet appeared

        // (i.e. validCount < n)

        int newValidCount = (i == (validCount - 1)) && (validCount < n) ?

            validCount + 1 :

            validCount;

        // k is decreased, because we have added a new character

        printAllKLengthRec(set, newPrefix, 

                                n, k - 1, newValidCount); 

    }

}

因此，例如，如果您的集合为{'a', 'b', 'c', 'd'}且validCount为3，则意味着a和b已经出现，因此可以将a或b或c附加到字符串中。如果追加c，则在递归调用函数之前增加值，因为现在a和b和c至少出现过一次，因此可以追加d。如果添加a或b，则该值将保持不变。

对于排列中的第一个字符，只能显示列表中的第一个字符：

static void printAllKLength(char[] set, int k)

{

    int n = set.length; 

    printAllKLengthRec(set, "", n, k, 1);

}