Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Variable number of predictable for loops in Python

I am trying to come up with a way to generate all possible unique strings from an alphabet of 20 characters where the order within the string doesn't matter, and the length of the string can vary. So, for instance, for a string of length 3, the possible strings would be AAA, AAB, AAC, etc., but would not include BAA or CAA. I figured out a way using itertools.product(), but it is very computationally expensive. The easiest way to do this is simply using nested for loops. For instance, to generate all strings of length four:

alphabet = ["A","C","D","E","F","G","H","I","K","L",
            "M","N","P","Q","R","S","T","V","W","Y"]
combos = []
for a in range(len(alphabet)):
    for b in range(a,len(alphabet)):
        for c in range(b,len(alphabet)):
            for d in range(c,len(alphabet)):
                combos.append(alphabet[a] + alphabet[b] + alphabet[c] + alphabet[d])

Now, this can easily be done for any length string by changing the number of for loops. Given the for loop sequence itself is quite predictable, is there are way to simplify this code instead of having if length == 3 run three for loops and if length == 4 run four loops instead? The only way I can think to do it right now is a bunch of if-elif statements:

if length == 3:
    for a in range(len(alphabet)):
        for b in range(a,len(alphabet)):
            for c in range(b,len(alphabet)):
                combos.append(alphabet[a] + alphabet[b] + alphabet[c])
elif length == 4:
    for a in range(len(alphabet)):
        for b in range(a,len(alphabet)):
            for c in range(b,len(alphabet)):
                for d in range(c,len(alphabet)):
                    combos.append(alphabet[a] + alphabet[b] + alphabet[c] + alphabet[d])

Is there any easier way than just covering a bunch of possible values of length?

like image 716
LordHadron Avatar asked Sep 28 '22 00:09

LordHadron


2 Answers

IIUC, you can simply use itertools.combinations_with_replacement.

>>> list(map(''.join, combinations_with_replacement(["a","b","c"],2)))
['aa', 'ab', 'ac', 'bb', 'bc', 'cc']
>>> list(map(''.join, combinations_with_replacement(["a","b","c"],3)))
['aaa', 'aab', 'aac', 'abb', 'abc', 'acc', 'bbb', 'bbc', 'bcc', 'ccc']
>>> list(map(''.join, combinations_with_replacement(alphabet,4))) == orig(alphabet)
True

(where orig is simply your original code wrapped into a function).

like image 92
DSM Avatar answered Oct 17 '22 16:10

DSM


  1. the code for itertools.product does exactly what you want and is much more efficient that nested loops

  2. i suspect that what you really want is itertools.combinations_with_replacement

like image 1
yurib Avatar answered Oct 17 '22 15:10

yurib