Поиск количества целых разделов с эффективным способом [дубликат]

Я немного опаздываю в игру, но могу предложить вклад, который может быть более элегантным в нескольких смыслах:

def partitions(n, m = None):
  """Partition n with a maximum part size of m. Yield non-increasing
  lists in decreasing lexicographic order. The default for m is
  effectively n, so the second argument is not needed to create the
  generator unless you do want to limit part sizes.
  """
  if m is None or m >= n: yield [n]
  for f in range(n-1 if (m is None or m >= n) else m, 0, -1):
    for p in partitions(n-f, f): yield [f] + p

Только 3 строки кода. Допускает их в лексикографическом порядке. Опционально позволяет накладывать максимальный размер детали.

У меня также есть вариация выше для разделов с заданным количеством частей:

def sized_partitions(n, k, m = None):
  """Partition n into k parts with a max part of m.
  Yield non-increasing lists.  m not needed to create generator.
  """
  if k == 1:
    yield [n]
    return
  for f in range(n-k+1 if (m is None or m > n-k+1) else m, (n-1)//k, -1): 
    for p in sized_partitions(n-f, k-1, f): yield [f] + p

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

def partitions(sum, max_val=100000, max_len=100000):
    """ generator of partitions of sum with limits on values and length """
    # Yields lists in decreasing lexicographical order. 
    # To get any length, omit 3rd arg.
    # To get all partitions, omit 2nd and 3rd args. 

    if sum <= max_val:       # Can start with a singleton.
        yield [sum]

    # Must have first*max_len >= sum; i.e. first >= sum/max_len.
    for first in range(min(sum-1, max_val), max(0, (sum-1)//max_len), -1):
        for p in partitions(sum-first, first, max_len-1):
            yield [first]+p

F(x,n) = \union_(i>=n) { {i}U g| g in F(x-i,i) }

Просто реализуйте эту рекурсию. F (x, n) - множество всех множеств, которые суммируются с x, а их элементы больше или равны n.

Гораздо быстрее, чем принятый ответ и не плохо выглядит. Принимаемый ответ делает много одной и той же работы несколько раз, потому что он вычисляет разделы для более низких целых чисел несколько раз. Например, когда n = 22, разница составляет 12,7 секунды против 0,0467 секунд.

def partitions_dp(n):
    partitions_of = []
    partitions_of.append([()])
    partitions_of.append([(1,)])
    for num in range(2, n+1):
        ptitions = set()
        for i in range(num):
            for partition in partitions_of[i]:
                ptitions.add(tuple(sorted((num - i, ) + partition)))
        partitions_of.append(list(ptitions))
    return partitions_of[n]

Код по существу тот же, за исключением того, что мы сохраняем разделы меньших целых чисел, поэтому нам не нужно их снова вычислять и снова.

Я не знаю, является ли мой код самым элегантным, но мне пришлось много раз его решать в исследовательских целях. Если вы измените переменную

sub_nums

, вы можете ограничить, какие числа используются в разделе.

def make_partitions(number):
    out = []
    tmp = []
    sub_nums = range(1,number+1)
    for num in sub_nums:
        if num<=number:
            tmp.append([num])
        for elm in tmp:
            sum_elm = sum(elm)
            if sum_elm == number:
                out.append(elm)
            else:
                for num in sub_nums:
                    if sum_elm + num <= number:
                         L = [i for i in elm]
                         L.append(num)
                         tmp.append(L)
    return out

В случае, если кому-то интересно: мне нужно было решить аналогичную проблему , а именно разбиение целого числа n на d неотрицательные части с перестановками. Для этого существует простое рекурсивное решение (см. здесь ):

def partition(n, d, depth=0):
    if d == depth:
        return [[]]
    return [
        item + [i]
        for i in range(n+1)
        for item in partition(n-i, d, depth=depth+1)
        ]


# extend with n-sum(entries)
n = 5
d = 3
lst = [[n-sum(p)] + p for p in partition(n, d-1)]

print(lst)

[
    [5, 0, 0], [4, 1, 0], [3, 2, 0], [2, 3, 0], [1, 4, 0],
    [0, 5, 0], [4, 0, 1], [3, 1, 1], [2, 2, 1], [1, 3, 1],
    [0, 4, 1], [3, 0, 2], [2, 1, 2], [1, 2, 2], [0, 3, 2],
    [2, 0, 3], [1, 1, 3], [0, 2, 3], [1, 0, 4], [0, 1, 4],
    [0, 0, 5]
]

Меньше и быстрее, чем функция Нолена:

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

Давайте сравним их:

In [10]: %timeit -n 10 r0 = nolen(20)
1.37 s ± 28.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [11]: %timeit -n 10 r1 = list(partitions(20))
979 µs ± 82.9 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [13]: sorted(map(sorted, r0)) == sorted(map(sorted, r1))
Out[14]: True

Похоже, что это в 1370 раз быстрее для n = 20.

В любом случае, он все еще далек от accel_asc :

def accel_asc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield a[:k + 2]
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield a[:k + 1]

Он не только медленнее, но требует гораздо больше памяти (но, по-видимому, гораздо легче запомнить):

In [18]: %timeit -n 5 r2 = list(accel_asc(50))
114 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 5 loops each)

In [19]: %timeit -n 5 r3 = list(partitions(50))
527 ms ± 8.86 ms per loop (mean ± std. dev. of 7 runs, 5 loops each)

In [24]: sorted(map(sorted, r2)) == sorted(map(sorted, r3))
Out[24]: True

Вы можете найти другие версии в ActiveState: Генератор для целых разделов (рецепт Python) .

Я использую Python 3.6.1 и IPython 6.0.0.

# -*- coding: utf-8 -*-
import timeit

ncache = 0
cache = {}


def partition(number):
    global cache, ncache
    answer = {(number,), }
    if number in cache:
        ncache += 1
        return cache[number]
    if number == 1:
        cache[number] = answer
        return answer
    for x in range(1, number):
        for y in partition(number - x):
            answer.add(tuple(sorted((x, ) + y)))
    cache[number] = answer
    return answer


print('To 5:')
for r in sorted(partition(5))[::-1]:
    print('\t' + ' + '.join(str(i) for i in r))

print(
    'Time: {}\nCache used:{}'.format(
        timeit.timeit(
            "print('To 30: {} possibilities'.format(len(partition(30))))",
            setup="from __main__ import partition",
            number=1
        ), ncache
    )
)

или https://gist.github.com/sxslex/dd15b13b28c40e695f1e227a200d1646