4

Having spent a considerable amount of time now trying to come up with a way to (what I think) should be a relatively simple procedure, I have managed to write the code which will generate the results (thanks to suggestions on this wonderful forum!), but according to my calculations it would take several years to compute all possibilities, so I'm desperately looking for some help as I fear my computer may not live to see that day. :) Any input would be very much appreciated!

What I would like to achieve is from a list of 10 unique entries (e.g. ['A','B','C','D','E','F','G',H','I','J']), get all permutations over a string length of 10, but with the requirement that 1 of the elements (e.g. 'C'), should occur exactly 3 times, and in all possible locations.

Right now I am using:

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

This way, it is computing all possible permutations and picks the ones with 3 'Cs', and therefore generates a large amount of unnecessary permutations which do not contain 3 'Cs', hence why it is taking longer than necessary. Does anyone have any suggestions how I might get Python to adhere to the 3x 'C' restriction while generating the permutations?

many, many thanks in advance!

4

3 に答える 3

5

最も簡単な方法は、他の文字を使用して 7 つの要素の順列を生成し、その後に 3 つの 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 に答える