0

从https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Restricted_pa​​rtitions，我们知道整数 p(n) 的分区数由下式给出

p(n)

可以用python写成：

def partitions(n, I=1):
    yield(n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p

我的问题是：如何修改它以返回 q(n)，即包含不同部分的分区数？

IE;

p(3)=2, 因为 3=2+1 3=1+1+1 (1,1,1)不明显。

但是q(3)=1，因为只 3=2+1包含不同的元素。

的生成函数由q(n)下式给出

在此处输入图像描述

我在 python 中找不到一个好的产品函数，它可以将产品从 n 返回到无穷大。

4

2 回答 2

1

好吧，没有计算机可以使用实际整数计算从 n 到无穷大的乘积。

我认为最有效的解决方案如下

import functools

@functools.lru_cache(maxsize=None)  # save previous results
def unique_partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in unique_partitions(n - i, i):
            if i not in p:  # eliminate non-unique results
                yield (i,) + p

然后你可以把它们算作

def q(n):
    count = 0
    for _ in unique_partitions(n):
        count += 1
    return count
于 2018-08-05T16:05:13.807 回答
0

Рус

Добрый день, я не могу оставить комментарий под ответом FHTMitchell , поэтому оставляю его отдельно。В моём случае строка

@functools.lru_cache(maxsize=None)  # save previous results

приводит кошибкам в расчётах。Также прилагаю свой вариант функции для расчёта всех значений от 1 до N.

恩（谷歌翻译）

下午好，我无法在FHTMitchell答案下发表评论，所以我单独发表评论。就我而言，字符串

@ functools.lru_cache (maxsize = None) # save previous results

导致计算错误。我还附上了我的函数版本，用于计算从 1 到 N 的所有值。

Число   Эталон  Расчёт   Ошибка 
1       1       1               
2       1       1               
3       2       2               
4       2       2               
5       3       3               
6       4       3        Ошибка 
7       5       4        Ошибка 
8       6       4        Ошибка 
9       8       5        Ошибка 
10      10      5        Ошибка 
11      12      6        Ошибка 
12      15      6        Ошибка 
13      18      7        Ошибка 
14      22      7        Ошибка 
15      27      8        Ошибка 
16      32      8        Ошибка 
17      38      9        Ошибка 
18      46      9        Ошибка 
19      54      10       Ошибка 
20      64      10       Ошибка 
21      76      11       Ошибка 
22      89      11       Ошибка 
23      104     12       Ошибка 
24      122     12       Ошибка 
25      142     13       Ошибка

Мой вариант функции：
我的函数变体：

def partit(N=10):
    part = {}

    for i in range(1, N + 1):
        part[i] = [(j, i - j) for j in range(1, i + 1) if j < i - j]

    for i in range(1, N + 1):
        temp = []
        for up, down in part[i]:
            p2 = [(up, (u, d)) for u, d in part[down] if u > up]
            temp.extend(p2)
        part[i].extend(temp)

    return {i:len(part[i])+1 for i in part}

Может кому-то пригодится ряд из 100 первых чисел:

有人可以使用一系列 100 个第一个数字：

1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 36352 40026 44046 48446 53250 58499 64234 70488 77312 84756 92864 101698 111322 121792 133184 145578 159046 173682 189586 206848 225585 245920 267968 291874 317788 345856 376256 409174 444793

于 2018-09-09T21:45:15.817 回答