具有重复的置换-非七字算法

Question

AIM：我试图找到包含长度为N的非字谜的列表的最大长度，每个字谜词由3个字母的组合组成：“ A”，“ B”或“ C”。

例如，如果N = 5：[AAAAA，AAAAB，...，AABBC，...，BABAA，...，CCCCC]。

要澄清，由于AAAAB是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和B的组合，从而简化了过程，因此我画了一张表-红叉表示无效的组合，因为总和> = 5： （顺便说一句，我想知道这个想法如何扩展到N> 3；因为从桌子上看，正方形被切成两半...）]

为了将这个“算法”转移到计算机上，我想到了某种方式来利用对称性-它使我想起了格雷码-但我无法正确实现它。

---

是否有任何功能可以有效地解决此问题？然后，我什至不必（至少显式地）首先调用anagram-checker函数来比较输入。

Answer 1

也许不是您要的有效解决方案，但是您可以使用集合的笛卡尔积来产生所需的3 ^ 5重复排列。

import itertools

x = ['a', 'b', 'c']
output_list = [p for p in itertools.product(x, repeat=5)]

然后使用适当的字谜检查器功能删除output_list中的所有非字谜。

---

编辑输出为：[（'a'，'a'，'a'，'a'，'a'），（'a'，'a'，'a'，'a'，'b'），（' a'，'a'，'a'，'a'，'c'），（'a'，'a'，'a'，'b'，'a'），（'a'，'a' ，“ a”，“ b”，“ b”），（“ a”，“ a”，“ a”，“ b”，“ c”），（“ a”，“ a”，“ a”，“ c'，'a'），（'a'，'a'，'a'，'c'，'b'），（'a'，'a'，'a'，'c'，'c' ），（'a'，'a'，'b'，'a'，'a'），（'a'，'a'，'b'，'a'，'b'），（'a' ，'a'，'b'，'a'，'c'），...，（'c'，'c'，'c'，'c'，'b'），（'c'，' c'，'c'，'c'，'c'）]

Answer 2

AIM：我正在尝试查找包含长度为N的非字词的列表的最大长度，每个字词由3个字母的组合组成：“ A”，“ B”或“ C”。] >

鉴于此目标，您生成所有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部分的方式的数量等于在k - 1之间插入n分隔符的方式的数量。项目。放置分隔符的结果是长度为n + k - 1的字符串：

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

因此，我们可以减少计算长度为k - 1的字符串中放置|个符号n + 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)

Answer 3

您可以将它们过滤掉。