python中字符串的所有可能长度k组合

Question

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

这就是我目前所拥有的，它很简单，如果k<；=len（字符串）：

 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 = 'AB'
k = 4
result = ['AAA,'ABB','AAB', 'ABA','BBB', 'BAA'.......]

提前谢谢。

Answer 1

根据你的评论：

I'm trying to search a very large string for the number of occurrences of each combination and see which combination occurs the most often.

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

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)

然后，您可以考虑使这个基本概念更加有效：例如，如果您在vlarge中遇到一个'x'字符，那么您知道包含它的任何子字符串都不是'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)

与此方法相比，“显而易见”的思想（遍历所有组合，计算它们作为子字符串出现的次数，并跟踪到目前为止最好的组合）使用较少的内存，但速度会慢一些，因为它必须在非常大的字符串上传递一个lot的过程。

如果我误解了你所说的“组合”的意思，也就是说如果我的uses_only函数不正确，那么你必须相应地调整我的想法。要点是：计算所需窗体的实际子字符串，因为它们比正确窗体的假设子字符串少。

Answer 2

我的回答只是对你正在做的事情的理论分析。 我将通过C（k，n）来表示二项式系数，该系数定义了包含n元素的集合中包含k元素的部分的数量。

假设你有一个长度串n∈ℕ^*和k∈ℕ，k。我假设字符串中的所有字符都是不同的。
我知道您正在尝试构建从输入字符串中提取的k个字符的字符串。

字符串的组合可以看作是⟦1，n的排列。有n！这样的排列。。。

然后，当k>；n时，情况变得更糟。。。设r=k mod n和p=（k-r）/n。显然我们有：

p ⩾ 1
0 ⩽ r < p

您的输出字符串可以分解成p“complete”子串，该子串由输入字符串的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!)² = 4

result = ['ABAB', 'ABBA', 'BAAB', 'BABA']

Answer 3

你很可能想要

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