重复排列 - 非字谜算法

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']

显然，这个列表远远不够。

我想到了分区 e.g) 0As, 2Bs, 3Cs 是 0+2+3。在此示例中，在不到一分钟的时间内，手工详尽地找到了 21 的答案。事实上，我简化了过程，注意到第三个字母（比如 C，不失一般性）的数量取决于 As 和 Bs 的组合，所以我画了一个 table - 红叉表示无效组合，因为 sum >= 5: （顺便说一句，我想知道这个想法是如何扩展到 N > 3 的；因为从 table 来看，正方形被切成两半...）

为了将此 'algorithm' 传输到计算机上，我想过以某种方式利用对称性 - 这让我想起了格雷码 - 但我无法正确实现它。

有没有什么函数可以有效地处理这个问题？然后我什至不必（至少明确地）首先调用变位词检查器函数来比较输入。

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 部分的方法数等于插入 [=] 的方法数23=] n 项之间的分隔符。放置分隔符的结果是一个长度为 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)

重复排列 - 非字谜算法

Permutations with repetitions - Non-anagram algorithm

python

combinations

permutation

anagram