4

现在花了相当多的时间试图想出一种方法(我认为)应该是一个相对简单的过程,我设法编写了将产生结果的代码(感谢这个精彩论坛上的建议!) ,但根据我的计算,计算所有可能性需要几年时间,所以我拼命寻求帮助,因为我担心我的电脑可能活不到那一天。:) 任何输入将不胜感激!

我想要实现的是来自 10 个唯一条目的列表(例如 ['A','B','C','D','E','F','G',H','I ','J']),获取长度为 10 的字符串上的所有排列,但要求元素中的 1 个(例如 'C')应恰好出现 3 次,并且出现在所有可能的位置。

现在我正在使用:

options = ['A','B','C','D','E','F','G','H','I','J']
def combos(options,n):
    if (n <= 0): return
    for s in options:
        if len(s) <= n: yield s
        for t in combos(options,n-len(s)): yield s+t

for x in combos(options,10):
    if x.count("C") == 3 and len(x) == 10:
        print x

这样,它正在计算所有可能的排列并选择具有 3 个“Cs”的排列,因此会生成大量不包含 3 个“Cs”的不必要排列,因此它花费的时间比必要的要长。有人对我如何让 Python 在生成排列时遵守 3x 'C' 限制有任何建议吗?

很多,非常感谢提前!

4

3 回答 3

5

最简单的方法是使用其他字母生成 7 个元素的排列,然后将三个 C 插入其中。

于 2012-08-28T08:08:04.800 回答
4

itertools是你的朋友:

from itertools import chain, imap, permutations, combinations, repeat
others = [o for o in options if o != 'C']
chain.from_iterable(permutations(*chain(repeat('C', 3), x))
                    for x in combinations(others, 7))

编辑:这将给出排列,而不是组合;如果你想要结果,AAAAAAACCC .. CCCJJJJJJJ那么它必须略有不同。这是一个相当有效的产品/过滤器解决方案:

from itertools import product
(x for x in product(options, repeat=10) if x.count('C') == 3)

这是一种使用 BrenBarn 建议的交错的方法:

from itertools import product
others = [o for o in options if o != 'C']
(r[:i] + ('C',) + r[i:j] + ('C',) + r[j:k] + ('C',) + r[k:]
 for r in product(others, repeat=7)
 for i in range(8) for j in range(i, 8) for k in range(j, 8))

您需要自己测试,但对我来说,交错方法要快得多。

于 2012-08-28T08:13:18.590 回答
1

BrenBarn 的建议可以给出:

from itertools import product, combinations

otheroptions = ['A','B',   'D','E','F','G','H','I','J']
c = "C"
l = 10
nc = 3

for t in product(otheroptions, repeat=l-nc):
    for p in combinations(range(l), nc):
        r = list(t)
        for i in p:
            r[i:i] = [c]
        print "".join(r)
于 2012-08-28T09:45:44.320 回答