Python и теория чисел: как мы можем создать производящую функцию для q(n) (количество разбиений n на отдельные части)?

Из https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Restricted_partitions, мы знаем, что количество разделов целого числа p(n) определяется выражением

р(н)

На питоне можно написать так:

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), количество разделов, содержащих различные части?

i.e.;

p(3)=2, потому что 3=2+1 3=1+1+1 (1,1,1) неразличимы.

но q(3)=1, потому что только 3=2+1 содержит отдельные элементы.

Производящая функция q(n) определяется выражением

введите здесь описание изображения

Я не могу найти хорошую функцию продукта в python, которая возвращает продукт от n до бесконечности.


python distinct-values integer-partition number-theory
person Emm Gee    schedule 05.08.2018    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Ни один компьютер не может вычислить произведения от 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
person FHTMitchell    schedule 05.08.2018
comment
Хотя это работает, мне было интересно, есть ли другой способ, кроме того, который я написал p(n), который более экономичен по времени? Там, где нам не нужно фактически генерировать все возможные комбинации элементов, сумма которых равна n, просто посчитайте их. - person Emm Gee; 05.08.2018
comment
Что ж, это вопрос к математикам. Для p(n) да (подставьте большие n (например, sys.maxsize) и возьмите потолок math.ceil). Но бесконечные функции генерации произведения/суммы не будут работать на языке программирования. - person FHTMitchell; 05.08.2018
comment
Спрашивая математиков, возвращается: Расширение Product_{m >= 1} (1 + x^m); количество разбиений n на отдельные части; количество разбиений n на нечетные части (если n > 0). Есть ли способ сделать это в Python? - person Emm Gee; 05.08.2018
comment
Нет. product_{m >= 1} — это бесконечный продукт — это не жизнеспособный компьютерный алгоритм — кроме того, что просто равно бесконечности, вам нужна другая сторона уравнения. - person FHTMitchell; 05.08.2018

arrow_upward
0
arrow_downward

Рус

Добрый день, я не могу оставить комментарий под ответом 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

person Максим Гришкин    schedule 09.09.2018