Calculer les partitions de N

22

Votre défi est simple: un entier étant donné N , ouput chaque liste des nombres entiers positifs que des sommes à N . Par exemple, si l'entrée était 5, vous devez sortir

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

Ces listes ne doivent pas être sorties dans un ordre particulier, pas plus que les numéros à l'intérieur de chaque liste. Par exemple, ce serait également une sortie acceptable pour «5»:

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

Vous pouvez supposer en toute sécurité que l'entrée sera un entier positif, et vous pouvez prendre ce nombre dans n'importe quel format raisonnable.

Vous ne pouvez pas utiliser de fonctions intégrées à cet effet.

Si votre programme échoue ou prend trop de temps pour un grand N, c'est OK, mais vous devez au moins produire la sortie correcte pour les 15 premiers.

Les failles standard s'appliquent et la réponse la plus courte en octets l'emporte!

Test IO

1:
[[1]]

2:
[[1, 1], [2]]

3:
[[1, 1, 1], [1, 2], [3]]

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

5:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 4], [2, 3], [5]]

7:
[[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 3], [1, 1, 1, 2, 2], [1, 1, 1, 4], [1, 1, 2, 3], [1, 1, 5], [1, 2, 2, 2], [1, 2, 4], [1, 3, 3], [1, 6], [2, 2, 3], [2, 5], [3, 4], [7]]

10:
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 6], [1, 1, 1, 2, 2, 3], [1, 1, 1, 2, 5], [1, 1, 1, 3, 4], [1, 1, 1, 7], [1, 1, 2, 2, 2, 2], [1, 1, 2, 2, 4], [1, 1, 2, 3, 3], [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 1, 8], [1, 2, 2, 2, 3], [1, 2, 2, 5], [1, 2, 3, 4], [1, 2, 7], [1, 3, 3, 3], [1, 3, 6], [1, 4, 5], [1, 9], [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5], [2, 4, 4], [2, 8], [3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]

Cas de test super grand: 15 devraient produire ceci

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 11], [1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 2, 2, 8], [1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 2, 3, 7], [1, 1, 1, 2, 4, 6], [1, 1, 1, 2, 5, 5], [1, 1, 1, 2, 10], [1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 3, 3, 6], [1, 1, 1, 3, 4, 5], [1, 1, 1, 3, 9], [1, 1, 1, 4, 4, 4], [1, 1, 1, 4, 8], [1, 1, 1, 5, 7], [1, 1, 1, 6, 6], [1, 1, 1, 12], [1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 7], [1, 1, 2, 2, 3, 3, 3], [1, 1, 2, 2, 3, 6], [1, 1, 2, 2, 4, 5], [1, 1, 2, 2, 9], [1, 1, 2, 3, 3, 5], [1, 1, 2, 3, 4, 4], [1, 1, 2, 3, 8], [1, 1, 2, 4, 7], [1, 1, 2, 5, 6], [1, 1, 2, 11], [1, 1, 3, 3, 3, 4], [1, 1, 3, 3, 7], [1, 1, 3, 4, 6], [1, 1, 3, 5, 5], [1, 1, 3, 10], [1, 1, 4, 4, 5], [1, 1, 4, 9], [1, 1, 5, 8], [1, 1, 6, 7], [1, 1, 13], [1, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 6], [1, 2, 2, 2, 3, 5], [1, 2, 2, 2, 4, 4], [1, 2, 2, 2, 8], [1, 2, 2, 3, 3, 4], [1, 2, 2, 3, 7], [1, 2, 2, 4, 6], [1, 2, 2, 5, 5], [1, 2, 2, 10], [1, 2, 3, 3, 3, 3], [1, 2, 3, 3, 6], [1, 2, 3, 4, 5], [1, 2, 3, 9], [1, 2, 4, 4, 4], [1, 2, 4, 8], [1, 2, 5, 7], [1, 2, 6, 6], [1, 2, 12], [1, 3, 3, 3, 5], [1, 3, 3, 4, 4], [1, 3, 3, 8], [1, 3, 4, 7], [1, 3, 5, 6], [1, 3, 11], [1, 4, 4, 6], [1, 4, 5, 5], [1, 4, 10], [1, 5, 9], [1, 6, 8], [1, 7, 7], [1, 14], [2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 7], [2, 2, 2, 3, 3, 3], [2, 2, 2, 3, 6], [2, 2, 2, 4, 5], [2, 2, 2, 9], [2, 2, 3, 3, 5], [2, 2, 3, 4, 4], [2, 2, 3, 8], [2, 2, 4, 7], [2, 2, 5, 6], [2, 2, 11], [2, 3, 3, 3, 4], [2, 3, 3, 7], [2, 3, 4, 6], [2, 3, 5, 5], [2, 3, 10], [2, 4, 4, 5], [2, 4, 9], [2, 5, 8], [2, 6, 7], [2, 13], [3, 3, 3, 3, 3], [3, 3, 3, 6], [3, 3, 4, 5], [3, 3, 9], [3, 4, 4, 4], [3, 4, 8], [3, 5, 7], [3, 6, 6], [3, 12], [4, 4, 7], [4, 5, 6], [4, 11], [5, 5, 5], [5, 10], [6, 9], [7, 8], [15]]

Catalogue

L'extrait de pile au bas de cet article génère le catalogue à partir des réponses a) comme une liste des solutions les plus courtes par langue et b) comme un classement général.

Pour vous assurer que votre réponse s'affiche, veuillez commencer votre réponse avec un titre, en utilisant le modèle Markdown suivant:

## Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les barrant. Par exemple:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Afficher l'extrait de code

code-golf math number-theory combinatorics integer-partitions DJMcMayhem
la source
1
Connexe: codegolf.stackexchange.com/questions/46991/…
DJMcMayhem
2
Pourriez-vous clarifier ce que vous entendez par poignée ?
Dennis
@flawr Je ne suis pas d'accord - trouver toutes les partitions est suffisamment différent de trouver des partitions strictes. Cependant, celui-ci pourrait être une cible dupe.
Mego
Je pense que chercher des partitions non ordonnées et ne pas limiter le nombre de parties rend cela assez différent.
xnor
Pouvez-vous clarifier ce que vous entendez par buitine ?
Leaky Nun

Réponses:

6

Pyth, 10 9 octets

{SMlMM./U

Je ne sais pas trop si ce n'est pas de la triche, mais les règles ont seulement dit que l'on ne peut pas utiliser la partition entière (ce n'est pas clairement indiqué dans la question elle-même, mais un commentaire d'OP dans la question dit partition entière). J'utilise une partition de liste de chaînes , ce qui crée des tranches de la liste qui concaténent jusqu'à la liste "mère". Je pense que je dois remercier @Maltysen pour l'idée d'utiliser des listes plutôt que des chaînes.

n = 15 prend moins d'une seconde sur ma machine.

Dans le pseudocode de flux de données:

              input       // initial data
        U     range       // makes a list of length equal to input
      ./      partition   // partitions string
   lMM        length      // length of each substring in each way to partition
 SM           sort        // sort each way to partition
{             deduplicate // removes all duplicate after sorting
              print       // implicit, output final result

Essayez-le en ligne ici.

busukxuan
la source
{mSlMd./*Nenregistre un octet
Leaky Nun
Vous pouvez opter pour 7 octets si vous utilisez le partitionnement de liste au lieu de la partition de chaîne: pyth.herokuapp.com/?code=sMM.%2Fm1&input=5&debug=0
Maltysen
@LeakyNun Eh bien, j'ai essayé et cela n'a pas sauvé un octet. Quand j'ai vu votre commentaire, j'ai découvert que ma réponse était en fait de 10 octets, donc j'ai fait une erreur de calcul (j'ai oublié les blocs gedit à partir de 1).
busukxuan
@Maltysen Vous devez trier chaque sous-liste, puis dédupliquer.
busukxuan
@Maltysen Vous aviez raison, utiliser des listes le raccourcit. J'ai essayé d'ajouter le tri et la déduplication au code auquel vous avez lié et cela n'a pas aidé, mais c'est grâce à vous que j'ai eu l'idée de remplacer * N par U. Merci!
busukxuan
6

Pyth, 18 octets

L?b{SM+R-bsdsyMb]Y

Essayez-le en ligne! (Le yà la fin est utilisé pour appeler la fonction)

C'est assez rapide.

Cela utilise la récursivité. Si l'entrée est b, ma méthode générera les partitions de 0à b-1, puis générera les partitions correctes à partir de chacune.

Par exemple, lorsque b=4:

  • b=0 donne [[]]
  • b=1 donne [[1]]
  • b=2 donne [[2], [1, 1]]
  • b=3 donne [[3], [1, 2], [1, 1, 1]]

Ensuite, à chaque partition dans b=0, ajoutez 4(pour faire la somme 4); à chaque partition b=1, ajoutez 3(pour faire la somme 4); etc.

C'est principalement ainsi que cela fonctionne.

L?b{SM+R-bsdsyMb]Y

L                    define a function called "y" which takes an argument: "b"
 ?b                  test for truthiness of b (in this case, test if b>0).


   {SM+R-bsdsyMb     if truthy:

             yMb         call this function from 0 to b-1.
            s            unpack each list of partitions, generating only partitions.
      +R                 to each partition (d), append:
        -                    the difference of
         b                   b (the argument) and
          sd                 the sum of d (the partition).
    SM                   sort each partition.
   {                     remove duplicates.


                ]Y   if falsey:

                 Y       yield [].
                ]        yield [[]].
Leaky Nun
la source
5

MATL , 20 octets

:"0Gq:@XNG3$Yc!dS!Xu

Essayez-le en ligne!

Pour l'entrée, 15cela prend environ 2 secondes dans le compilateur en ligne.

Explication

Cela fonctionne en générant des points de partition puis en les convertissant en longueurs de partition . Ce que je veux dire par là est le suivant. Étant donné l'entrée N = 5, une partition possible est [2 2 1]. Ceci est représenté par des points de partition [0 2 4 5], de sorte que des différences (ou longueurs) consécutives des points de partition donnent la partition résultante du numéro d'entrée.

Tous les tableaux de points de partition commencent par 0 et se terminent par N . Le nombre k de points intermédiaires varie de 0 à N -1. Pour N et k donnés, les points intermédiaires peuvent être générés comme une combinaison des nombres [1, 2, ..., N -1] pris k à la fois.

Plusieurs tableaux de points de partition peuvent donner lieu au même résultat dans un ordre différent. Par exemple, les points de partition [0 1 3 5] donneraient les longueurs de partition [1 2 2], c'est-à-dire les mêmes que les [2 2 1] précédents uniquement dans un ordre différent. Cela doit être pris en compte en triant chaque tableau de longueurs de partition et en supprimant les doublons .

:        % Implicitly input N. Push [1 2 ... N]. These are the possible values of k,
         % except with N instead of 0
"        % For each
  0      %   Push 0
  Gq:    %   Push [1 ... N-1]. These the possible intermediate points
  @XN    %   Push k and produce the combinations. Each k produces a 2D array with
         %   each combination on a row. The value k=N produces an empty array
  G      %   Push N
  3$Yc   %   Prepend a column of zeros and append a column of N to the array
  !d     %   Transpose. Consecutive differences of each column
  S!     %   Sort each column. Transpose
  Xu     %   Keep only unique rows
         % Implicitly end for and display all arrays in the stack
Luis Mendo
la source
1
Bien, le concept de points de partition est un moyen très intelligent de résoudre ce problème.
Nick
@Nick Merci! Et bienvenue sur (être actif dans) ce site! :-)
Luis Mendo
5

Haskell, 53 octets

p=[[]]:[map(1:)q++[a+1:b|a:b<-q,all(a<)b]|q<-p]
(p!!)
Anders Kaseorg
la source
5

J, 49 42 36 35 32 octets

a:1&([:~.@,(,;}./:~@,(+{.))&>)~]

C'est tacite maintenant!

Construit la partition entière de n en construisant les partitions entières de 1 à n . Calcule le résultat pour n = 15 en une milliseconde.

En commençant par la partition entière initiale [[1]]qui correspond à n = 1, construisez la partition entière suivante en joignant les résultats de deux opérations: en ajoutant un 1 à chaque partition; incrémenter la plus petite valeur de 1 dans chaque partition. Bien sûr, les partitions en double seront supprimées. Pour obtenir la partition entière n = 2 et au-delà,

Partition for n = 1
[[1]]

Partition for n = 2
[[1, 1]] join [[2]]
= [[1, 1], [2]]

Partition for n = 3
[[1, 2], [1, 1, 1]] join [[3], [1, 2]]
= [[3], [1, 2], [1, 1, 1]]

... and so on

Usage

   f =: a:1&([:~.@,(,;}./:~@,(+{.))&>)~]
   f 1
┌─┐
│1│
└─┘
   f 2
┌───┬─┐
│1 1│2│
└───┴─┘
   f 3
┌─────┬───┬─┐
│1 1 1│1 2│3│
└─────┴───┴─┘
   f 5
┌─────────┬───────┬─────┬───┬─────┬───┬─┐
│1 1 1 1 1│1 1 1 2│1 2 2│2 3│1 1 3│1 4│5│
└─────────┴───────┴─────┴───┴─────┴───┴─┘
   # f 15
176

Explication

Étant donné que J ne prend pas en charge les tableaux irréguliers, chaque partition doit être encadrée afin de ne pas être remplie de zéro lorsqu'elle est ajoutée à d'autres partitions.

a:1&([:~.@,(,;}./:~@,(+{.))&>)~]  Input: n
a:                                The empty box
                               ]  Get the input n
  1&(                        )~   Repeat n times with an initial array of one empty box
           (              )&>       Operate on each partition
                     (   )            Hook a partition
                       {.               Get its head (the smallest value)
  1                   +                 Add 1 to it
  1           }.                      Drop the first value in each partition
                    ,                 Join the previous two results
                /:~@                  Sort it
  1         ,                         Prepend a 1 to the initial partition
             ;                        Box the last two results and join them
     [:   ,                         Flatten the pairs of boxes
       ~.@                          Remove duplicates and return
                                  Return the final result where each box
                                  is a partition of n
miles
la source
4

Python, 65 octets

Python 3

def f(n,i=1,l=[]):n or print(l);i>n or[f(n-i,i,[i]+l),f(n,i+1,l)]

Cette fonction accumule une partition et imprime les sorties, en se ramifiant sur les choix. Il décide du nombre de 1 à mettre dans la partition, du nombre de 2, etc. Pour chaque valeur i, soit

  • Ajoute une partie de la taille iet diminue nà n-i, ou
  • Passe à i+1

Si i>n, alors plus aucune pièce ne peut être fabriquée, cela s'arrête. Si ntombe à 0, la partition réussit et est donc imprimée.

Python 2

f=lambda n,i=1:n/i and[l+[i]for l in f(n-i,i)]+f(n,i+1)or[[]][n:]

Une méthode récursive qui génère une liste de partitions. Comme avec le code Python 3, il compte la taille de la pièce iet décide à chaque étape s'il faut ajouter une autre partie de la taille iou s'arrêter.

Les deux font n=15presque instantanément.

xnor
la source
3

Javascript, 194 octets

p=n=>{var a=[];for(var i=1;i<=n-i;i+=1){for(v of p(n-i)){v.push(i);a.push(v.sort())}}a.push([n]);return a};n=5;s=p(n).map(v=>JSON.stringify(v));s=s.filter((v,i)=>s.indexOf(v)==i);console.log(s);

Non minifié

Trouver des uniques en les triant et en les comparant à une chaîne est un vrai hack, mais économise probablement de l'espace.

p = n => {
    var a = [];

    for (var i = 1; i <= n-i; i++)
    {
        for (v of p(n-i)) {
            v.push(i);
            a.push(v.sort());
        }
    }

    a.push([n]);

    return a;
}

n = 5;
s = p(n).map(v =>  JSON.stringify(v));
s = s.filter((v,i) => s.indexOf(v) == i);
console.log(s);
Entaille
la source
4
Quite a hack but saves spaceC'est exactement de cela qu'il s'agit. : D
DJMcMayhem
2

Python 3.5, 82 72 octets

f=lambda n:{(*sorted([*p,i]),)for i in range(1,n)for p in f(n-i)}|{(n,)}

Renvoie un ensemble de tuples. n = 15 se termine instantanément.

Testez - le sur repl.it .

Dennis
la source
2

Haskell, 44 octets

0%m=[[]]
n%m=[j:r|j<-[m..n],r<-(n-j)%j]
(%1)

La fonction auxiliaire n%mdonne les partitions de nen parties ≥m, la fonction principale utilisant m=1. Il branche de chaque première entrée javec m≤j≤n, récursif sur la partition restante de n-jen parties qui sont au moins j. Le cas de base n==0donne juste la partition vide.

xnor
la source
1

Pyth, 17 octets

L|{SMs+LVrb0yMb]Y

Définit une fonction nommée y. Essayez-le en ligne .

Anders Kaseorg
la source
1

Gelée , 9 octets

b1ŒṖḅ1Ṣ€Q

Essayez-le en ligne!

Comment ça marche

b1ŒṖḅ1Ṣ€Q  Main link. Argument: n (integer)

b1         Convert n to unary, i.e., a list A of n 1's.
  ŒṖ       Generate all partitions of the list A.
    ḅ1     Convert each flat list from unary to integer.
      Ṣ€   Sort each resulting list.
        Q  Unique; deduplicate the lists.
Dennis
la source
1

J, 39 octets

[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:

Il s'agit d'un verbe monadique qui prend un entier et renvoie un tableau de tableaux encadrés. Essayez-le ici. Usage:

   p =: [:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:
   p 3
+-----+---+-+
|1 1 1|2 1|3|
+-----+---+-+

Sur l'entrée 15, il fonctionne pendant environ une seconde sur ma machine.

Explication

Ce défi ressemblait immédiatement à un travail pour Catalog ( {) et Cut ( ;.). Le contour de l'algorithme est:

  • Produisez tous les tableaux 0-1 de longueur n.
  • Pour chacun d'eux, coupez un ntableau de longueurs fictif le long des 1 et énumérez les longueurs de chaque partie.
  • Triez les longueurs et supprimez les tableaux en double du résultat.

Apparemment, Luis Mendo avait aussi la même idée .

Explication du code:

[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:   Input is n.
                                     <:   n-1
                                   #~     copies of
                             (<1 0)       the boxed array [1 0].
                       1    ;             Prepend the boxed array [1].
                          {@              Catalog: produces all combinations of taking one
                                          item from each box, in a high-dimensional matrix.
                        ,@                Flatten the matrix. This results in a list of all
                                          boxed 0-1 arrays of length n that begin with a 1.
    i.                                    The array A =: 0, 1, ..., n-1.
            (     "1 0)                   For each of the boxed arrays B:
              ;.1~                          cut A along the occurrences of 1s in B,
             #                              take the length of each part,
        \:~@                                sort the lengths,
      <@                                    and put the result in a box.
[:~.                                      Remove duplicate boxes.
Zgarb
la source
Très belle utilisation de la coupe à ;.nouveau.
miles
1

Brachylog , 33 octets (non concurrent)

:1f:oad.
:1eI,.##lI,.:{.>0}a+?,.=

Ce n'est pas en concurrence en raison d'une correction de bogue.

Cela prend environ 1 seconde 15sur ma machine. Pour 20et plus, cela se bloque avec une Out of global stackexception.

Explication

Cela n'utilise aucun partitionnement intégré d'aucune sorte, et utilise à la place le fait que cela +fonctionne dans les deux sens via la propagation des contraintes.

  • Prédicat principal:

    :1f                       Find the list of all valid outputs of predicate 1
   :oa                    Sort each element of that list
      d.                  Output is that list of sorted lists minus all duplicates

  • Prédicat 1:

    :1eI                      I is an integer between Input and 1
    .##lI,                Output is a list of length I
          .:{.>0}a        Elements of Output are integers greater than 0
                  +?,     The sum of the elements of Output is Input
                     .=   Assign values to the elements of Output
Fatalize
la source
1

Mathematica, 62 54 octets

Inner[#2~Table~#&,FrobeniusSolve[r=Range@#,#],r,Join]&

Les partitions d'un entier n peuvent être trouvées en résolvant pour n -tuples d'entiers non négatifs ( c 1 , c 2 , ..., c n ) tels que c 1 + 2 c 2 + ... + n c n = n . FrobeniusSolveest capable de trouver toutes les solutions à cette équation qui sont utilisées pour créer autant de copies de leurs valeurs respectives afin de trouver toutes les partitions entières de n .

miles
la source
... et comment cela n'est-il pas intégré?
Leaky Nun
@LeakyNun FrobeniusSolvene trouve pas de partitions entières, il trouve toutes les solutions d'entiers non négatifs x1 ... xN aux équations de la forme a1 x1 + a2 x2 + ... aN xN = bdonnée a1 ... aNet b.
miles
0

JavaScript (Firefox 30-57) 79 ES6, 65 octets

f=(n,m=1,a=[])=>n?m>n?[]:[...f(n-m,m,[...a,m]),...f(n,m+1,a)]:[a]

Port de la solution Python @ xnor. (Si seulement j'avais remarqué que vous pouviez récuser maussi bien que n...)

Neil
la source