gpt4 book ai didi

Python:从具有字符限制的列表中生成所有可能的序列组合

转载 作者:太空狗 更新时间:2023-10-30 01:19:06 25 4
gpt4 key购买 nike

我的问题和this question一模一样.我有字符数组(列表)。我想从该列表中获取所有可能的序列组合,但具有字符限制(例如:最多 2 个字符)。此外,排列行中不能重复单个字符:

chars = ['a', 'b', 'c', 'd']

# output
output = [['a', 'b', 'c', 'd'],
['ab', 'c', 'd'],
['a', 'bc', 'd'],
['a', 'b', 'cd'],
['ab', 'cd'],
['abc', 'd'], # this one will be exempted
['a', 'bcd'], # this one will be exempted
['abcd']] # this one will be exempted

我知道我可以在生成和构建序列时检查条件以省略超出限制的字符组合。但它会增加运行时间。我的目的是减少现有的执行时间

如果没有字符数限制,组合将像 2^(N-1) 一样生成。如果列表超过 15 个字符,则执行程序的时间会太长。因此,我想通过字符限制减少组合计数。

优先考虑的是性能。我已经研究并尝试了两天,但没有成功。

最佳答案

一种方法是遍历输入列表并逐渐建立组合。在每一步中,下一个字符都从输入列表中取出并添加到先前生成的组合中。

from collections import defaultdict

def make_combinations(seq, maxlen):
# memo is a dict of {length_of_last_word: list_of_combinations}
memo = defaultdict(list)
memo[1] = [[seq[0]]] # put the first character into the memo

seq_iter = iter(seq)
next(seq_iter) # skip the first character
for char in seq_iter:
new_memo = defaultdict(list)

# iterate over the memo and expand it
for wordlen, combos in memo.items():
# add the current character as a separate word
new_memo[1].extend(combo + [char] for combo in combos)

# if the maximum word length isn't reached yet, add a character to the last word
if wordlen < maxlen:
word = combos[0][-1] + char

new_memo[wordlen+1] = newcombos = []
for combo in combos:
combo[-1] = word # overwrite the last word with a longer one
newcombos.append(combo)

memo = new_memo

# flatten the memo into a list and return it
return [combo for combos in memo.values() for combo in combos]

输出:

[['a', 'b', 'c', 'd'], ['ab', 'c', 'd'], ['a', 'bc', 'd'],
['a', 'b', 'cd'], ['ab', 'cd']]

对于短输入,此实现比朴素的 itertools.product 方法慢:

input: a b c d
maxlen: 2
iterations: 10000

itertools.product: 0.11653625800136069 seconds
make_combinations: 0.16573870600041118 seconds

但当输入列表较长时,它会很快恢复:

input: a b c d e f g h i j k
maxlen: 2
iterations: 10000

itertools.product: 6.9087735799985240 seconds
make_combinations: 1.2037671390007745 seconds

关于Python:从具有字符限制的列表中生成所有可能的序列组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49716403/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com