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

Question

Print all possible strings of length k formed from set of n characters is a common question and already have solution.

不过，我希望知道

Question: Is there any way to Print all possible strings without repetitive structure ?

重复结构示例 [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)。

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，则该值将保持不变。

对于排列中的第一个字符，只能出现list中的第一个字符:

static void printAllKLength(char[] set, int k)
{
    int n = set.length; 
    printAllKLengthRec(set, "", n, k, 1);
}