Particiones estrictas de un entero positivo

14

OEIS A000009 cuenta el número de particiones estrictas de los enteros. Una partición estricta de un entero no negativo nes un conjunto de enteros positivos (por lo que no se permite la repetición y el orden no importa) que suman n.

Por ejemplo, 5 tiene tres particiones estrictas: 5, 4,1, y 3,2.

10 tiene diez particiones:

10
9,1
8,2
7,3
6,4
7,2,1
6,3,1
5,4,1
5,3,2
4,3,2,1

Desafío

Dado un entero no negativo n<1000, genera el número de particiones estrictas que tiene.

Casos de prueba:

0 -> 1

42 -> 1426

Aquí hay una lista de los números de partición estrictos del 0 al 55, de OEIS:

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

Este es el , por lo que gana la solución más corta en bytes.

lirtosiast
fuente

Respuestas:

4

Mathematica, 11 bytes

PartitionsQ

Caso de prueba

PartitionsQ@Range[10]
(* {1,1,2,2,3,4,5,6,8,10} *)
njpipeorgan
fuente
3

Pyth, 7 bytes

l{I#./Q

Pruébalo en línea. Banco de pruebas.

  • Toma la entrada ( Q).
  • Encuentra sus particiones ( ./).
  • #Filtrarlo ( ) en uniquify ( {) sin cambiar ( I) la partición. Esto elimina particiones con duplicados.
  • Encuentra la longitud del resultado ( l).
PurkkaKoodari
fuente
3

Haskell, 39 bytes

f n=sum[1|x<-mapM(:[0])[1..n],sum x==n]

La función (:[0])convierte un número ka la lista [k,0]. Entonces,

mapM(:[0])[1..n]

calcula el producto cartesiano de [1,0],[2,0],...,[n,0], que da todos los subconjuntos de [1..n]con 0 para elementos omitidos. Las particiones estrictas de ncorresponden a dichas listas con suma n. Dichos elementos se cuentan mediante una comprensión de la lista, que es más corta que length.filter.

xnor
fuente
¡Brillante! Estaba buscando un reemplazo para subsequences(+ import) en mi respuesta, pero hasta ahora no tuve éxito.
nimi
2

ES6, 64 bytes

f=(n,k=0)=>[...Array(n)].reduce((t,_,i)=>n-i>i&i>k?t+f(n-i,i):t,1)

Obras por sustracción recursiva de prueba. kes el número que se restó por última vez, y el siguiente número que se restará debe ser mayor (pero no tan grande que no se pueda restar un número aún mayor). Se agrega 1 porque siempre se puede restar n. (Además, dado que esto es recursivo, debo tener cuidado de que todas mis variables sean locales).

Neil
fuente
2

Python, 68 bytes

p=lambda n,d=0:sum(p(n-k,n-2*k+1)for k in range(1,n-d+1))if n else 1

Simplemente llame a la función anónima pasando el entero no negativo ncomo argumento ... y espere el final del universo.

Beto
fuente
lo hace n>0, se ahorra un byte e ir más rápido (creo que son recursivos en números negativos): P
st0le
Además, este tipo de Memoizing lo acelera
st0le
No puede cambiar su declaración if a:return sum(...)if n else 1
andlrc
@randomra Por supuesto, por supuesto ...
Bob
1

Python 2, 49 bytes

f=lambda n,k=1:n/k and f(n-k,k+1)+f(n,k+1)or n==0

Las ramas de recursividad en cada sumando el potencial kde 1que npara decidir si debe ser incluido. Cada sumando incluido se resta de la suma deseada n, y al final, si n=0permanece, se cuenta esa ruta.

xnor
fuente
1

Haskell, 43 bytes

0%0=1
_%0=0
n%k=n%(k-1)+(n-k)%(k-1)
f n=n%n

La función binaria n%kcuenta el número de particiones estrictas de nen partes con una parte máxima k, por lo que la función deseada es f n=n%n. Cada valor kpuede ser incluido, que disminuye npor k, o excluido, y de cualquier manera el nuevo máximo kes uno inferior, dando la recursión n%k=n%(k-1)+(n-k)%(k-1).

xnor
fuente
n%k|q<-k-1=n%q+(n-k)%qafeita un byte de la línea 3.
Izaak Weiss
0

Julia, 53 bytes

n->endof(collect(filter(p->p==∪(p),partitions(n))))

Esta es una función anónima que acepta un entero y devuelve un entero. Para llamarlo, asígnelo a una variable.

Obtenemos las particiones enteras usando partitions, filtersolo para aquellos con sumandos distintos, collecten una matriz, y encontramos el último índice (es decir, la longitud) usando endof.

Alex A.
fuente
0

Haskell, 58 bytes

import Data.List
h x=sum[1|i<-subsequences[1..x],sum i==x]

Ejemplo de uso: map h [0..10]-> [1,1,1,2,2,3,4,5,6,8,10].

Es un enfoque simple de fuerza bruta. Verifique las sumas de todas las subsecuencias de 1..x. Esto también funciona x == 0porque todas las subsecuencias de [1..0]are [[]]y la suma de []is 0.

nimi
fuente
0

05AB1E , 8 bytes

ÅœʒDÙQ}g

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

Ŝ          # Get all integer partitions of the (implicit) input
            #  i.e. 5 → [[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]]
  ʒ   }     # Filter by:
   D        #  Duplicate the current partition
    Ù       #  Uniquify (removing any duplicated values from) this copied partition
            #   i.e. [1,1,1,1,1] → [1]
            #   i.e. [1,4] → [1,4]
     Q      #  Check if it's still the same
            #   i.e. [1,1,1,1,1] and [1] → 0 (falsey)
            #   i.e. [1,4] and [1,4] → 1 (truthy)
       g    # Then take the length of the filtered list (and implicitly output it)
            #  i.e. [[1,4],[2,5],[5]] → 3
Kevin Cruijssen
fuente
0

05AB1E , 5 bytes

LæOQO

Pruébalo en línea!

Nota: esto es extremadamente lento y agota el tiempo de espera para entradas mayores de aproximadamente 20.

Explicación:

L         # range 1..input
 æ        # list of subsets
  O       # sum each subset
   Q      # equal? (1 for each sum that equals the input, 0 otherwise)
    O     # sum the booleans
Mugriento
fuente