如何编写最有效的算法来找到字符串列表中所有可能的排列

Question

下面的代码输出字符串列表中所有可能的排列数，这些排列在使用递归求解的常量长度内。假设list_1 = ["A"]和list_2 = ["BB"]的长度为5，则：

所有可能的组合都是：

A A A A A
A A A BB
A A BB A
A BB A A
BB A A A
A BB BB
BB A BB
BB BB A

现在，如果我将列表更改为list_1 = ["A"], list_2 = ["BB"], list_3 = ["CCCC"], list_4 = ["DDDDDDDD"]长度为256。这需要太多的时间来回应。我想知道如何加快代码的速度。

list_1 = ["A"]
list_2 = ["BB"]
list_3 = ["CCCC"]
list_4 = ["DDDDDDDD"]
size = 256
strs = list_1 + list_2 + list_3 + list_4
res = []
def helper(strs, size, cur, res):
if size == 0:
res.append(cur)
return
if size < 0:
return
for s in strs:
helper(strs, size-len(s), cur+[s], res)
helper(strs, size, [], res)
print(len(res))

Answer 1

如果你真的只对排列的数量感兴趣，你可以使用记忆(动态编程(：

import functools

@functools.lru_cache(maxsize=None)
def num_permutations_of_length(l, k):
if k < 0:
return 0
elif k == 0:
return 1
total = 0
for i in range(len(l)):
total += num_permutations_of_length(l, k-l[i])
return total

def main():
print(num_permutations_of_length((1,2,4,8), 256))

if __name__ == '__main__':
main()

只需输入字符串长度的元组，而不是字符串本身。

此输出

1038196252619804983509071079561190746560608760522777019070489047

顺便说一下。