Combien de partitions ai-je?

16

Le numéro de partition d'un entier positif est défini comme le nombre de façons dont il peut être exprimé comme une somme d'entiers positifs. En d'autres termes, le nombre de partitions entières qu'il possède. Par exemple, le nombre 4a les partitions suivantes:

[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

Par conséquent, il a des 5partitions. C'est OEIS A000041 .

Tâche

Étant donné un entier positif, N détermine son numéro de partition.

  • Toutes les règles standard s'appliquent.

  • L'entrée et la sortie peuvent être traitées par tout moyen raisonnable.

  • Il s'agit de code-golf , donc le code le plus court en octets l'emporte.

Cas de test

Entrée | Production

1 | 1
2 | 2
3 | 3
4 | 5
5 | sept
6 | 11
7 | 15
8 | 22
9 | 30
10 | 42
code-golf math number-theory combinatorics integer-partitions Martin Ender
la source
1
Je suis presque
certain
@DJMcMayhem Umm, d'accord. Faites-moi savoir si vous trouvez un doublon. Désolé, je suis nouveau dans tout ça!
1
@DJMcMayhem peut - être cette question que vous avez posée car c'est un court pas de "générer" à "compter" mais vous n'avez pas nécessairement à générer toutes les partitions pour les compter ...
Giuseppe
1
celui-ci est un dupe, SAUF qui est un popcon (?) et fermé comme trop large. À mon humble avis, il est bien mieux écrit et devrait rester ouvert, tandis que l'ancien devrait être (rouvert et) fermé comme dupe
Rod
2
@Rod, c'est un mauvais pop-con, mais changer la raison proche de duper ne serait pas une amélioration. L'exigence de performances serait un obstacle au portage de certaines réponses (personne ne va générer les partitions 24061467864032622473692149727991 de 1000 en quelques minutes); et l'implémentation Hardy-Ramanujan-Rademacher n'est pas exactement du golf ... Cependant, il peut être utile d'ouvrir une discussion en méta sur ce qu'il faut faire avec cette question et celle-là.
Peter Taylor

Réponses:

13

Pyth , 3 octets

l./

Essayez-le ici! ou Essayez une suite de tests.

La réponse a mis beaucoup plus de temps à formater qu'à écrire le code lui-même: P.

Comment?

Pyth est le bon outil pour le travail.

l. / Programme complet avec entrée implicite.

 ./ Partitions entières. Renvoie toutes les listes triées d'entiers positifs qui s'ajoutent à l'entrée.
l Longueur.
      Sortie implicite du résultat.
M. Xcoder
la source
34

Mathematica, 11 octets

PartitionsP

Explication

¯\_(ツ)_/¯
ngenisis
la source
8

Python 2 , 85 83 octets

-2 octets grâce à @notjagan

lambda n:n<1or sum(sum(i*((n-k)%i<1)for i in range(1,n+1))*p(k)for k in range(n))/n

Essayez-le en ligne!

Utilisation d'une formule récursive d' OEIS A000041 .

shooqie
la source
83 octets.
notjagan
84 octets . ==0est équivalent à <1dans ce cas. EDIT: Utilisez l'approche de notjagan
M. Xcoder
@ Mr.Xcoder Le code d'origine avait en fait <1au lieu de ==0, mais pas le code TIO.
notjagan
Aussi 83 octets .
M. Xcoder
8

Emojicode 0,5, 204 201 octets

🐋🚂🍇🐖🅰️➡🚂🍇🍊⬅🐕1🍇🍎1🍉🍮s 0🔂k⏩0🐕🍇🍦t➖🐕k🍮r t🔂i⏩1 t🍇🍊😛🚮t i 0🍇🍮➕r i🍉🍉🍮➕s✖r🅰️k🍉🍎➗s🐕🍉🍉

Essayez-le en ligne!

-3 octets en utilisant "inférieur ou égal à 1" au lieu de "inférieur à 2" car l'émoji "inférieur à" a un encodage UTF-8 assez long. Également fait tun gel pour faire taire un avertissement sans affecter le nombre d'octets.

Étend la classe 🚂 (entier) avec une méthode nommée 🅰️. Vous pouvez écrire un programme simple qui prend un nombre de l'entrée, appelle 🅰️ sur le numéro et imprime le résultat comme ceci:

🏁🍇
 🍦str🔷🔡😯🔤Please enter a number🔤
 🍊🍦num🚂str 10🍇
  😀🔡🅰️num 10
 🍉🍓🍇
  😀🔤Learn what a number is, you moron!🔤
 🍉
🍉

Cette partie pourrait être beaucoup jouée en omettant les messages et la gestion des erreurs, mais elle n'est pas incluse dans le score, donc je préfère montrer plus de fonctionnalités d'Emojicode à la place, tout en améliorant la lisibilité en cours de route.

Non golfé

🐋🚂🍇
 🐖🅰️➡🚂🍇
  🍊◀️🐕2🍇
   🍎1
  🍉
  🍮sum 0
  🔂k⏩0🐕🍇
   🍦nmk➖🐕k
   🍮sig nmk
   🔂i⏩1 nmk🍇
    🍊😛🚮nmk i 0🍇
     🍮➕sig i
    🍉
   🍉
   🍮➕sum✖sig🅰️k
  🍉
  🍎➗sum🐕
 🍉
🍉

Explication

Remarque: beaucoup de choix d'emoji n'a pas beaucoup de sens dans emojicode 0.5. C'est 0.x, après tout. 0.6 corrigera cela.

Emojicode est un langage de programmation orienté objet comprenant des génériques, des protocoles, des options et des fermetures, mais ce programme n'utilise aucune fermeture et tous les génériques et protocoles peuvent être considérés comme implicites, tandis que le seul facultatif apparaît dans le talon d'E / S.

Le programme ne fonctionne que sur quelques types: 🚂 est le type entier, 🔡 est le type chaîne et ⏩ est le type plage. Quelques booléens (👌) apparaissent également, mais ils ne sont utilisés que dans des conditions. Les booléens peuvent prendre une valeur de 👍 ou 👎, qui correspondent respectivement à vrai et faux.

Il n'y a actuellement aucun opérateur dans Emojicode, donc l'addition, les comparaisons et d'autres opérations qui sont normalement des opérateurs sont implémentées en tant que fonctions, ce qui fait que les expressions utilisent la notation de préfixe . Des opérateurs sont également prévus en 0.6.

Abordons d'abord le programme de test.

🏁

Il s'agit du bloc 🏁, qui peut être comparé au principal des autres langues.

🍇 ... 🍉

Les raisins et les pastèques déclarent des blocs de code en emojicode.

🍦str🔷🔡😯🔤Please enter a number🔤

Cela déclare un "gelé" nommé stret lui attribue une nouvelle chaîne créée à l'aide de l'initialiseur (constructeur) which, qui prend une invite sous forme de chaîne, puis entre une ligne de l'utilisateur. Pourquoi utiliser un gelé au lieu d'une variable? Il ne changera pas, donc une variable émettrait un avertissement.

🍊🍦num🚂str 10

Décomposons-le. 🚂str 10appelle la méthode 🚂 sur le strgelé avec l'argument 10. Par convention, les méthodes nommées avec le nom d'un type convertissent l'objet en ce type. 10 est la base à utiliser pour la conversion d'entiers. Cette méthode retourne une option, 🍬🚂. Les options peuvent contenir une valeur de type de base ou néant, ⚡. Lorsque la chaîne ne contient pas de nombre, ⚡ est renvoyé. Pour utiliser la valeur, il faut déballer l'option en utilisant 🍺, ce qui déclenche une erreur d'exécution si la valeur est ⚡. Par conséquent, il est recommandé de vérifier le néant avant de déballer une option. C'est tellement courant, en fait, qu'Emojicode a un raccourci pour ça. Normalement, 🍊c'est un "si".🍊🍦 variable expression signifie: évaluer l'expression. Si l'option facultative ne contient rien, la condition est évaluée à 👎 (faux). Sinon, un nom figévariableest créé avec la valeur non encapsulée de l'option, et la condition est évaluée à 👍, (true). Par conséquent, en utilisation normale, le 🍇 ... 🍉bloc suivant le conditionnel est entré.

😀🔡🅰️num 10

🅰️ est la méthode que le code principal ajoute à 🚂 en utilisant 🐋 qui calcule le nombre de partitions. Cela appelle 🅰️ sur le numgelé que nous avons déclaré au conditionnel et convertit le résultat en une chaîne utilisant la base 10 par la méthode 🔡. Ensuite, 😀 imprime le résultat.

🍓🍇 ... 🍉

🍓 signifie "autre", donc ce bloc est entré lorsque l'utilisateur n'a pas entré correctement un numéro.

😀🔤Learn what a number is, you moron!🔤

Imprime la chaîne littérale.

Maintenant, regardons le programme principal. Je vais expliquer la version non golfée; la version golfée a simplement supprimé les espaces et renommé les variables en noms de lettre unique.

🐋🚂🍇 ... 🍉

Étendez la classe 🚂. Il s'agit d'une fonctionnalité que l'on ne trouve pas couramment dans les langages de programmation. Au lieu de créer une nouvelle classe avec 🚂 comme superclasse, 🐋 modifie 🚂 directement.

🐖🅰️➡🚂🍇 ... 🍉

Crée une nouvelle méthode nommée 🅰️ qui renvoie un 🚂. Il renvoie le nombre de partitions calculé à l'aide de la formulea(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k)

🍊⬅🐕1🍇
 🍎1
🍉

🐕 est similaire thisou selfprovenant d'autres langages et fait référence à l'objet sur lequel la méthode a été appelée. Cette implémentation est récursive, il s'agit donc de la condition de fin: si le nombre auquel la méthode a été appelée est inférieur ou égal à 1, retournez 1.

🍮sum 0

Créez une nouvelle variable sumet définissez-la sur 0. Suppose implicitement le type 🚂.

🔂k⏩0🐕

🔂 itère sur tout ce qui implémente le protocole 🔂🐚⚪️, tandis que ⏩ est un littéral de plage qui arrive à implémenter 🔂🐚🚂. Une plage a une valeur de début, une valeur d'arrêt et une valeur de pas, qui est supposée être 1 si start < stop, ou -1 sinon. On peut également spécifier la valeur de l'étape en utilisant le ⏭ pour créer le littéral de plage. La valeur de départ est inclusive, tandis que la valeur d'arrêt est exclusive, c'est donc équivalent à for k in range(n)ou Sum_{k=0..n-1}dans la formule.

🍦nmk➖🐕k

Nous devons calculer sigma (n - k), ou la somme des diviseurs de n - ken d'autres termes, et l'argument est nécessaire plusieurs fois, donc cela stocke n - kdans la variable nmkpour économiser quelques octets.

🍮sig nmk
🔂i⏩1 nmk

Cela définit la sigvariable sur l'argument de sigma et itère sur tous les nombres de 1 à nmk - 1. Je pourrais initialiser la variable à 0 et itérer sur 1..nmk mais le faire de cette façon est plus court.

🍊😛🚮nmk i 0

🚮 calcule le reste, ou module et 😛 vérifie l'égalité, donc la condition sera 👍 si iest un diviseur de nmk.

🍮➕sig i

Il s'agit d'une affectation par appel, similaire à la += -= >>=famille des opérateurs dans certaines des langues inférieures, sans emoji. Cette ligne peut également s'écrire 🍮 sig ➕ sig i. Par conséquent, une fois la boucle intérieure terminée, sigcontiendra la somme des diviseurs de n - k, ousigma(n - k)

🍮➕sum✖sig🅰️k

Une autre affectation par appel, donc cela ajoute sigma(n - k) * A(k)au total, tout comme dans la formule.

🍎➗sum🐕

Enfin, la somme est divisée par n et le quotient est renvoyé. Cette explication a probablement pris trois fois plus de temps que d'écrire le code lui-même ...

NieDzejkob
la source
3

Octave, 18 octets

partcnt(input(''))

Utilise la fonction intégrée partcnt.

Impossible de faire les choses correctement en utilisant une fonction anonyme en utilisant @, une aide serait appréciée.

Michthan
la source
3

Rétine , 34 octets

.+
$*
+%1`\B
;$'¶$`,
,

%O`1+
@`.+

Essayez-le en ligne!

Explication

.+
$*

Convertissez l'entrée en unaire.

+%1`\B
;$'¶$`,

Ceci calcule les 2 n-1 partitions de la liste de chiffres unaires. Nous faisons cela en répétant ( +) en faisant correspondre la première ( 1) frontière non-mot ( \B, c'est-à-dire une position entre deux 1s) dans chaque ligne ( %) et en la remplaçant par ;, tout après ( $'), un saut de ligne ( ), tout en face de il ( $`) et ,. Exemple:

1;1,111

Devient

      vv
1;1,1;11
1;1,1,11
^^^^^

Où vmarque le résultat de $'et ^marque le résultat$` . Il s'agit d'un idiome commun pour obtenir le résultat de deux remplacements différents à la fois (nous insérons essentiellement à la fois le ;et le ,remplacement, ainsi que les «moitiés» manquantes de la chaîne pour effectuer deux substitutions complètes).

Nous traiterons ;comme des partitions réelles et ,comme des espaces réservés qui empêcheront les \Bcorrespondances ultérieures . Alors ensuite ...

,

... nous supprimons ces virgules. Cela nous donne toutes les partitions. Par exemple, pour la saisie, 4nous obtenons:

1;1;1;1
1;1;11
1;11;1
1;111
11;1;1
11;11
111;1
1111

Nous ne nous soucions pas de la commande cependant:

%O`1+

Cela trie les séries de 1s dans chaque ligne afin que nous obtenions des partitions non ordonnées.

@`.+

Enfin, nous comptons les correspondances uniques ( @) de .+, c'est-à-dire le nombre de lignes / partitions distinctes que nous avons obtenues. J'ai ajouté cette @option il y a longtemps, puis je l'ai complètement oubliée et je ne l'ai redécouverte que récemment. Dans ce cas, il enregistre un octet sur la première déduplication des lignes avec D`.

Martin Ender
la source
3

Python 2 , 54 53 octets

f=lambda n,k=1:1+sum(f(n-j,j)for j in range(k,n/2+1))

Essayez-le en ligne!

Comment ça fonctionne

Chaque partition de n peut être représentée comme une liste x = [x 1 , ⋯, x m ] telle que x 1 + ⋯ + x m = n . Cette représentation devient unique si nous exigeons que x 1 ≤ ⋯ ≤ x m .

Nous définissons une fonction auxiliaire f (n, k) qui compte les partitions à borne inférieure k , c'est-à-dire les listes x telles que x 1 + ⋯ + x m = n et k ≤ x 1 ≤ ⋯ ≤ x m . Pour l'entrée n , le défi demande donc la sortie de f (n, 1) .

Pour les entiers positifs n et k tels que k ≤ n , il existe au moins une partition à borne inférieure k : la liste singleton [n] . Si n = k (en particulier, si n = 1 ), c'est la seule partition éligible. En revanche, si k> n , il n'y a aucune solution.

Si k <n , nous pouvons compter récursivement les partitions restantes en les construisant de gauche à droite, comme suit. Pour chaque j tel que k ≤ j ≤ n / 2 , on peut construire des partitions [x 1 , ⋯, x m ] = [j, y 1 , ⋯, y m-1 ] . On a que x 1 + ⋯ + x m = n si et seulement si y 1 + ⋯ + y m-1 = n - j . De plus, x 1 ≤ ⋯ ≤ x m si et seulement si j ≤ y 1 ≤ ⋯ ≤ y m-1 .

Par conséquent, les partitions x de n qui commencent par j peuvent être calculées comme f (n - j, j) , qui compte les partitions valides y . En exigeant que j ≤ n / 2 , nous assurons que j ≤ n - j , donc il y a au moins un y . On peut donc compter toutes les partitions de n en sommant 1 (pour [n] ) et f (n - j, j) pour toutes les valeurs valides de j .

Le code est une implémentation simple de la fonction mathématique f . De plus, il fait k par défaut à 1 , donc f(n)calcule la valeur de f (n, 1) pour l'entrée n .

Dennis
la source
Oh wow, c'est incroyable! Pouvez-vous ajouter une explication sur la façon dont cela fonctionne?
J'ai édité ma réponse. Si quelque chose n'est pas clair, faites-le moi savoir.
Dennis
3

J , 37 35 octets

0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:

Essayez-le en ligne!

Explication

0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:  Input: n
                                 1:  Constant 1
  ]                                  Get n
   1&(                          )    Repeat n times on x = [1]
                          \            For each prefix
                         #               Length
                      q:@                Prime factors
                 /.~&                    Group equal factors
              #.~                        Compute p+p^2+...+p^k for each group
           >:@                           Increment
                    &.q:                 Product
                           %           Divide
                            #          Length
         ]                             Get x
          *                            Times
   1   #.                              Sum
                              ,        Joim
                               ]       Get x
                                       Set this as next value of x
0{                                   Select value at index 0
miles
la source
Je suis stupéfait et abasourdi, ça vous dérange de poster une explication?
cole
1
@cole Il s'agit d'une approche itérative qui commence par la solution pour p (0) = 1, et construit la suivante en utilisant la formule p(n) = sum(sigma(n-k) * p(k) for k = 0 to n-1) / n. J'ajouterai une explication du code plus tard quand je pense qu'il ne peut pas être raccourci de manière significative.
miles
2

JavaScript, 125 121 octets

n=>(z=(a,b)=>[...Array(a)].map(b))(++n**n,(_,a)=>z[F=z(n,_=>a%(a/=n,n)|0).sort().join`+`]=b+=eval(F)==n-1&!z[F],b=0)|b||1

Essayez-le en ligne!

Attention: la complexité du temps et de l'espace est exponentielle. Fonctionne très lentement pour les grands nombres.


la source
2

Python 2 , 89 octets

-9 octets par Mr.Xcoder -1 octet par notjagan

lambda n:len(p(n))
p=lambda n,I=1:{(n,)}|{y+(x,)for x in range(I,n/2+1)for y in p(n-x,x)}

Essayez-le en ligne!

Possum mort
la source
1
90 octets
M. Xcoder
@ Mr.Xcoder Je ne sais même pas pourquoi je n'ai pas utilisé lambda D:
Dead Possum
Hehe, ¯\_(ツ)_/¯- BTW, si vous vouliez garder une fonction complète, vous n'auriez pas besoin de la variable, 94 octets
M. Xcoder
@ Mr.Xcoder Ouais .. Je me sens rouillé après un certain temps loin de codegolf: c
Dead Possum
-1 octet.
notjagan
1

Gelée , 13 octets

JÆsæ.:L;
1Ç¡Ḣ

Essayez-le en ligne!

Prend 5 secondes pour résoudre n = 1000 sur TIO.

miles
la source
0

Java 8 (229 octets)

import java.util.function.*;class A{static int j=0;static BiConsumer<Integer,Integer>f=(n,m)->{if(n==0)j++;else for(int i=Math.min(m,n);i>=1;i--)A.f.accept(n-i,i);};static Function<Integer,Integer>g=n->{f.accept(n,n);return j;};}

Non golfé:

import java.util.function.*;

class A {
    static int j = 0;
    static BiConsumer<Integer, Integer> f = (n, m) -> {
        if (n == 0)
            j++;
        else
            for (int i = Math.min(m, n); i >= 1; i--)
                A.f.accept(n - i, i);
    };
    static Function<Integer, Integer> g = n -> {
        f.accept(n, n);
        return j;
    };
}
Roberto Graham
la source
0

Gelée , 3 octets

L' Œṗatome a récemment été ajouté, et cela signifie "partitions entières".

ŒṗL

Essayez-le en ligne!

ŒṗL - Programme complet.

Œṗ - partitions entières.
  L - Longueur.
      - Sortie implicitement.
M. Xcoder
la source
0

Pyt , 2 octets

←ᵱ

Explication:

←          Get input
 ᵱ         Number of partitions
mudkip201
la source
0

JavaScript ES7, 69 octets

n=>(f=(i,s)=>i?[for(c of Array(1+n))f(i-1,s,s-=i)]:c+=!s)(n,n,c=0)&&c

JavaScript ES6, 71 octets

n=>(f=(i,s)=>i?[...Array(1+n)].map(_=>f(i-1,s,s-=i)):c+=!s)(n,n,c=0)&&c

Complexité temporelle O (n ^ n), alors soyez prudent (un retard évident apparaît sur mon ordinateur pour F(6))

l4m2
la source