1

我想获得长度为 k 的字符串中所有可能的字母组合。我知道这方面有很多帖子，但我有点扭曲 k 大于字符串的长度。

这就是我到目前为止所拥有的，如果 k <= len(string)，它很简单并且有效：

 string = 'ABCD'
 permutations = ["".join(x) for x in itertools.permutations(string, k)]

如果 k = 4，则结果：

 ['ABCD', 'ABDC', 'ACBD', 'ACDB', 'ADBC', 'ADCB', 'BACD', 'BADC', 'BCAD', 'BCDA', 
'BDAC','BDCA', 'CABD', 'CADB', 'CBAD', 'CBDA', 'CDAB', 'CDBA', 'DABC', 'DACB', 
'DBAC', 'DBCA', 'DCAB', 'DCBA']

这按预期工作。但是，我想要这四个字母与 k > len(string) 的所有可能组合。

我想要的一个示例答案是：

string = 'AB'
k = 4
result = ['AAA,'ABB','AAB', 'ABA','BBB', 'BAA'.......]

提前致谢。

4

3 回答 3

8

你可能想要

itertools.product(string, repeat=k)

反而。试试看！您的描述不明确，因此无法确定。

例子：

>>> import itertools
>>> for p in itertools.product("ab", repeat=3):
...     print p
('a', 'a', 'a')
('a', 'a', 'b')
('a', 'b', 'a')
('a', 'b', 'b')
('b', 'a', 'a')
('b', 'a', 'b')
('b', 'b', 'a')
('b', 'b', 'b')
于 2013-10-17T21:14:49.530 回答
3

根据您的评论：

我正在尝试在一个非常大的字符串中搜索每个组合的出现次数，并查看哪个组合最常出现。

还有另一种方法可以做你想做的事：

def substrings(vlarge, k):
    return (vlarge[idx:idx+k] for idx in range(len(vlarge)-k+1))

def uses_only(value, chars):
    return all(ch in chars for ch in value)

def most_common(vlarge, chars, k):
    return collections.Counter(s for s in substrings(vlarge, k) if uses_only(s, chars)).most_common(1)

然后，您可以考虑使这个基本想法更有效：例如，如果您遇到一个'x'字符，vlarge那么您知道包含它的子字符串都不是'abcd'. 因此，您可以跳到在以下位置开始的子字符串x：

def generate_substrings(vlarge, chars, k):
    idx = 0
    goodrange = 0
    while idx <= len(vlarge) - k:
        while goodrange < idx + k:
            if vlarge[goodrange] in chars:
                goodrange += 1
            else:
                idx = goodrange + 1
                if idx > len(vlarge) - k:
                    return
                goodrange = idx
        yield vlarge[idx:goodrange]
        idx += 1

def most_common(vlarge, chars, k):
    return collections.Counter(generate_substrings(vlarge, chars, k)).most_common(1)

与这种方法相比，“明显”的想法（遍历所有组合，计算它们作为子字符串出现的次数，并跟踪迄今为止最好的）使用更少的内存但会慢很多，因为它必须使很多通过非常大的字符串。

如果我误解了您所说的“组合”是什么意思，也就是说如果我的uses_only功能不正确，那么您必须相应地调整我的想法。关键是：计算您想要的形式的实际子字符串，因为它们的数量少于正确形式的假设子字符串。

于 2013-10-17T22:01:53.667 回答
1

我的回答只是对你在做什么的理论分析。我将用C(k,n)表示定义包含n 个元素的集合中包含k个元素的部分的数量的二项式系数。

假设你有一个长度为n ∈ ℕ<sup>* 和k ∈ ℕ, k ⩾ n的字符串。我会假设你的字符串中的所有字符都是不同的。
我了解到您正在尝试构建从输入字符串中提取的k个字符的字符串。

您的字符串字符的组合可以看作是 ⟦<em>1, n⟧ 的排列。有n！这样的排列...

然后，当k > n时，情况会变得更糟......让r = k mod n和p = (k - r)/n。显然我们有：

p ⩾ 1
0 ⩽ r < p

您的输出字符串可以分解为p个“完整”子字符串，这些子字符串由n 个输入字符的排列组成，一个子字符串仅由输入字符串的r个字符组成。

要构建这样一个“不完整”的子字符串，您首先必须选择输入字符串的r个字符的子集，然后选择这些字符的排列。最后，此类可能子串的数量s r,n为：

s r,n = C(r,n).r!

请注意，当 r = 0 时，此公式不会导致无效的全局结果，因为 C(0,n) = 1 和 0！= 1 按照惯例。

您可以根据您的方案构建的k长字符串的最终数量是：

s tot = (C(r,n).r!).(n!) p

这个数字高的离谱！

对于k = 4和n = 2，我们有：

s tot = (C(0,4).0!).(2!) 2 = 4

result = ['ABAB', 'ABBA', 'BAAB', 'BABA']
于 2013-10-17T22:15:40.903 回答