Python: 如何获取字典中可能的键组合

Question

给定一个词汇字典：{'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

但它 returns 我只有一个列表。

我也在 itertools 中寻找有用的东西，但我找不到任何明显有用的东西。不过可能错过了。

Answer 1

使用 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')]

Answer 2

虽然这不是最有效的解决方案，但应该可行：

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

Answer 3

尝试所有可能的前缀，并对句子的其余部分递归地做同样的事情。

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

Python: 如何获取字典中可能的键组合

Python: How to get possible combinations of keys in dict

python

string

list

python-3.x

text-segmentation