找到具有n个不同部分的整数分区的数量

发布于 2025-02-10 23:02:05 字数 558 浏览 1 评论 0原文

一个具有n不同部分的整数分区是一个降低的积极整数列表，该列表汇总到n中，其中没有数字超过一次。
例如，有3个整数分区为5： [5]，[4,1]，[3,2]。
编写一个函数，该函数返回具有n不同部分的整数分区的数量，其中1＆lt; = n＆lt; = 600。

来源：

”

import itertools
list_poss = [list(i) for j in range(1, n+1) for i in itertools.combinations(range(n+1), j) if sum(list(i)) == n and 0 not in list(i)]

但是它太慢了，并且会产生以下错误：执行时间（12000 ms）。

如何进一步优化此代码？

原文

An integer partition with distinct parts of n is a decreasing list of positive integers which sum to n, in which no number occurs more than once.
For example, there are 3 integer partitions of 5:
[5], [4,1], [3,2].
Write a function which returns the number of integer partitions with distinct parts of n where 1 <= n <= 600.

Source: https://www.codewars.com/kata/6267a007e67fba0058725ad2

I wrote this code:

import itertools
list_poss = [list(i) for j in range(1, n+1) for i in itertools.combinations(range(n+1), j) if sum(list(i)) == n and 0 not in list(i)]

but it is too slow and gives the following error : Execution Timed Out (12000 ms).

How can I optimise this code further?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

薆情海 2025-02-17 23:02:05

这看起来像是递归的工作。

n的分区始终具有[n]。然后，对于每个数字k从n-1降低到N的一半（独家），可以用k和n（即NK）的其余部分形成分区：

from functools import lru_cache

@lru_cache(None)        # remember/reuse past results
def countParts(n):
    return 1 + sum(countParts(n-k) for k in range(n-1,n//2,-1))

输出：

for n in range(1,20):
    print(n,countParts(n))

1 1
2 1
3 2
4 2
5 3
6 3
7 5
8 5
9 7
10 7
11 10
12 10
13 13
14 13
15 18
16 18
17 23
18 23
19 30

countParts(100) # 4914

countParts(600) # 38847071

要查看分区是什么，您可以使用递归生成器编写递归生成器相同的逻辑：

def genParts(n):
    yield [n]
    for k in range(n-1,n//2,-1):
        for p in genParts(n-k):
            yield [k,*p]

for n in range(1,10):
    print(n,*genParts(n))

1 [1]
2 [2]
3 [3] [2, 1]
4 [4] [3, 1]
5 [5] [4, 1] [3, 2]
6 [6] [5, 1] [4, 2]
7 [7] [6, 1] [5, 2] [4, 3] [4, 2, 1]
8 [8] [7, 1] [6, 2] [5, 3] [5, 2, 1]
9 [9] [8, 1] [7, 2] [6, 3] [6, 2, 1] [5, 4] [5, 3, 1]

This looks like a job for recursion.

Partitions for n will always have [n] on its own. Then for every number k from n-1 down to half of n (exclusively), partitions can be formed with k and the remainder of n (i.e. n-k):

from functools import lru_cache

@lru_cache(None)        # remember/reuse past results
def countParts(n):
    return 1 + sum(countParts(n-k) for k in range(n-1,n//2,-1))

output:

for n in range(1,20):
    print(n,countParts(n))

1 1
2 1
3 2
4 2
5 3
6 3
7 5
8 5
9 7
10 7
11 10
12 10
13 13
14 13
15 18
16 18
17 23
18 23
19 30

countParts(100) # 4914

countParts(600) # 38847071

To see what the partitions are, you can write a recursive generator using the same logic:

def genParts(n):
    yield [n]
    for k in range(n-1,n//2,-1):
        for p in genParts(n-k):
            yield [k,*p]

for n in range(1,10):
    print(n,*genParts(n))

1 [1]
2 [2]
3 [3] [2, 1]
4 [4] [3, 1]
5 [5] [4, 1] [3, 2]
6 [6] [5, 1] [4, 2]
7 [7] [6, 1] [5, 2] [4, 3] [4, 2, 1]
8 [8] [7, 1] [6, 2] [5, 3] [5, 2, 1]
9 [9] [8, 1] [7, 2] [6, 3] [6, 2, 1] [5, 4] [5, 3, 1]

回复收藏 0 原文

~没有更多了~