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

Question

打印由 n 个字符组成的所有可能的长度为 k 的字符串是一个常见问题，并且已经有了解决方案。

不过，我希望知道

问题：有没有办法打印所有可能的字符串而不重复结构？

重复结构示例 [k = 3, n = {a, b, c}]：

1. AAA = BBB = CCC
2. ABB = ACC = BAA = BCC = CAA = CBB
3. ABC = ACB = BAC = BCA = CAB = CBA
4. ABA = ACA = BAB = BCB = CAC = CBC
5. AAB = AAC = BBA = BBC = CCA = CCB

例如：

输入： k=3,n={a,b,c}

输出：

aaa
aab
aba
abb
abc

对于复杂度要求：不应大于O(n^k)。

标签： javaalgorithmpermutation

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