Fast Permutation with some static elements

Question

i have a function which gets a string like "ABA?" the question-mark is a wildcard which can either be A or B the passed string can have multiple wildcards. It should give back multiple strings as an array with all possible solutions. My Code is far to slow. I am new to python so its a little difficult to find a good solution.

When "ABA?" is passed it should return ['ABAA', 'ABAB'].

from itertools import product

def possibilities(param):
    result = []
    for i in product([A,B], repeat=param.count('?')):
        string = param
        for p in [i]:
            for val in p:
                string = string.replace('?', str(val), 1)
            result.append(string)
    return result

I don't understand your question, you want to append one per time the letters without repetitions ? So if ABC output : ABCA ABCB ABCC ???Anyway here you can find what are you looking for : https://docs.python.org/2/library/itertools.html — Teshtek, Feb 01 '17 at 15:25
there is no C the only letters are AB and a wildcard which can be A or B — user2502106, Feb 01 '17 at 15:59

score 1 · Accepted Answer · edited May 23 '17 at 12:24

1

You should use a generator so you can loop over the output. If you have a lot of wildcards, the complete list would require a lot of memory to store completely (it grows exponentially!)

import itertools

def possibilties(s):
    n_wildcard = s.count('?')

    for subs in itertools.product(['A','B'], repeat=n_wildcard):
        subs = iter(subs)
        yield ''.join([x if x != '?' else subs.next() for x in s])

for p in possibilties('A?BA?'):
    print p

This gives:

AABAA
AABAB
ABBAA
ABBAB

edited May 23 '17 at 12:24

Community

1
1

answered Feb 01 '17 at 15:27

Hooked

84,485
43
192
261

Its definitely a better solution but it takes to long to finish it should need to be 10 % faster but i really have no idea how this is achieved. – user2502106 Feb 01 '17 at 15:56

Fast Permutation with some static elements

1 Answers1