迭代算法生成具有任意数量列表的所有组合

Question

我有一个问题试图自己解决，但我不确定是否有更好的算法来解决这个问题。假设我有一个完整字母表的dict。我可以调用传递字符串的函数，该字符串指示与要用于生成输出的列表相关的键。我可以多次添加同一个密钥。我想在它们之间生成所有可能的组合，并在没有递归的情况下解决它。

我试着用下面的暴力方法自己解决这个问题，但我想知道是否有更好的方法。

我的尝试如下：

words_dict = {
2: ['a', 'b', 'c'],
3: ['d', 'e', 'f'],
4: ['g', 'h', 'i'],
5: ['j', 'k', 'l'],
6: ['m', 'n', 'o'],
7: ['p', 'q', 'r'],
8: ['t', 'u', 'v', 'w'],
9: ['x', 'y', 'z'],
}

def generate_combinations(numbers):
words_to_expand = words_dict[int(numbers[0])]
for i in range(1, len(numbers)):
letters_list = words_dict[int(numbers[i])]
aux_words_expanded = []
for incomplete_word in words_to_expand:
for letter_to_combine in letters_list:
expanded_word = incomplete_word + letter_to_combine
aux_words_expanded.append(expanded_word)
words_to_expand = aux_words_expanded
print(words_to_expand)
return words_to_expand
pass

generate_combinations('234')

Answer 1

@MmBaguette的回答为您指明了正确的方向。它建议使用itertools

完整的功能类似于：

def generate_combinations(numbers):
words = []
indexes = (int(val) for val in numbers)
letter_groups = [words_dict[idx] for idx in indexes]
for entry in itertools.product(*letter_groups):
words.append("".join(entry))
print(words)
print(len(words))

甚至更短：

def generate_combinations(numbers):
indexes = (int(val) for val in numbers)
letter_groups = [words_dict[idx] for idx in indexes]
words = list("".join(entry)
for entry in itertools.product(*letter_groups))
print(words)
print(len(words))

Answer 2

这里有一种更Python的方法来实现

import itertools
my_list = ["a", "b", "c", "d"]
itertools.combinations(my_list) #returns generator of combinations
itertools.permutations(my_list, 3) #same but with length of results specified