Я попытался написать код для решения стандартной задачи Integer Partition (Wikipedia). Код, который я написал, был беспорядок. Мне нужно элегантное решение проблемы, потому что я хочу улучшить свой стиль кодирования. Это не вопрос домашней работы.
Элегантный код Python для целых разделов
Ответ 1
Пока этот ответ в порядке, я бы рекомендовал skovorodkin ответить ниже:
>>> def partition(number):
... answer = set()
... answer.add((number, ))
... for x in range(1, number):
... for y in partition(number - x):
... answer.add(tuple(sorted((x, ) + y)))
... return answer
...
>>> partition(4)
set([(1, 3), (2, 2), (1, 1, 2), (1, 1, 1, 1), (4,)])
Если вы хотите, чтобы все перестановки (т.е. (1, 3) и (3, 1)) меняли answer.add(tuple(sorted((x, ) + y))
на answer.add((x, ) + y)
Ответ 2
Чем меньше и быстрее функция Nolen:
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.
Ответ 3
Я сравнил решение с perfplot
( perfplot
небольшой проект для таких целей) и обнаружил, что ответ с perfplot
также самый медленный.
Оба ответа, предоставленные Сковородкиным, намного быстрее. (Обратите внимание на шкалу журнала.)
Чтобы сгенерировать сюжет:
import perfplot
import collections
def nolen(number):
answer = set()
answer.add((number, ))
for x in range(1, number):
for y in nolen(number - x):
answer.add(tuple(sorted((x, ) + y)))
return answer
def skovorodkin(n):
return set(skovorodkin_yield(n))
def skovorodkin_yield(n, I=1):
yield (n,)
for i in range(I, n//2 + 1):
for p in skovorodkin_yield(n-i, i):
yield (i,) + p
def accel_asc(n):
return set(accel_asc_yield(n))
def accel_asc_yield(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 tuple(a[:k + 2])
x += 1
y -= 1
a[k] = x + y
y = x + y - 1
yield tuple(a[:k + 1])
def mct(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]
perfplot.show(
setup=lambda n: n,
kernels=[
nolen,
mct,
skovorodkin,
accel_asc,
],
n_range=range(1, 17),
logy=True,
# https://stackoverflow.com/a/7829388/353337
equality_check=lambda a, b:
collections.Counter(set(a)) == collections.Counter(set(b)),
xlabel='n'
)
Ответ 4
Гораздо быстрее, чем принятый ответ и не плохо выглядит. Принимаемый ответ делает много одной и той же работы несколько раз, потому что он вычисляет разделы для более низких целых чисел несколько раз. Например, когда 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]
Код по существу тот же, за исключением того, что мы сохраняем разделы меньших целых чисел, поэтому нам не нужно их снова и снова вычислять.
Ответ 5
В случае, если кому-то интересно: мне нужно было решить аналогичную задачу, а именно разбиение целого числа 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]
]
Ответ 6
Я немного опаздываю в игру, но я могу предложить вклад, который может квалифицироваться как более элегантный в нескольких смыслах:
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
Ответ 7
# -*- 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
Ответ 8
Я не знаю, является ли мой код самым элегантным, но мне пришлось много раз его решать в исследовательских целях. Если вы измените
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
Ответ 9
F(x,n) = \union_(i>=n) { {i}U g| g in F(x-i,i) }
Просто реализуйте эту рекурсию. F (x, n) - множество всех множеств, которые суммируются с x, а их элементы больше или равны n.
Ответ 10
Вот рекурсивная функция, которая использует стек, в котором мы храним номера разделов в порядке возрастания. Это достаточно быстро и очень интуитивно понятно.
# get the partitions of an integer
Stack = []
def Partitions(remainder, start_number = 1):
if remainder == 0:
print(" + ".join(Stack))
else:
for nb_to_add in range(start_number, remainder+1):
Stack.append(str(nb_to_add))
Partitions(remainder - nb_to_add, nb_to_add)
Stack.pop()
Когда стек заполнен (сумма элементов стека соответствует числу, которое мы хотим разделить), мы печатаем его, удаляем его последнее значение и проверяем следующее возможное значение, которое будет сохранено в стеке. Когда все следующие значения были проверены, мы снова выталкиваем последнее значение стека и возвращаемся к последней вызывающей функции. Вот пример вывода (с 8):
Partitions(8)
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1 + 3
1 + 1 + 1 + 1 + 2 + 2
1 + 1 + 1 + 1 + 4
1 + 1 + 1 + 2 + 3
1 + 1 + 1 + 5
1 + 1 + 2 + 2 + 2
1 + 1 + 2 + 4
1 + 1 + 3 + 3
1 + 1 + 6
1 + 2 + 2 + 3
1 + 2 + 5
1 + 3 + 4
1 + 7
2 + 2 + 2 + 2
2 + 2 + 4
2 + 3 + 3
2 + 6
3 + 5
4 + 4
8
Структура рекурсивной функции проста для понимания и проиллюстрирована ниже (для целого числа 31):
remainder
соответствует значению оставшегося числа, которое мы хотим разделить (31 и 21 в примере выше). start_number
соответствует первому номеру раздела, его значение по умолчанию равно единице (1 и 5 в примере выше).
Если бы мы хотели вернуть результат в список и получить количество разделов, мы могли бы сделать это:
def Partitions2_main(nb):
global counter, PartitionList, Stack
counter, PartitionList, Stack = 0, [], []
Partitions2(nb)
return PartitionList, counter
def Partitions2(remainder, start_number = 1):
global counter, PartitionList, Stack
if remainder == 0:
PartitionList.append(list(Stack))
counter += 1
else:
for nb_to_add in range(start_number, remainder+1):
Stack.append(nb_to_add)
Partitions2(remainder - nb_to_add, nb_to_add)
Stack.pop()
Наконец, большое преимущество функции " Partitions
показанной выше, состоит в том, что она очень легко адаптируется для поиска всех композиций натурального числа (две композиции могут иметь одинаковый набор чисел, но порядок в этом случае различен): нам просто нужно сбросьте переменную start_number
и установите ее start_number
1 в цикле for
.
# get the compositions of an integer
Stack = []
def Compositions(remainder):
if remainder == 0:
print(" + ".join(Stack))
else:
for nb_to_add in range(1, remainder+1):
Stack.append(str(nb_to_add))
Compositions(remainder - nb_to_add)
Stack.pop()
Пример вывода:
Compositions(4)
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
1 + 3
2 + 1 + 1
2 + 2
3 + 1
4