Código elegante de Python para el Partición Entero

Question

Traté de escribir código para resolver el problema estándar de la Partición Integer (Wikipedia). El código que escribí fue un desastre. Necesito una solución elegante para resolver el problema, porque quiero mejorar mi estilo de codificación. Esta no es una pregunta de tarea.

Answer 1

Mientras que esta respuesta está muy bien, me gustaría recomendar la respuesta de skovorodkin a continuación:

>>> 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,)]) 

Si desea que todas las permutaciones (es decir, (1, 3) y (3, 1)) cambio answer.add(tuple(sorted((x,) + y)) a answer.add((x,) + y)

Answer 2

No sé si mi código es el más elegante, pero he tenido que resolverlo muchas veces para fines de investigación. Si modifica la

sub_nums 

variable, puede restringir los números que se utilizan en la partición.

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 

Answer 3

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

Sólo implementar esta recursividad. F (x, n) es el conjunto de todos los conjuntos que suman x y sus elementos son mayores que o iguales a n.

Answer 4

Mucho más rápido que la respuesta aceptada y no está mal visto, tampoco. La respuesta aceptada hace muchas veces el mismo trabajo varias veces porque calcula las particiones para enteros inferiores varias veces. Por ejemplo, cuando n = 22 la diferencia es 12.7 segundos contra 0.0467 segundos.

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] 

El código es esencialmente el mismo, excepto que salvar a las particiones de números enteros más pequeños, así que no tenemos que calcular una y otra vez.

Answer 5

# -*- 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 
    ) 
) 

o https://gist.github.com/sxslex/dd15b13b28c40e695f1e227a200d1646

Answer 6

Una pequeña y rápida que la función de 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 

Comparemos ellos:

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 

parece que es 1370 veces más rápido para n = 20.

De todos modos, todavía lejos de 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] 

No es sólo más lento, pero requiere mucha más memoria (pero al parecer es mucho más fácil de recordar):

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 

---

Usted puede encontrar otras versiones en ActiveState: Generator For Integer Partitions (Python Recipe).

---

Uso Python 3.6.1 e IPython 6.0.0.

Answer 7

He comparado la solución con perfplot (un pequeño proyecto mío para tales fines) y encontré que la respuesta más votada de Nolen es también la más lenta.

Ambas respuestas suministradas por skovorodkin son mucho más rápido. (Tenga en cuenta la escala logarítmica.)

---

Para para generar la trama:

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' 
    ) 

Answer 8

En caso de que a alguien le interesa: que tenía que resolver un similares problema , es decir, la partición de un número entero n en d partes no negativas, con permutaciones. Para esto, hay una solución simple recursivo (ver here):

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) 

Salida:

[ 
    [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] 
] 

Answer 9

estoy un poco tarde al juego, pero puedo ofrecer una contribución que podría calificar como más elegante en algunos sentidos:

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 

Solo 3 líneas de código. Los cede en orden lexicográfico. Opcionalmente permite la imposición de un tamaño de parte máximo.

También tienen una variación de lo anterior para particiones con un número determinado de piezas:

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 

Después de componer lo anterior, me encontré con una solución que había creado hace casi 5 años, pero que he tenido olvidado de. Además de un tamaño máximo de parte, este ofrece la característica adicional de que puede imponer una longitud máxima (a diferencia de una longitud específica). 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