在Python中找到所有n个正数加起来等于k个的所有组合? [英] Find all combinations of `n` positive numbers adding up to `k` in Python?

查看:517
本文介绍了在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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆