Partitions strictes d'un entier positif

14

OEIS A000009 compte le nombre de partitions strictes des entiers. Une partition stricte d'un entier non négatif nest un ensemble d'entiers positifs (donc aucune répétition n'est autorisée, et l'ordre n'a pas d'importance) qui somme n.

Par exemple, 5 a trois partitions strictes: 5, 4,1et 3,2.

10 a dix partitions:

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

Défi

Étant donné un entier non négatif n<1000, affichez le nombre de partitions strictes dont il dispose.

Cas de test:

0 -> 1

42 -> 1426

Voici une liste des numéros de partition stricts de 0 à 55, d'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]

Il s'agit de , donc la solution la plus courte en octets l'emporte.

lirtosiast
la source

Réponses:

4

Mathematica, 11 octets

PartitionsQ

Cas de test

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

Pyth, 7 octets

l{I#./Q

Essayez-le en ligne. Suite de tests.

  • Prenez l'entrée (Q ).
  • Trouvez ses partitions ( ./).
  • Filtrez-le ( #) sur uniquify ( {) sans modifier ( I) la partition. Cela supprime les partitions avec doublons.
  • Trouvez la longueur du résultat ( l).
PurkkaKoodari
la source
3

Haskell, 39 octets

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

La fonction (:[0])convertit un nombre kdans la liste [k,0]. Donc,

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

calcule le produit cartésien de [1,0],[2,0],...,[n,0], qui donne tous les sous-ensembles de [1..n]avec 0 pour les éléments omis. Les partitions strictes de ncorrespondent à de telles listes avec somme n. Ces éléments sont comptés par une compréhension de liste, qui est plus courte que length.filter.

xnor
la source
Brillant! Je cherchais moi-même un remplaçant pour subsequences(+ import) dans ma réponse, mais je n'ai pas réussi jusqu'à présent.
nimi
2

ES6, 64 octets

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

Fonctionne par soustraction d'essai récursive. kest le nombre qui a été soustrait en dernier, et le nombre suivant à soustraire doit être plus grand (mais pas si grand qu'un nombre encore plus grand ne peut pas être soustrait). 1 est ajouté car vous pouvez toujours vous soustraire n. (De plus, comme c'est récursif, je dois veiller à ce que toutes mes variables soient locales.)

Neil
la source
2

Python, 68 octets

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

Appelez simplement la fonction anonyme en passant l' nargument non négatif comme argument ... et attendez la fin de l'univers.

Bob
la source
faites-le n>0, vous enregistrez un octet et allez plus vite (je crois que vous recurse sur les nombres négatifs): P
st0le
En outre, la mémorisation de ce type accélère
st0le
Je ne peux pas changer votre instruction if en:return sum(...)if n else 1
andlrc
@randomra Bien sûr, bien sûr ...
Bob
1

Python 2, 49 octets

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

La récursivité se branche à chaque sommation potentielle kde 1à npour décider si elle doit être incluse. Chaque somme incluse est soustraite de la somme souhaitée n, et à la fin, s'il n=0reste, ce chemin est compté.

xnor
la source
1

Haskell, 43 octets

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

La fonction binaire n%kcompte le nombre de partitions strictes de nen parties avec une partie maximale k, donc la fonction souhaitée est f n=n%n. Chaque valeur kpeut être inclus, ce qui diminue npar k, ou exclue, et de toute façon le nouveau maximum kest une inférieure, ce qui donne la récursion n%k=n%(k-1)+(n-k)%(k-1).

xnor
la source
n%k|q<-k-1=n%q+(n-k)%qrase un octet de la ligne 3.
Izaak Weiss
0

Julia, 53 octets

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

Il s'agit d'une fonction anonyme qui accepte un entier et renvoie un entier. Pour l'appeler, affectez-le à une variable.

Nous obtenons les partitions entières en utilisant partitions, filteruniquement celles avec des sommets distincts, collectdans un tableau, et trouvons le dernier index (c'est-à-dire la longueur) en utilisant endof.

Alex A.
la source
0

Haskell, 58 octets

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

Exemple d'utilisation: map h [0..10]-> [1,1,1,2,2,3,4,5,6,8,10].

C'est une approche simple par force brute. Vérifiez les sommes de toutes les sous-séquences de 1..x. Cela fonctionne x == 0aussi parce que toutes les sous-séquences de [1..0]are [[]]et la somme de []is 0.

nimi
la source
0

05AB1E , 8 octets

ÅœʒDÙQ}g

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

Ŝ          # 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
la source
0

05AB1E , 5 octets

LæOQO

Essayez-le en ligne!

Remarque: ceci est extrêmement lent et expirera pour les entrées supérieures à environ 20.

Explication:

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
Grimmy
la source