I have troubles with implementing distributions in python

Question

I want to write the function all_possible(word, n) where word is string with no spaces in it, and n is number of |'s. I need to put |'s in  word so that my output is list of all possible strings with inserted |'s between characters.
Example:
letters = 'abcdefghijklmnopqrstuvwxyz'
print(all_possible(letters, 7)
>> ['a|b|c|d|e|f|g|hijklmnopqrstuvwxyz', 'a|b|c|d|e|f|gh|ijklmnopqrstuvwxyz', 'a|b|c|d|e|f|ghi|jklmnopqrstuvwxyz'...]

This is what I have so far:
def all_possible(word, n):
    word = list(word)
    l = ['|'] * n
    k = 1
    for c in l:
        word.insert(k, c)
        k += 2
    word = ''.join(word)
    return word

Any help now?

Mark · Answer

You are not going to be able to do this with a single loop. You can try using itertools.combination(). For example, combos = combinations(range(1, 26), 7) will give you an iterator that lists out all the indices of the letters you should insert the bar before (with the help of enumerate to keep track of how many letters you're adding:
letters = 'abcdefghijklmnopqrstuvwxyz'

combos = combinations(range(1, 26), 2)

for indices in combos:
    l = list(letters)
    for i, n in enumerate(indices):
        l.insert(i + n, '|')
    print("".join(l))

Prints:
a|b|cdefghijklmnopqrstuvwxyz
a|bc|defghijklmnopqrstuvwxyz
a|bcd|efghijklmnopqrstuvwxyz
...
abcdefghijklmnopqrstuvwx|y|z

You can change the 2 to 7, but be warned, it is a lot of combinations.
You can also do this recursively with the insight that inserting a single bar at between each letter is a single loop. Inserting 2 bars is the same as inserting a bar and then doing the same for the string left after the bar.
def insert_bars(s, n):
    if n == 0:
        yield s
    else:
        for i in range(1, len(s) - n+1):
            for rest in insert_bars(s[i:], n-1):
                yield s[:i] + '|' + rest
l = list(insert_bars(letters, 7))

l is length 480700:
['a|b|c|d|e|f|gh|ijklmnopqrstuvwxyz',
 'a|b|c|d|e|f|ghi|jklmnopqrstuvwxyz',
 'a|b|c|d|e|f|ghij|klmnopqrstuvwxyz',
 'a|b|c|d|e|f|ghijk|lmnopqrstuvwxyz',
 'a|b|c|d|e|f|ghijkl|mnopqrstuvwxyz',
 'a|b|c|d|e|f|ghijklm|nopqrstuvwxyz',
 'a|b|c|d|e|f|ghijklmn|opqrstuvwxyz',
 'a|b|c|d|e|f|ghijklmno|pqrstuvwxyz',
 ...
 'abcdefghijklmnopqr|s|t|u|v|w|x|yz',
 'abcdefghijklmnopqr|s|t|u|v|w|xy|z',
 'abcdefghijklmnopqr|s|t|u|v|wx|y|z',
 'abcdefghijklmnopqr|s|t|u|vw|x|y|z',
 'abcdefghijklmnopqr|s|t|uv|w|x|y|z',
 'abcdefghijklmnopqr|s|tu|v|w|x|y|z',
 'abcdefghijklmnopqr|st|u|v|w|x|y|z',
 'abcdefghijklmnopqrs|t|u|v|w|x|y|z']

I have troubles with implementing distributions in python

One Answer

Add your own answers!

Ask a Question