递归-具有不同计数约束的两个字母的所有组合的列表
递归-具有不同计数约束的两个字母的所有组合的列表
提问于 2020-08-09 17:23:33
我想打印一个包含所有可能的方式来订购两个字母的列表，例如'a'，'b‘，其中每个字母必须分别包含n，k次。
例如，如果我们有字母'a', 'b'和n=1, k=2，那么我们应该有如下列表：
[
'abb',
'bab',
'bba',
]我设法使用字符串'a'*n+'b'*k上的递归排列来解决这个问题，但是这是非常低效率的，当我们在n/k上达到8-10时，程序就耗尽了内存。
如何使用递归(没有迭代工具)在python中解决这个问题？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-08-09 17:47:55
因为它很有教育意义，所以我将给您一个不同的谜题;-)这对于递归生成器来说非常容易：
def crunch(letters, n, k):
a, b = letters
def inner(n, k):
if n == 0 == k:
yield ""
# It starts with a or it starts with b.
if n:
for tail in inner(n-1, k):
yield a + tail
if k:
for tail in inner(n, k-1):
yield b + tail
return inner(n, k)然后，例如，
>>> list(crunch('ab', 1, 2))
['abb', 'bab', 'bba']
>>> list(crunch('ab', 2, 1))
['aab', 'aba', 'baa']
>>> list(crunch('ab', 1, 0))
['a']
>>> list(crunch('ab', 1, 1))
['ab', 'ba']
>>> list(crunch('ab', 2, 2))
['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']因此，有一个难题:你怎么能重写它而不使用生成器呢？在现实生活中，没有人会费心摆脱发电机。但是，在现实生活中，任何人都会首先使用itertools.combinations() (由于n+k的长度，您选择了"a“应该去的n位置--或者相当于"b”应该去的k位置)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/63329302
复制相关文章
相似问题
腾讯云开发者
