英文:
Python - Count all combinations of K numbers from 1-N whose sum is equal to N
问题
如何计算所有从1到n中选取k个数字的组合，使它们的总和等于n？例如，对于n = 10，k = 3，我们有(1, 2, 7)，(1, 3, 6)，(1, 4, 5)，(2, 3, 5)。
我尝试过使用itertools.combination，但对于大数字而言，它增长得非常快。
英文:
How do i count all combinations of k numbers from 1-n whose sum is equal to n? Like for n = 10, k = 3, we have (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 3, 5)
I've tried using itertools.combination but it grows really fast for big numbers
答案1
得分: 2
我们可以用 k 个不同的正整数制造出的最小数是 choose(k+1, 2)。
令 r(n,k) = n - choose(k+1, 2)。
那么从 k 个不同的整数中形成 n 的方式数量等于将 k 个非负、不一定不同的整数相加以得到 r(n,k) 的方式数量。思路是从 1, 2, 3, ..., k 开始，然后以非递减的方式分配 r(n,k) 到这些起始整数上。
例如，对于 10, 3：
1 + 2 + 3 = choose(4,2) = 6，所以 r(10,3) = 10-6 = 4。
4 = 0+0+4, 0+1+3, 0+2+2, 1+1+2
(1,2,3) + (0,0,4) = (1,2,7)
(1,2,3) + (0,1,3) = (1,3,6)
(1,2,3) + (0,2,2) = (1,4,5)
(1,2,3) + (1,1,2) = (2,3,5)
所以我们将问题简化为计算 k 个非负整数相加得到 r(n,k) 的方式数量。在[这里][1]有答案。
Ruby 代码（包括实用函数）：
def choose(n, k)
return 0 if k > n
result = 1
1.upto(k) do |d|
result *= n
result /= d
n -= 1
end
return result
end
def count_partitions_nozeroes(n, k, cache = {})
return 1 if k==0 && n==0
return 0 if n <= 0 || k <= 0
# 检查结果是否已被记忆
if cache.key?([n, k])
return cache[[n, k]]
end
# 计算结果
result = count_partitions_nozeroes(n-1, k-1, cache) + count_partitions_nozeroes(n-k, k, cache)
# 记忆结果以备将来使用
cache[[n, k]] = result
return result
end
def count_partitions_zeros(n,k)
return count_partitions_nozeroes(n+k, k)
end
def solve(n,k)
r = n - choose(k+1,2)
return count_partitions_zeros(r,k)
end
示例结果：
> solve(10,3)
=> 4
> solve(200,10)
=> 98762607
> solve(2000,10)
=> 343161146717017732
> solve(2000,100) # 没有解决方案是正确的
=> 0
> solve(2000,40)
=> 2470516759655914864269838818691
> solve(5000,50)
=> 961911722856534054414857561149346788190620561928079
> solve(9000,100)
=> 74438274524772625088229884845232647085568457172246625852148213
这是一个更简单的 Ruby 版本，避免了递归（其他方法不变）。它给出与上述相同的结果。下面展示了一些更大数字的结果。这个版本的复杂度是 O(n*r)。
def count_partitions_nozeroes(n, k)
n_to_k_to_count = Hash.new{|h, n| h[n] = Hash.new{|h2, k| h2[k] = 0}}
n_to_k_to_count[n][k] = 1
(n).downto(1) do |cur_n|
n_to_k_to_count.delete(cur_n + 1) # 删除旧键以节省空间
n_to_k_to_count[cur_n].keys.each do |cur_k|
n_to_k_to_count[cur_n - 1][cur_k - 1] += n_to_k_to_count[cur_n][cur_k] if cur_n >= 1 && cur_k >= 1
n_to_k_to_count[cur_n - cur_k][cur_k] += n_to_k_to_count[cur_n][cur_k] if cur_n >= cur_k && cur_k >= 0
end
end
return n_to_k_to_count[0][0]
end
示例结果：
> solve(10_000, 100)
=> 274235043379646744332574760930015102932669961381003514201948469288939
> solve(20_000, 100)
=> 7299696028160228272878582999080106323327610318395689691894033570930310212378988634117070675146218304092757
> solve(30_000, 100)
=> 272832080760303721646457320315409638838332197621252917061852201523368622283328266190355855228845140740972789576932357443034296
> solve(40_000, 200)
=> 1207940070190155086319681977786735094825631330761751426889808559216057614938892266960158470822904722575922933920904751545295375665942760497367
> solve(100_000, 200)
=> 13051215883535384859396062192804954511590479767894013629996324213956689010966899432038449004533035681835942448619230013858515264041486939129111486281204426757510182253404556858519289275662797170197384965998425620735381780708992863774464769
> solve(1_000_000, 200) # 变得非常慢；3.5 分钟
=> 428880856178598710720148624933560494061607079247573557573778067722670591454531582929217788942407876811003263888596981076595546473767426764847052870957098719920895206333233661830556744660481006393060648337767876434226805997102371290790505388472758064159747958795845134023811256732973394383039538732268993828238034324648751357082834429815006950891214256221354725682849015159958577756592134668188434645414960901194459625871943042
<details>
<summary>英文:</summary>
The smallest number we can make with k distinct positive integers is choose(k+1, 2).
Let r(n,k) = n - choose(k+1, 2).
Then the count of ways of forming n from k distinct integers is equal to the count of ways of summing k nonnegative non-necessarily-distinct integers to get r(n,k). The idea is we start with 1, 2, 3, ..., k, and then allocate r(n,k) to these starting integers in a nondecreasing manner.
E.g., 10, 3:
1 + 2 + 3 = choose(4,2) = 6, so r(10,3) = 10-6 = 4.
4 = 0+0+4, 0+1+3, 0+2+2, 1+1+2
(1,2,3) + (0,0,4) = (1,2,7)
(1,2,3) + (0,1,3) = (1,3,6)
(1,2,3) + (0,2,2) = (1,4,5)
(1,2,3) + (1,1,2) = (2,3,5)
So we've reduce the problem to counting the number of ways of summing k nonnegative integers to get r(n,k). Answered [here][1]
Ruby code (including util functions):
def choose(n, k)
return 0 if k > n
result = 1
1.upto(k) do |d|
result *= n
result /= d
n -= 1
end
return result
end
def count_partitions_nozeroes(n, k, cache = {})
return 1 if k==0 && n==0
return 0 if n <= 0 || k <= 0
# Check if the result is already memoized
if cache.key?([n, k])
return cache[[n, k]]
end
# Calculate the result
result = count_partitions_nozeroes(n-1, k-1, cache) + count_partitions_nozeroes(n-k, k, cache)
# Memoize the result for future use
cache[[n, k]] = result
return result
end
def count_partitions_zeros(n,k)
return count_partitions_nozeroes(n+k, k)
end
def solve(n,k)
r = n - choose(k+1,2)
return count_partitions_zeros(r,k)
end
Sample results
> solve(10,3)
=> 4
> solve(200,10)
=> 98762607
> solve(2000,10)
=> 343161146717017732
> solve(2000,100) # correct that there's no solution
=> 0
> solve(2000,40)
=> 2470516759655914864269838818691
> solve(5000,50)
=> 961911722856534054414857561149346788190620561928079
> solve(9000,100)
=> 74438274524772625088229884845232647085568457172246625852148213
Here's a simpler Ruby version that avoids recursion (other methods unchanged). It gives the same results as above. A few results for larger numbers shown below. This version is O(n*r).
def count_partitions_nozeroes(n, k)
n_to_k_to_count = Hash.new{|h, n| h[n] = Hash.new{|h2, k| h2[k] = 0}}
n_to_k_to_count[n][k] = 1
(n).downto(1) do |cur_n|
n_to_k_to_count.delete(cur_n + 1) # delete old keys to save space
n_to_k_to_count[cur_n].keys.each do |cur_k|
n_to_k_to_count[cur_n - 1][cur_k - 1] += n_to_k_to_count[cur_n][cur_k] if cur_n >= 1 && cur_k >= 1
n_to_k_to_count[cur_n - cur_k][cur_k] += n_to_k_to_count[cur_n][cur_k] if cur_n >= cur_k && cur_k >= 0
end
end
return n_to_k_to_count[0][0]
end
Sample results
> solve(10_000, 100)
=> 274235043379646744332574760930015102932669961381003514201948469288939
> solve(20_000, 100)
=> 7299696028160228272878582999080106323327610318395689691894033570930310212378988634117070675146218304092757
> solve(30_000, 100)
=> 272832080760303721646457320315409638838332197621252917061852201523368622283328266190355855228845140740972789576932357443034296
> solve(40_000, 200)
=> 1207940070190155086319681977786735094825631330761751426889808559216057614938892266960158470822904722575922933920904751545295375665942760497367
> solve(100_000, 200)
=> 13051215883535384859396062192804954511590479767894013629996324213956689010966899432038449004533035681835942448619230013858515264041486939129111486281204426757510182253404556858519289275662797170197384965998425620735381780708992863774464769
> solve(1_000_000, 200) # getting painfully slow; 3.5 mins
=> 42888085617859871072014862493356049406160707924757355757377806772267059145453158292921778894240787681100326388859698107659554647376742676484705287095709871992089520633323366183055674466048100639306064833776787643422680599710237129079050538847275806415974795879584513402381125673297339438303953873226899382823803432464875135708283442981500695089121425622135472568284901515995857775659213466818843464541496090119445962587194304280691087464026800781
[1]: https://math.stackexchange.com/questions/217597/number-of-ways-to-write-n-as-a-sum-of-k-nonnegative-integers
</details>
# 答案2
**得分**: 1
使用带有缓存的递归方法可以在合理的时间内产生结果：
```python
from functools import lru_cache
@lru_cache(None)
def countNK(n, k, t=None):
t = n if t is None else t # 跟踪目标部分和
if k == 0: return int(t==0) # 空集可以求和为零
if t < 1: return 0 # 仅有效目标
if k > n: return 0 # 值不够
return countNK(n-1, k, t) + countNK(n-1, k-1, t-n) # 合并计数
- 递归需要以逐渐减小的
n值来寻找目标 - 它还需要在从目标中删除每个值后对较短的组合进行相同的操作
- 这将多次合并相同的计算，因此需要缓存
输出：
print(countNK(10,3)) # 4
print(countNK(200,10)) # 98762607
如果您需要处理较大的n值（例如500+），您需要增加递归限制或将函数转换为迭代循环。
英文:
A recursive approach with caching can produce results in a reasonable time:
from functools import lru_cache
@lru_cache(None)
def countNK(n,k,t=None):
t = n if t is None else t # track target partial sum
if k == 0: return int(t==0) # empty set can sum to zero
if t < 1 : return 0 # valid target only
if k > n : return 0 # not enough values
return countNK(n-1,k,t)+countNK(n-1,k-1,t-n) # combine counts
- recursion needs to aim for a target using progressively smaller values of
n - it also needs to do that for shorter combinations after removing each value from the target
- this will combine the same calculations multiple times, hence the caching
...
output:
print(countNK(10,3)) # 4
print(countNK(200,10)) # 98762607
If you need to process large values of n (e.g. 500+), you'll either need to increase the recursion limit or convert the function to an iterative loop
答案3
得分: 1
以下是您提供的代码的中文翻译部分：
def Kelly(n, k):
if k == 0:
return 1 if n == 0 else 0
@cache
def c(n, k):
if n < k * (k+1) // 2:
return 0
if k == 1:
return 1
n -= k
return c(n, k) + c(n, k-1)
return c(n, k)
# 预先计算用于 "n < ..." 基本情况的界限
def Kelly2(n, k):
if k == 0:
return 1 if n == 0 else 0
min_n_for_k = list(accumulate(range(k+1)))
@cache
def c(n, k):
if n < min_n_for_k[k]:
return 0
if k == 1:
return 1
n -= k
return c(n, k) + c(n, k-1)
return c(n, k)
def Alain(n, k):
@lru_cache(None)
def countNK(n,k,t=None):
t = n if t is None else t # 跟踪目标部分和
if k == 0: return int(t==0) # 空集可以总和为零
if t < 1 : return 0 # 仅有效目标
if k > n : return 0 # 不足够的值
return countNK(n-1,k,t)+countNK(n-1,k-1,t-n) # 合并计数
return countNK(n, k)
def Dave_translated_by_Kelly(n, k):
def choose(n, k):
if k > n: return 0
result = 1
for d in range(1, k+1):
result *= n
result //= d
n -= 1
return result
def count_partitions_nozeroes(n, k, cache = {}):
if k==0 and n==0: return 1
if n <= 0 or k <= 0: return 0
# 检查结果是否已被记忆
if (n, k) in cache:
return cache[n, k]
# 计算结果
result = count_partitions_nozeroes(n-1, k-1, cache) + count_partitions_nozeroes(n-k, k, cache)
# 为将来的使用记忆结果
cache[n, k] = result
return result
def count_partitions_zeros(n,k):
return count_partitions_nozeroes(n+k, k)
def solve(n,k):
r = n - choose(k+1,2)
return count_partitions_zeros(r,k)
return solve(n, k)
big = False
funcs = Alain, Kelly, Kelly2, Dave_translated_by_Kelly
if big:
funcs = funcs[1:]
from functools import lru_cache, cache
from itertools import accumulate
from time import perf_counter as time
from statistics import mean, stdev
import sys
import gc
# 正确性
for n in range(51):
for k in range(51):
expect = funcs[0](n, k)
for f in funcs[1:]:
result = f(n, k)
assert result == expect
# 速度
sys.setrecursionlimit(20000)
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e3 for t in sorted(times[f])[:5]]
return f'{mean(ts):5.1f} ± {stdev(ts):4.1f} ms '
for _ in range(25):
for f in funcs:
gc.collect()
t0 = time()
if big:
f(9000, 100)
else:
for k in range(101):
f(100, k)
times[f].append(time() - t0)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)
请注意，由于代码段包含特定的编程注释和功能，因此某些部分的翻译可能会失去一些上下文，但我已尽力保持了代码的完整性和一致性。
英文:
Benchmark with n=100 and all k from 0 to 100, Kelly* are my solutions:
2.5 ± 0.1 ms Kelly
2.8 ± 0.2 ms Kelly2
3.5 ± 0.2 ms Dave_translated_by_Kelly
295.0 ± 23.7 ms Alain
Let c(n, k) be the number of combinations with sum n with k different numbers 1 or larger.
We get: c(n, k) = c(n-k, k) + c(n-k, k-1)
You want sum n with k different numbers 1 or larger. You either use the number 1 in the combination or you don't.
- If you don't use 1, then you want sum n with k different numbers 2 or larger. Imagine you had such k numbers. Subtract 1 from each of them, then you have sum n-k with k different numbers 1 or larger. That's c(n-k, k).
- If you do use 1, then you want remaining sum n-1 with k-1 different numbers 2 or larger. Imagine you had such k-1 numbers. Subtract 1 from each of them, then you have sum (n-1)-(k-1) = n-k with k-1 different numbers 1 or larger. That's c(n-k, k-1).
The faster solutions with Dave's case n=9000, k=100:
469.1 ± 9.2 ms Kelly2
478.8 ± 17.0 ms Kelly
673.4 ± 18.8 ms Dave_translated_by_Kelly
Code (Attempt This Online!):
def Kelly(n, k):
if k == 0:
return 1 if n == 0 else 0
@cache
def c(n, k):
if n < k * (k+1) // 2:
return 0
if k == 1:
return 1
n -= k
return c(n, k) + c(n, k-1)
return c(n, k)
# Precompute the bounds for the "n < ..." base case
def Kelly2(n, k):
if k == 0:
return 1 if n == 0 else 0
min_n_for_k = list(accumulate(range(k+1)))
@cache
def c(n, k):
if n < min_n_for_k[k]:
return 0
if k == 1:
return 1
n -= k
return c(n, k) + c(n, k-1)
return c(n, k)
def Alain(n, k):
@lru_cache(None)
def countNK(n,k,t=None):
t = n if t is None else t # track target partial sum
if k == 0: return int(t==0) # empty set can sum to zero
if t < 1 : return 0 # valid target only
if k > n : return 0 # not enough values
return countNK(n-1,k,t)+countNK(n-1,k-1,t-n) # combine counts
return countNK(n, k)
def Dave_translated_by_Kelly(n, k):
def choose(n, k):
if k > n: return 0
result = 1
for d in range(1, k+1):
result *= n
result //= d
n -= 1
return result
def count_partitions_nozeroes(n, k, cache = {}):
if k==0 and n==0: return 1
if n <= 0 or k <= 0: return 0
# Check if the result is already memoized
if (n, k) in cache:
return cache[n, k]
# Calculate the result
result = count_partitions_nozeroes(n-1, k-1, cache) + count_partitions_nozeroes(n-k, k, cache)
# Memoize the result for future use
cache[n, k] = result
return result
def count_partitions_zeros(n,k):
return count_partitions_nozeroes(n+k, k)
def solve(n,k):
r = n - choose(k+1,2)
return count_partitions_zeros(r,k)
return solve(n, k)
big = False
funcs = Alain, Kelly, Kelly2, Dave_translated_by_Kelly
if big:
funcs = funcs[1:]
from functools import lru_cache, cache
from itertools import accumulate
from time import perf_counter as time
from statistics import mean, stdev
import sys
import gc
# Correctness
for n in range(51):
for k in range(51):
expect = funcs[0](n, k)
for f in funcs[1:]:
result = f(n, k)
assert result == expect
# Speed
sys.setrecursionlimit(20000)
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e3 for t in sorted(times[f])[:5]]
return f'{mean(ts):5.1f} ± {stdev(ts):4.1f} ms '
for _ in range(25):
for f in funcs:
gc.collect()
t0 = time()
if big:
f(9000, 100)
else:
for k in range(101):
f(100, k)
times[f].append(time() - t0)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)
答案4
得分: 0
让我们介绍一个函数：f(n,k,s)=从1到n中选择k个数字，它们的和为s的组合数。
为了解决这个任务，我们需要计算f(n,k,n)。
这个函数可以通过递归计算。所有的组合可以分为两组：包含最大数字和不包含最大数字的组合，这给了我们f(n,k,s)=f(n-1,k-1,s-n)+f(n-1,k,s)。递归可以在以下情况下停止：
- n小于k -> 0（数字不够）
- k=1，s大于n -> 0（每个数字都太小）
- k=1，s小于1 -> 0（每个数字都太小）
- k=1，1<=s<=n -> 1（只有一个合适的数字）
- s小于0 -> 0
有N^2*k种可能的参数组合，所以如果我们缓存已经计算过的值，我们的复杂度将在O(N^3)范围内。
英文:
Let's introduce a function: f(n,k,s)=number of combinations of k numbers from 1 to n, having s as their sum.
To solve the task we need to calculate f(n,k,n).
The function may be calculated recursively. All combinations can be split into two groups: with and without the max number. That gives us f(n,k,s)=f(n-1,k-1,s-n)+f(n-1,k,s). The recursion may stop in the following cases:
- n<k -> 0 (we don't have enough numbers)
- k=1, s>n -> 0 (every number is too small)
- k=1, s<1 -> 0 (every number is too small)
- k=1, 1<=s<=n -> 1 (there is only one suitable number)
- s<0 -> 0
There are N^2*k possible combinations of arguments, so if we cache the already calculated values, we will be within O(N^3).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论