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!

les_paulde
  • 43
  • 3

3 Answers3

5

The simplest way would be to generate permutations of 7 elements using the other letters, then interleave three Cs in with this afterwards.

BrenBarn
  • 242,874
  • 37
  • 412
  • 384
4

itertools is your friend:

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

Edit: this will give permutations, not combinations; if you want the result to be AAAAAAACCC .. CCCJJJJJJJ then it'll have to be slightly different. Here's a reasonably efficient product/filter solution:

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

And here's a method using interleaving as suggested by 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))

You'll need to test yourself, but for me the interleave method was significantly faster.

ecatmur
  • 152,476
  • 27
  • 293
  • 366
  • Thanks a lot for the great suggestions everyone! The interleave method indeed seems to be the fastest, and now it's managed to generate the list overnight, so I am very impressed! Ended up going with MatthieuW's code, works an absolute treat, many thanks! – les_paulde Aug 29 '12 at 05:59
2

What BrenBarn proposes can give this:

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)
MatthieuW
  • 2,292
  • 15
  • 25
  • I had no idea about inserting into a list using slices. For an explanation of this (possibly controversial) feature, see https://stackoverflow.com/a/2947881/10499953. – Attila the Fun Jun 14 '22 at 16:07