带重复的置换算法

Question

目标：我试图找到一个列表的最大长度，该列表包含长度为N的非字谜，每个字谜单词由3个字母组成：“a”、“B”或“C”

例如，如果N=5:[aaaaaaa，AAAAB，…，AABBC，…，BABAA，…，CCCCC]

为了澄清，因为aab是AABAA的一个字谜，反之亦然，所以它们从输出列表中被打折

---

我的问题：首先，我想知道如何生成所有3^5排列。 我的尝试：

import itertools
print([''.join(p) for p in itertools.combinations_with_replacement('abc', 3)])

>> ['aaaaa', 'aaaab', 'aaaac', 'aaabb', 'aaabc', 'aaacc', 'aabbb', 'aabbc', 'aabcc', 'aaccc', 'abbbb', 'abbbc', 'abbcc', 'abccc', 'acccc', 'bbbbb', 'bbbbc', 'bbbcc', 'bbccc', 'bcccc', 'ccccc']

显然，这份名单还有很长的路要走

我考虑过分区，例如）0As，2Bs，3Cs是0+2+3。在本例中，用手进行的详尽查找在一分钟内给出了21的答案。事实上，我简化了这个过程，注意到第三个字母的数量（比如说C，不失去一般性）取决于As和Bs的组合，所以我画了一个表格——红十字代表无效的组合，因为sum>；=5:（顺便说一句，我想知道这个想法是如何延伸到N>；3的；因为从桌子上看，正方形被切成两半……）

为了将这个“算法”转移到计算机上，我曾想过以某种方式利用对称性——这让我想起了格雷码——但我无法正确地实现它

---

是否有任何功能可以有效地处理此问题？然后，我甚至不必（至少明确地）首先调用一个字谜检查器函数来比较输入

Answer 1

AIM: I am trying to find the maximum length of a list comprising non-anagrams, of length N, each anagram-word consisting of a combination of 3 letters: 'A's, 'B's or 'C's.

考虑到这个目标，生成所有3 ** 5可能的字符串然后过滤掉字谜的方法是无效的。可以直接计算所需的数字，而无需实际生成任何字符串：

• 当且仅当两个字符串具有相同的字母频率时，它们才是字谜。例如，ABCAB是AABBC的一个字谜，因为两个字符串的字母频率都是{'A': 2, 'B': 2, 'C': 1}
• 因此，不包含字谜的列表的最大可能长度等于可能的不同频率映射的数量，其中键为'A', 'B', 'C'，值为非负整数，值之和为5（因此字符串长度为5）
• 这可以通过计算将非负整数n划分为k个部分的方法的数量来计算，其中部分的顺序很重要，并且一个部分允许为0

下面是一个递归解决方案：

from functools import lru_cache

# memoize since there are overlapping subproblems
@lru_cache(maxsize=None)
def count_partitions(n, k):
    if n < 0 or k < 0:
        raise ValueError()
    elif n == 0:
        return 1
    elif k <= 1:
        return k
    else:
        return sum(count_partitions(r, k - 1) for r in range(n + 1))

例如：

>>> count_partitions(5, 3)
21

这与itertools.combinations_with_replacement一致，它在本例中生成了一个包含21个字符串的列表，并且与手工计算一致

---

事实上，我们可以通过稍微不同的方式来进一步构建问题：将n划分为k部分的方法的数量相当于在n项之间插入k - 1分隔符的方法的数量。放置分隔符的结果是长度为n + k - 1的字符串：

• 在上面的示例中，分隔符的位置类似于AA|BB|C
• 相反，如果我们知道两个分隔符的位置，比如..|..|.，那么我们可以用字母填充以生成字符串AA|BB|C

因此，我们可以将问题简化为计算在长度为n + k - 1的字符串中放置k - 1符号|的方法的数量。这就是二项式系数binom(n + k - 1, k - 1)：

def binom(n, k):
    if n < 0 or k < 0 or k > n:
        return 0
    k = min(k, n - k)
    result = 1
    for a, b in zip(range(n, n - k, -1), range(1, k + 1)):
        result *= a
        result //= b
    return result

def count_partitions(n, k):
    return binom(n + k - 1, k - 1)