CODEWITHSUNDEEP
pythonstringlistcombinations
ooj-001
ooj-001

Reputation: 180

Given a word and a number for each letter of this word, how to create a full tree of every combinations?

Let's say I have the word "stack" and for each of its letters there is a number that will define the number of times the letter has to be repeated. In a JSON file I would have the following:

{
   "s": 4,
   "t": 3,
   "a": 2,
   "c": 5,
   "k": 2
}

From this I would like to generate the complete tree of every possible combinations, namely:

Depth 1: stack
Depth 2: stack, sstack, ssstack, sssstack
Depth 3: stack, sttack, stttack, sstack, ssttack, sstttack,ssstack, sssttack, ssstttack, sssstack, ssssttack, sssstttack
Depth 4: ... with 'a'
Depth 5: ... with 'c'
Depth 6: ... with 'k'

This would give 4*3*2*5*2 = 240 possibilities. Also, I have these functions from someone I asked few days ago here, and on which I modified a little bit:

def all_combinations(itr):
    lst = list(itr)
    for r in range(1, len(lst) + 1): 
        for perm in itertools.combinations(lst, r=r):
            yield perm 

def all_repeats(n, letters, word):
    for rep in all_combinations(letters):
        yield ''.join(char * n if char in rep else char for char in word)

Which gives me:

word = 'stack'
for i in range(1,5):
    liste.append(''.join(list(all_repeats(i, ['s'], word))))

Output: ['stack', 'sstack', 'ssstack', 'sssstack']

From this, how can I recursively call this function to create all possibilities, given the couple (letter, number) in the JSON file?

Upvotes: 0

Views: 122

Answers (2)

Ajax1234
Ajax1234

Reputation: 71461

You can also use recursion:

data = {'s': 4, 't': 3, 'a': 2, 'c': 5, 'k': 2}
def combos(d):
  yield ''.join(map(''.join, d))
  for i in data:
     if any(c[0] == i and len(c) < data[i] for c in d):
        yield from combos([c+[i] if c[0] == i and len(c) < data[i] else c for c in d])

Upvotes: 1

Sam Mason
Sam Mason

Reputation: 16194

a couple of versions, first we work with a list because it's easier to index

options = [
   ("s", 4),
   ("t", 3),
   ("a", 2),
   ("c", 5),
   ("k", 2),
]

now we can get a long form version, to help understand what's going on:

output = ['']

for letter, repeats in options:
    tmp = []
    for num in range(repeats):
        postfix = letter * (num+1)
        for cur in output:
            tmp.append(cur + postfix)
    output = tmp

if you print(output) you'll get what you expect. I'd suggest running in a debugger or inserting lots of print statements to understand what's happening

as a second version, we can shorten this all down using itertools as:

from itertools import product

tmp = [[l*(i+1) for i in range(num)] for l, num in options]
output = [''.join(l) for l in product(*tmp)]

you could even put it all on one line, but it becomes a little too unreadable in my opinion

a recursive solution would fit nicely as well, but I'll leave that to you

Upvotes: 1

Related Questions