Python bruteforce combinations given a starting string

Question

I'm trying to do a bruteforce string generator in Python and itertools.combinations_with_replacement seemed to do just the trick.

gen = itertools.combinations_with_replacement('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ',12)
for combination in gen:
  check(''.join(combination))

Say the user runs the program for some hours and reaches up to string aaaeabdouzIU.

Is there any way given a string where they left off to start making combinations from that point onwards?

So if I pass the string 'acc' it should start trying 'acd','ace',...

itertools.combinations_with_replacement does not provide this natively, is there any way someone could achive this?

I don't know of any way, but the itertools documentation lists an equivalent piece of code (two, actually) that you could try to adopt to your use. — , Jun 17 '15 at 23:36
Also a bonus tidbit. If you don't want to type out all the letters. `import string; string.ascii_letters` — cr1msonB1ade, Jun 17 '15 at 23:51
You want to be able to 'increment' the first output to get the second, and the nth to get the n+1th. There is no built-in way. Try to convert the output range to an integer range and back. If that is possible, you can easily increment the integers starting from anywhere in the sequence, and generate any subsequence you wish. — krethika, Jun 17 '15 at 23:55

cr1msonB1ade · Accepted Answer · 2015-06-19T22:47:52.913

Taking the original code from the itertools man page copy the code for the combinations_with_replacement code but replace line 7 with new indices starting from your entered word.

inputStr='acc'
indices=[pool.index(l) for l in inputStr]

And then run the rest of the code from the man page.

EDIT: For a complete running function:

def combinations_with_replacement(iterable, r, startWord=None):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC                                                                                   
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    if startWord is None:
        indices = [0] * r
    else:
        assert len(startWord) == r
        indices = [pool.index(l) for l in startWord]
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

The final else block should be unintended - it belongs to the for loop, not the if. The code doesn't work otherwise — Magnus, Jun 19 '15 at 22:34

score 1 · Answer 2 · edited May 23 '17 at 12:05

It's easy if you know, given a combination, how to generate the next one.

One way to do it could be to define a mapping from combination to natural numbers, and the inverse mapping, from natural numbers to combinations. For example you can use base62_encode/base62_decode from Base 62 conversion

def next_comb(s):
    return base62_encode(1+base62_decode(s))

and a generator to generate all combination given a starting point:

def generate_all(start='a'):
    while True:
        yield start
        start = next_comb(start)

Usage:

for comb in generate_all():
    print(comb)

or, to resume computation from a starting point:

for comb in generate_all(starting_point):
    print(comb)

Python bruteforce combinations given a starting string

2 Answers2