Учитывая слово и число для каждой буквы этого слова, как создать полное дерево каждой комбинации? - PullRequest
Новая
       8

Учитывая слово и число для каждой буквы этого слова, как создать полное дерево каждой комбинации?

0 голосов
/ 16 апреля 2019

Допустим, у меня есть слово «стопка», и для каждой из его букв есть число, которое будет определять количество повторений буквы.В файле JSON у меня будет следующее: 

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

Из этого я хотел бы создать полное дерево всех возможных комбинаций, а именно: 

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'

Это даст 4 *3 * 2 * 5 * 2 = 240 возможностей.Кроме того, у меня есть эти функции от кого-то, кого я спросил здесь несколько дней назад, и который я немного изменил: 

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)

Что дает мне: 

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

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

Отсюда, какя могу рекурсивно вызвать эту функцию, чтобы создать все возможности, учитывая пару (букву, число) в файле JSON?

Ответы [ 2 ]

1 голос
/ 16 апреля 2019

Вы также можете использовать рекурсию: 

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])
1 голос
/ 16 апреля 2019

пара версий, сначала мы работаем со списком, потому что его легче индексировать 

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

теперь мы можем получить длинную версию формы, чтобы помочь понять, что происходит: 

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

если вы print(output) вы получите то, что ожидаете. Я бы посоветовал запустить в отладчике или вставить множество print операторов, чтобы понять, что происходит

как вторая версия, мы можем сократить все это, используя itertools как: 

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)]

Вы могли бы даже поместить все это в одну строку, но, на мой взгляд, это становится слишком нечитаемым

рекурсивное решение тоже подойдет, но я оставлю это вам

...