Python: как получить возможные комбинации клавиш в dict - PullRequest
Новая
       46

Python: как получить возможные комбинации клавиш в dict

0 голосов
/ 12 мая 2018

С учетом словарного запаса: {'A': 3, 'B': 4, 'C': 5, 'AB':6} и предложения, которое должно быть сегментировано: ABCAB.

Мне нужно создать все возможные комбинации этого предложения, такие как [['A', 'B', 'C', 'A', 'B'], ['A', 'B', 'C', 'AB'], ['AB', 'C', 'AB'], ['AB', 'C', 'A', 'B']]

Вот что у меня есть: 

def find_words(sentence):   
    for i in range(len(sentence)):

        for word_length in range(1, max_word_length + 1):

            word = sentence[i:i+word_length]
            print(word)

            if word not in test_dict:
                continue

            if i + word_length <= len(sentence):
                if word.startswith(sentence[0]) and word not in words and word not in ''.join(words):
                    words.append(word)
                else:
                    continue

                next_position = i + word_length

                if next_position >= len(sentence):
                    continue
                else:
                    find_ngrams(sentence[next_position:])

    return words

Но он возвращает мне только один список.

Я также искал что-то полезное в itertools , но не смог найти что-то полезное. Возможно, я пропустил это.

Ответы [ 3 ]

0 голосов
/ 12 мая 2018

Хотя это не самое эффективное решение, оно должно работать: 

from itertools import product

dic = {'A': 3, 'B': 4, 'C': 5, 'AB': 6}
choices = list(dic.keys())
prod = []

for a in range(1, len(choices)+2):
    prod = prod + list(product(choices, repeat=a))

result = list(filter(lambda x: ''.join(x) == ''.join(choices), prod))
print(result) 

# prints [('AB', 'C', 'AB'), ('A', 'B', 'C', 'AB'), ('AB', 'C', 'A', 'B'), ('A', 'B', 'C', 'A', 'B')]
0 голосов
/ 12 мая 2018

Попробуйте все возможные префиксы и рекурсивно сделайте то же самое для остальной части предложения. 

VOC = {'A', 'B', 'C', 'AB'}  # could be a dict

def parse(snt):
    if snt == '': 
        yield []
    for w in VOC:
        if snt.startswith(w):
            for rest in parse(snt[len(w):]):
                yield [w] + rest

print(list(parse('ABCAB')))

# [['AB', 'C', 'AB'], ['AB', 'C', 'A', 'B'],
# ['A', 'B', 'C', 'AB'], ['A', 'B', 'C', 'A', 'B']]
0 голосов
/ 12 мая 2018

Используйте перестановки itertools, чтобы получить все уникальные комбинации. 

d ={'A': 3, 'B': 4, 'C': 5, 'AB':6}

l = [k for k, v in d.items()]

print(list(itertools.permutations(l)))

[('A', 'B', 'C', 'AB'), ('A', 'B', 'AB', 'C'), ('A', 'C', 'B', 'AB'), ('A', 'C', 'AB', 'B'), ('A', 'AB', 'B', 'C'), ('A', 'AB', 'C', 'B'), ('B', 'A', 'C', 'AB'), ('B', 'A', 'AB', 'C'), ('B', 'C', 'A', 'AB'), ('B', 'C', 'AB', 'A'), ('B', 'AB', 'A', 'C'), ('B', 'AB', 'C', 'A'), ('C', 'A', 'B', 'AB'), ('C', 'A', 'AB', 'B'), ('C', 'B', 'A', 'AB'), ('C', 'B', 'AB', 'A'), ('C', 'AB', 'A', 'B'), ('C', 'AB', 'B', 'A'), ('AB', 'A', 'B', 'C'), ('AB', 'A', 'C', 'B'), ('AB', 'B', 'A', 'C'), ('AB', 'B', 'C', 'A'), ('AB', 'C', 'A', 'B'), ('AB', 'C', 'B', 'A')]

...