Member 12695673 Ответов: 0

Получение большего контроля над целочисленными функциями разбиения и алгоритмом

Целочисленные разделы-очень интересная тема. Создание всех разделов данного целого числа почти просто, например, следующий код:

def aP(n):
    """Generate partitions of n as ordered lists in ascending
    lexicographical order.

    This highly efficient routine is based on the delightful
    work of Kelleher and O'Sullivan."""

    a = [1]*n
    y = -1
    v = n
    while v > 0:
        v -= 1
        x = a[v] + 1
        while y >= 2 * x:
            a[v] = x
            y -= x
            v += 1
        w = v + 1
        while x <= y:
            a[v] = x
            a[w] = y
            yield a[:w + 1]
            x += 1
            y -= 1
        a[v] = x + y
        y = a[v] - 1
        yield a[:w]


Поиск способа получить гораздо больший контроль над функцией, например, для того, чтобы генерировать только разделы размера N, это решение кажется лучше:

def sum_to_n(n, size, limit=None):
    """Produce all lists of `size` positive integers in decreasing order
    that add up to `n`."""
    if size == 1:
        yield [n]
        return
    if limit is None:
        limit = n
    start = (n + size - 1) // size
    stop = min(limit, n - size + 1) + 1
    for i in range(start, stop):           
        for tail in sum_to_n(n - i, size - 1, i):
            yield [i] + tail


Но оба они действительно генерируют все возможные разбиения данного числа, первое с каждым размером, второе с заданным размером. Что делать, если мне нужен только один конкретный раздел данного числа ? Следующий код генерирует следующий раздел данного раздела:

def next_partition(p):
  if max(p) == 1:
    return [sum(p)]
  p.sort()
  p.reverse()
  q = [ p[n] for n in range(len(p)) if p[n] > 1 ]
  q[-1] -= 1
  if (p.count(1)+1) % q[-1] == 0: 
    return q + [q[-1]]*((p.count(1)+1) // q[-1])
  else:
    return q + [q[-1]]*((p.count(1)+1) // q[-1]) + [(p.count(1)+1) % q[-1]]


Но все же есть проблема, вы должны знать, что такое раздел, прежде чем раздел будет запрошен.

Предположим теперь, что вам нужен данный раздел целого числа N, и вы знаете только номер этого раздела; пример:

Разделы 4 являются:

n.1 4
n.2 3+1
n.3 2+2
n.4 2+1+1
n.5 1+1+1+1


Как создать раздел номер 2 (3+1), дающий только целое число (4), порядковый номер (2) и необязательный размер ? И все это без создания всех разделов ? Я где-то читал, что это возможно с помощью математической формулы, но не знаю как.

Что я уже пробовал:

Изучил много учебников по этой теме, но так и не нашел решения.

0 Ответов