在Python中找到所有n个正数加起来等于k个的所有组合? [英] Find all combinations of `n` positive numbers adding up to `k` in Python?
本文介绍了在Python中找到所有n个正数加起来等于k个的所有组合?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我将如何有效地找到 n
个正整数的所有可能组合,这些总和等于一个给定的 k
Python吗?
How would I efficiently find all the possible combinations of n
positive integers adding up to a given number k
in Python?
我知道我可以通过过滤所有可能的组合来解决此问题:
I know I could solve this by filtering all the possible combinations:
import itertools
def to_sum_k(n, k):
for i in itertools.product(range(1, k - n + 2), repeat=n):
if sum(i) == k:
yield i
print(list(to_sum_k(3, 5)))
# [(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]
我已经看到类似的东西已经被抽象地讨论过了此处,但我看不到将其转换为代码的简单方法。
I have seen something similar has been discussed in abstract way here, but I do not see a simple way of translating this into code.
另外,相对于递归,我更喜欢迭代解决方案。
Also, I would prefer an iterative solution over a recursive one.
推荐答案
基于此:
def to_sum_k_rec(n, k):
if n == 1:
yield (k,)
else:
for x in range(1, k):
for i in to_sum_k_rec(n - 1, k - x):
yield (x,) + i
print(list(to_sum_k_rec(3, 5)))
# [(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]
和一个迭代项:
And an iterative one:
import itertools
def to_sum_k_iter(n, k):
index = [0] * (n + 1)
index[-1] = k
for j in itertools.combinations(range(1, k), n - 1):
index[1:-1] = j
yield tuple(index[i + 1] - index[i] for i in range(n))
print(list(to_sum_k_iter(3, 5)))
# [(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]
在时间上,递归解决方案似乎是最快的:
Time-wise, the recursive solution seems to be fastest:
%timeit list(to_sum_k_OP(4, 100))
# 1 loop, best of 3: 13.9 s per loop
%timeit list(to_sum_k_rec(4, 100))
# 10 loops, best of 3: 101 ms per loop
%timeit list(to_sum_k_iter(4, 100))
# 1 loop, best of 3: 201 ms per loop
这篇关于在Python中找到所有n个正数加起来等于k个的所有组合?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文