À propos de la série

Tout d'abord, vous pouvez traiter cela comme n'importe quel autre défi de golf de code et y répondre sans vous soucier de la série. Cependant, il existe un classement pour tous les défis. Vous pouvez trouver le classement avec plus d'informations sur la série dans le premier post .

Bien que j'ai un tas d'idées alignées pour la série, les défis futurs ne sont pas encore gravés dans le marbre. Si vous avez des suggestions, faites-le moi savoir sur le post sandbox correspondant .

Trou 3: partitions entières

Il est temps d'augmenter un peu la difficulté.

Une partition d'un entier positif nest définie comme un ensemble multiple d'entiers positifs qui se résument à n. Par exemple, si n = 5, les partitions suivantes existent:

{1,1,1,1,1}
{2,1,1,1}
{2,2,1}
{3,1,1}
{3,2}
{4,1}
{5}

Notez que ce sont des multisets, donc il n'y a pas d'ordre {3,1,1}, {1,3,1}et ils {1,1,3}sont tous considérés comme identiques.

Votre tâche est, étant donné n, de générer une partition aléatoire de n. Voici les règles détaillées:

• La répartition des cloisons produites doit être uniforme . Autrement dit, dans l'exemple ci-dessus, chaque partition doit être renvoyée avec une probabilité 1/7.

  Bien sûr, en raison des limites techniques des PRNG, une uniformité parfaite sera impossible. Aux fins d'évaluer l'uniformité de votre soumission, les opérations suivantes seront considérées comme produisant des distributions parfaitement uniformes:

  • Obtention d'un numéro à partir d'un PRNG (sur n'importe quelle plage), qui est documenté comme étant (approximativement) uniforme.
  • Mapper une distribution uniforme sur un ensemble de nombres plus grand sur un ensemble plus petit via modulo ou multiplication (ou une autre opération qui distribue les valeurs uniformément). L'ensemble plus grand doit contenir au moins 1024 fois autant de valeurs possibles que l'ensemble plus petit.

• Étant donné que les partitions sont des ensembles multiples, vous pouvez les renvoyer dans n'importe quel ordre, et cet ordre n'a pas à être cohérent. Cependant, aux fins de la distribution aléatoire, l'ordre est ignoré. Autrement dit, dans l'exemple ci-dessus {3,1,1}, {1,3,1}et {1,1,3} ensemble doivent avoir une probabilité de 1/7 d'être retourné.

• Votre algorithme doit avoir un runtime déterministe. En particulier, vous ne pouvez pas générer de multisets aléatoires et les rejeter s'ils ne correspondent pas n.
• La complexité temporelle de votre algorithme doit être polynomiale n. En particulier, vous ne pouvez pas simplement générer toutes les partitions et en sélectionner une au hasard (car le nombre de partitions croît de façon exponentielle avec n). Vous pouvez supposer que le PRNG que vous utilisez peut renvoyer des valeurs uniformément réparties en O (1) par valeur.
• Vous ne devez utiliser aucune fonction intégrée qui résout cette tâche.

Vous pouvez écrire un programme complet ou une fonction et prendre une entrée via STDIN ou l'alternative la plus proche, l'argument de ligne de commande ou l'argument de fonction et produire une sortie via la valeur de retour ou en imprimant vers STDOUT (ou l'alternative la plus proche).

Vous pouvez supposer que n ≤ 65(tel que le nombre de partitions est inférieur à 2 ²¹ ). La sortie peut être dans n'importe quelle liste ou format de chaîne pratique et sans ambiguïté.

Si vous soumettez une fonction, veuillez également envisager de fournir un petit programme de test qui appelle la fonction plusieurs fois et imprime les résultats. Ce n'est pas grave si les paramètres doivent être modifiés dans le code. C'est juste pour que les gens puissent vérifier que la solution est au moins approximativement uniforme.

Il s'agit du code golf, donc la soumission la plus courte (en octets) l'emporte. Et bien sûr, la soumission la plus courte par utilisateur entrera également dans le classement général de la série.

Classement

Le premier post de la série génère un classement.

Pour vous assurer que vos réponses s'affichent, veuillez commencer chaque réponse par 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 rayant. Par exemple:

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

(La langue n'est pas actuellement affichée, mais l'extrait de code l'exige et l'analyse, et je pourrai ajouter un classement par langue à l'avenir.)

Python 2, 179 octets

from random import*
m=r=input();i=q=r+1;h=[1]+[0]*q*q;exec"h[i]=h[i+~q]+h[i-i%q*q];i+=1;"*r*q
while r:
 x=random()*sum(h[r*q:r*q-~m]);m=0
 while x>0:m+=1;x-=h[r*q+m]
 print m;r-=m

J'ai utilisé la formule (39) de cet extrait de Knuth , qui donne le nombre de partitions nqui ont exactement des mparties. Cela arrive à égaler le nombre de partitions nqui ont mcomme élément maximum, ce qui est l'interprétation que j'utilise. Les éléments de la partition sont générés du plus grand au moins. À chaque étape, la formule est réutilisée avec le reste actuel net l'élément maximal autorisé.

Dyalog APL, 67 59 51 octets

p←{⍵,⊂1,⍨+/¨⌽⍵↑¨⍨⌽⍳⍴⍵}⍣⎕⊢⍬⋄f←{⍵=0:⍬⋄a,a∇⍵-a←{1++/(?+/⍵)>+\⍵}⍺↑⍵⊃p}⍨ (67 octets)

pest un vecteur de vecteurs dans lequel p[n][k]est le nombre de partitions de nen ksommets, ou de façon équivalente: le nombre de partitions avec le plus grand sommet k. Nous construisons pen commençant par le vecteur vide ⍬, en lisant n(l' ⎕entrée de lectures) et en appliquant à plusieurs reprises les éléments suivants:

{⍵,⊂1,⍨+/¨⌽⍵↑¨⍨⌽⍳⍴⍵}
                 ⍴⍵   ⍝ the current length, initially 0
                ⍳⍴⍵   ⍝ 1 2 ... length
               ⌽⍳⍴⍵   ⍝ length ... 2 1
           ⍵↑¨⍨       ⍝ take length elements from p[1], length-1 from p[2], etc
                      ⍝ padded with 0-s, e.g. if p was (,1)(1 1)(1 1 1)(1 2 1 1)(1 2 2 1 1):
                      ⍝ we get:     (1 0 0 0 0)(1 1 0 0)(1 1 1)(1 2)(,1)
          ⌽           ⍝ reverse it: (,1)(1 2)(1 1 1)(1 1 0 0)(1 0 0 0 0)
       +/¨            ⍝ sum each:   1 3 3 2 1
    1,⍨               ⍝ append 1:   1 3 3 2 1 1
 ⍵,⊂                  ⍝ append the above to the vector of vectors

Après napplications ( ⍣⎕), nous avons construitp .

fchoisit une partition aléatoire. n f kest une partition aléatoire d' au plus k sommets. f nest n f n.

{⍵=0:⍬⋄a,a∇⍵-a←{1++/(?+/⍵)>+\⍵}⍺↑⍵⊃p}⍨
                                     ⍨ ⍝ "selfie" -- use n as k if no k is provided
 ⍵=0:⍬                                 ⍝ if n=0 return empty
                                 ⍵⊃p   ⍝ pick the n-th element of p
                               ⍺↑      ⍝ take k elements from that
               {1++/(?+/⍵)>+\⍵}        ⍝ use them as weights to pick a random number 1...k
               {           +\⍵}        ⍝   partial sums of weights
               {    (?+/⍵)    }        ⍝   a random number 1...sum of weights
               {    (?+/⍵)>+\⍵}        ⍝   which partial sums is it greater than?
               {  +/          }        ⍝   count how many "greater than"-s
               {1+            }        ⍝   we're off by one
             a←                        ⍝ this will be the greatest number in our partition
         a∇⍵-a                         ⍝ recur with n1=n-a and k1=a
       a,                              ⍝ prepend a

Quelques améliorations:

• en ligne p au prix de performances légèrement pires (mais toujours assez bonnes)

• dans le calcul de préorganiser ⌽et1, de sauvegarder un caractère

• se transformer {1++/(?+/⍵)>+\⍵}en train avec 1+devant:1+(+/(?+/)>+\)

• faire fune fonction anonyme et fournir ⎕(entrée évaluée) comme argument pour obtenir un programme complet

{⍵=0:⍬⋄a,a∇⍵-a←1+(+/(?+/)>+\)⍺↑⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬}⍨⎕ (59 octets)

Test avec n = 5

Test avec n = 65

Et le lien suivant s'exécute n = 5 milliers de fois et rassemble des statistiques sur la fréquence de chaque partition: ⎕rl←0 ⋄ {⍺,⍴⍵}⌸ {⍵=0:⍬⋄a,a∇⍵-a←1+(+/(?+/)>+\)⍺↑⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬}⍨ ¨10000⍴5

Plus d'améliorations, avec l'aide de Roger Hui :

• remplacer {⍵=0:A⋄B}par {×⍵:B⋄A}. Signum ( ×⍵) renvoie vrai pour ⍵>0et faux pour⍵=0 .

• remplacer (+/(?+/)>+\)par+/b<?⊃⌽b←+\ , il enregistre un personnage

• utiliser une matrice au lieu d'un vecteur de vecteurs pour calculer p: remplacer ⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬par ⊃↓(0,⍨⊢⍪⍨1 1⍉+\)⍣⍵⍪1.

{×⍵:a,a∇⍵-a←1++/b<?⊃⌽b←+\⍺↑⊃↓(0,⍨⊢⍪⍨1 1⍉+\)⍣⍵⍪1⋄⍬}⍨ (51 octets)

test n = 5 ; test n = 65 ; statistiques freq

GolfScript, 90 octets

~[[[1.]]]\({..[[{{(\{)}%+}%1$,1$,-=}%[1,]@0=+{1+}%]zip{{(\.,/*~}%.,.rand@=+}:^%]\+}*0=^(;`

Démo en ligne

Il s'agit d'une adaptation de mon code de comptage de partition (plus simple) qui, au lieu de simplement suivre un compte, suit à la fois un compte et un élément uniformément sélectionné parmi les éléments comptés.

Comparaison côte à côte des deux:

~[[[1.]]]\({..[[{{(\{)}%+}%1$,1$,-=}%[1,]@0=+{1+}%]zip{{(\.,/*~}%.,.rand@=+}:^%]\+}*0=^(;`
 [[ 1  ]]\({..[[{          1$,1$,-=}%  0 @0=+     ]zip{{+}*                }:^%]\+}*0=^

Différences:

• La première ~est que c'est un programme plutôt qu'un extrait de code.
• Le [1.]remplacement 1correspond au changement de ce qui est suivi.
• Les {(\{)}%+}%incréments supplémentaires incrémentent chaque élément de cette partition et les {1+}%ajouts 1à la partition.
• 0devient [0](joué au golf 1,) dans le cadre du changement de ce qui est suivi, mais parce qu'il doit rester un tableau lorsqu'il est ajouté à un autre, il a besoin de plus [ ].
• La somme simple {+}*devient une sélection pondérée à partir des partitions, combinée à une somme de leur nombre.
• Le (;`supprime le nombre de la sortie et place la partition dans un format agréable.

Cadre de test

;7000,{;
  '5'

  ~[[[1.]]]\({..[[{{(\{)}%+}%1$,1$,-=}%[1,]@0=+{1+}%]zip{{(\.,/*~}%.,.rand@=+}:^%]\+}*0=^(;`

}%
:RESULTS
.&${
  RESULTS.[2$]--,' '\n
}/

Modifiez le 7000 initial si vous souhaitez exécuter un nombre différent d'essais. Notez que c'est beaucoup trop lent pour une démo en ligne.

Java, 285 267 octets

int[][]p;void p(int n){p=new int[n+1][n+1];int a=n,b=k(n,a),c,d;for(b*=Math.random();n>0;System.out.print(c+" "),n-=a=c)for(c=0;c++<(a<n?a:n)&b>=(d=k(n-c,c));b-=d);}int k(int n,int k){if(p[n][k]<1)for(int a=0,b=0;b<k&b++<n;p[n][k]=a)a+=k(n-b,b);return n>0?p[n][k]:1;}

Il s'agit de la même méthode que la réponse de TheBestOne, mais elle utilise un tableau simple au lieu d'une carte. De plus, au lieu de renvoyer la partition aléatoire en tant que a List, il les imprime sur la console.

Voici un programme de test qui l'exécute 100000 fois. Pour l'exemple n=5, tous les sets étaient à 0,64% d'un 1/7 parfait lors de ma dernière course.

public class Partition {
    public static void main(String[] args) {
        Partition p = new Partition();
        for(int i=0;i<100000;i++){
            p.p(5);
            System.out.println();
        }
    }

    int[][]p;

    void p(int n){
        p=new int[n+1][n+1];
        int a=n,b=k(n,a),c,d;
        for(b*=Math.random();n>0;System.out.print(c+" "),n-=a=c)
            for(c=0;c++<(a<n?a:n)&b>=(d=k(n-c,c));b-=d);
    }

    int k(int n,int k){
        if(p[n][k]<1)
            for(int a=0,b=0;b<k&b++<n;p[n][k]=a)
                a+=k(n-b,b);
        return n>0?p[n][k]:1;
    }

}

CJam, 64 56 octets

ri_L{_0>{\,f{)_@1$-j+}{)@)2$+:Umr@<@@?U+}*}{!a\;}?}2j);p

Vous pouvez le tester avec ce script:

ria100*{_L{_0>{\,f{)_@1$-j+}{)@)2$+:Umr@<@@?U+}*}{!a\;}?}2j);}%__|\f{_,\2$a-,-}2/p

Explication

ri_                  " Read an integer and duplicate. ";
L{                   " Create a memoized function of the maximum and the sum, which returns
                       a random partition, and the total number of partitions as the last item. ";
    _0>              " If sum > 0: ";
    {
        \,f{         " For I in 0..max-1: ";
            )_@1$-   " Stack: I+1 I+1 sum-I-1 ";
            j+       " Recursively call with the two parameters, and prepend I+1. ";
        }
        {            " Reduce on the results: ";
            )@)2$+   " Stack: partition1 total1 partition2 total1+total2 ";
            :Umr     " U = total1+total2, then generate a random number smaller than that. ";
            @<@@?    " If it is <total1, choose partition1, else choose partition2. ";
            U+       " Append the total back to the array. ";
        }*
    }
    {!a\;}?          " Else return [0] if negative, or [1] if zero. ";
}2j
);p                  " Discard the total and print. ";

Pyth, 64 octets

Utilise /programming//a/2163753/4230423 sauf que a) Pas de cache puisque Pyth mémorise automatiquement, b) Imprime chacun au lieu de l'ajouter à la liste, et c) est traduit en Pyth.

M?smg-Gddr1hhS,GHG1Akd,QOgQQWQFNr1hhS,QkKg-QNNI<dKB-=dK)N=kN-=QN

Je posterai une explication de cela quand j'aurai le temps, mais voici le code python correspondant:

g=lambda G,H: sum(map(lambda d:g(G-d, d), range(1, (H if H<G else G) + 1))) if G else 1
Q=input()
k,d = Q,random.randrange(g(Q, Q))
while Q:
    for N in range(1, min(k, Q) + 1):
        K = g(Q-N, N)
        if d < K:
            break
        d -= K
    print N
    k=N
    Q -= N

Edit: j'ai finalement réussi à faire l'explication:

M                Lambda g(G,H)
 ?         G     If G truthy
  s              Sum
   m             Map
    g            Recursive call
     -Gdd        G-d,d
    r            Range
     1           1 to
     h           +1
      hS         First element of sorted (does min)
       ,GH       From G and H
   1             Else 1
A                Double assign
 kd              Vars k and d
 ,               To vals
  Q              Q (evaled input)
  O              Randrange 0 till val
   gQQ           Call g(Q, Q)
WQ               While Q is truthy
 FN              For N in
  r              Range
   1             From one
   h             Till +1
    hS,QK        Min(Q,K)
  Kg             K=g(
   -QN           Q-N
   N             N
  I<dK           If d<k
   B             Break (implicit close paren)
  -=dk           Subtracts d-=k
 )               Close out for loop
 N               Prints N
 =kN             Set k=N
 -=QN            Subtracts Q-=N

Octave, 200

function r=c(m)r=[];a=eye(m);a(:,1)=1;for(i=3:m)for(j=2:i-1)a(i,j)=a(i-1,j-1)+a(i-j,j);end;end;p=randi(sum(a(m,:)));while(m>0)b=a(m,:);c=cumsum(b);x=min(find(c>=p));r=[r x];p=p-c(x)+b(x);m=m-x;end;end

Non golfé:

function r=c(m)
  r=[];
  a=eye(m);
  a(:,1)=1;
  for(i=3:m)
    for(j=2:i-1)
      a(i,j)=a(i-1,j-1)+a(i-j,j);
    end;
  end;
  p=randi(sum(a(m,:)));
  while(m>0)
    b=a(m,:);
    c=cumsum(b);
    x=min(find(cumsum(b)>=p));
    r=[r x];
    p=p-c(x)+b(x);
    m=m-x;
  end
end

Construisez une matrice carrée où chaque cellule (m, n) reflète le nombre de partitions mdont le plus grand nombre est n, selon l'extrait de Knuth @feersum si gentiment cité. Par exemple, 5,2nous donne 2 car il y a deux partitions valides 2,2,1et 2,1,1,1. 6,3nous donne 3 pour 3,1,1,1, 3,2,1et3,3 .

Nous pouvons maintenant trouver de façon déterministe la pème partition. Ici, nous générons pun nombre aléatoire, mais vous pouvez modifier légèrement le script, tout pcomme un paramètre:

function r=c(m,p)
  r=[];
  a=eye(m);
  a(:,1)=1;
  for(i=3:m)
    for(j=2:i-1)
      a(i,j)=a(i-1,j-1)+a(i-j,j);
    end;
  end;
  while(m>0)
    b=a(m,1:m);
    c=cumsum(b);
    x=min(find(c>=p));
    r=[r x];
    p=p-c(x)+b(x);
    m=m-x;
  end
end

Nous pouvons maintenant montrer de façon déterministe que chaque résultat dépend uniquement de p:

octave:99> for(i=1:7)
> c(5,i)
> end
ans =

   1   1   1   1   1

ans =

   2   1   1   1

ans =

   2   2   1

ans =

   3   1   1

ans =

   3   2

ans =

   4   1

ans =  5

Ainsi, pour revenir à l'original où p est généré de façon aléatoire, nous pouvons être assurés que chaque résultat est également probable.

R, 198 octets

function(m){r=c();a=diag(m);a[,1]=1;for(i in 3:m)for(j in 2:(i-1))a[i,j]=a[i-1,j-1]+a[i-j,j];p=sample(sum(a[m,]),1);while(m>0){b=a[m,];c=cumsum(b);x=min(which(c>=p));r=c(r,x);p=p-c[x]+b[x];m=m-x};r}

Non golfé:

f <- function(m) {
    r <- c()
    a <- diag(m)
    a[, 1] <- 1
    for (i in 3:m)
        for (j in 2:(i-1))
            a[i, j] <- a[i-1, j-1] + a[i-j, j]
    p <- sample(sum(a[m, ]), 1)
    while (m > 0) {
        b <- a[m, ]
        c <- cumsum(b)
        x <- min(which(c >= p))
        r <- c(r, x)
        p <- p - c[x] + b[x]
        m <- m - x
    }
    return(r)
}

Il suit la même structure que la grande solution de @ dcsohl dans Octave , et est donc également basé sur le extrait de Knuth publié par @feersum.

J'éditerai cela plus tard si je peux trouver une solution plus créative dans R. En attendant, toute contribution est bien sûr la bienvenue.

Java, 392 octets

import java.util.*;Map a=new HashMap();List a(int b){List c=new ArrayList();int d=b,e=b(b,d),f=(int)(Math.random()*e),g,i;while(b>0){for(g=0;g++<Math.min(d, b);f-=i){i=b(b-g,g);if(f<i)break;}c.add(g);d=g;b-=g;}return c;}int b(int b,int c){if(b<1)return 1;List d=Arrays.asList(b,c);if(a.containsKey(d))return(int)a.get(d);int e,f;for(e=f=0;f++<Math.min(c, b);)e+=b(b-f,f);a.put(d,e);return e;}

Appeler avec a(n) . Renvoie unList deInteger s

Dentelé:

import java.util.*;

Map a=new HashMap();

List a(int b){
    List c=new ArrayList();
    int d=b,e=b(b,d),f=(int)(Math.random()*e),g,i;
    while(b>0){
        for(g=0;g++<Math.min(d, b);f-=i){
            i=b(b-g,g);
            if(f<i)
                break;
        }
        c.add(g);
        d=g;
        b-=g;
    }
    return c;
}

int b(int b,int c){
    if(b<1)
        return 1;
    List d=Arrays.asList(b,c);
    if(a.containsKey(d))
        return(int)a.get(d);
    int e,f;
    for(e=f=0;f++<Math.min(c, b);)
        e+=b(b-f,f);
    a.put(d,e);
    return e;
}

Adapté de /programming//a/2163753/4230423 et golfé

Comment cela fonctionne: Nous pouvons calculer combien de partitions d'un entier n il y a en temps O ( n ² ). Comme effet secondaire, cela produit un tableau de taille O ( n ² ) que nous pouvons ensuite utiliser pour générer la k ème partition de n , pour tout entier k , dans O ( n ).

Soit donc total = le nombre de partitions. Choisissez un nombre aléatoire k de 0 au total - 1. Générez la k ème partition.

Comme d'habitude , les suggestions sont les bienvenues :)

Python 2, 173 octets

from random import*
N,M=input__
R=67;d=[(0,[])]*R*R
for k in range(R*R):p,P=d[k+~R];q,Q=d[k-k%R*R];d[k]=p+q+0**k,[[x+1 for x in Q],[1]+P][random()*(p+q)<p]
print d[N*R+M][1]

Fait récursivement un dictionnaire d, avec des clés kreprésentant une paire (n,m)par k=67*n+m(en utilisant la garantie n<=65). L'entrée est le tuple du nombre de partition de ndansm parties, et une telle partition aléatoire. Les décomptes sont calculés par la formule récursive (merci à feersum de l'avoir signalé)

f(n,m) = f(n-1,m-1) + f(n,n-m),

et la partition aléatoire est mise à jour en choisissant l'une des deux de ses branches avec une probabilité proportionnelle à son comptage. La mise à jour se fait en ajoutant se fait en ajoutant un1 pour la première branche et en incrémentant chaque élément pour la seconde.

J'ai eu beaucoup de mal à obtenir des valeurs hors limites met nà donner des comptes de zéro. Au début, j'ai utilisé un dictionnaire par défaut à un nombre de 0 et une liste vide. Ici, j'utilise une liste et je la remplis avec cette entrée par défaut à la place. Les indices négatifs provoquent la lecture de la liste depuis sa fin, ce qui donne une entrée par défaut qui n'est rien près de la fin comme jamais atteinte, et les bouclages ne touchent qu'une région où m>n.

80386 code machine, 105 octets

Hexdump du code:

60 8b fa 81 ec 00 41 00 00 33 c0 8b f4 33 d2 42
89 14 06 42 33 ed 8b d8 03 2c 1e 2a fa 73 f9 83
c6 04 89 2c 06 42 3b d1 76 ea fe c4 3a e1 76 db
33 d2 0f c7 f0 f7 f5 86 e9 85 d2 74 1b 33 c0 8d
34 0c 39 14 86 77 03 40 eb f8 2b 54 86 fc 40 89
07 83 c7 04 2a e8 77 e1 42 89 17 83 c7 04 fe cd
7f f7 4a b6 41 03 e2 61 c3

En fonction de C: void random_partition(int n, int result[]);. Il renvoie le résultat sous la forme d'une liste de nombres dans le tampon fourni; cela ne marque en aucun cas la fin de la liste, mais l'utilisateur peut découvrir la fin en accumulant les nombres - la liste se termine lorsque la somme est égale àn .

Comment utiliser (dans Visual Studio):

#include <stdio.h>

__declspec(naked) void __fastcall random_partiton(int n, int result[])
{
#define a(byte) __asm _emit 0x ## byte
a(60) a(8b) a(fa) a(81) a(ec) a(00) a(41) a(00) a(00) a(33) a(c0) a(8b) a(f4) a(33) a(d2) a(42)
a(89) a(14) a(06) a(42) a(33) a(ed) a(8b) a(d8) a(03) a(2c) a(1e) a(2a) a(fa) a(73) a(f9) a(83)
a(c6) a(04) a(89) a(2c) a(06) a(42) a(3b) a(d1) a(76) a(ea) a(fe) a(c4) a(3a) a(e1) a(76) a(db)
a(33) a(d2) a(0f) a(c7) a(f0) a(f7) a(f5) a(86) a(e9) a(85) a(d2) a(74) a(1b) a(33) a(c0) a(8d)
a(34) a(0c) a(39) a(14) a(86) a(77) a(03) a(40) a(eb) a(f8) a(2b) a(54) a(86) a(fc) a(40) a(89)
a(07) a(83) a(c7) a(04) a(2a) a(e8) a(77) a(e1) a(42) a(89) a(17) a(83) a(c7) a(04) a(fe) a(cd)
a(7f) a(f7) a(4a) a(b6) a(41) a(03) a(e2) a(61) a(c3)
}

void make_stack() // see explanations about stack below
{
    volatile int temp[65 * 64];
    temp[0] = 999;
}

int main()
{
    int result[100], j = 0, n = 64, counter = n;
    make_stack(); // see explanations about stack below

    random_partiton(n, result);

    while (counter > 0)
    {
        printf("%d ", result[j]);
        counter -= result[j];
        ++j;
    }
    putchar('\n');
}

Exemple de sortie (avec n = 64):

21 7 4 4 3 3 3 3 2 2 2 2 2 1 1 1 1 1 1

Cela demande beaucoup d'explications ...

Bien sûr, j'ai utilisé l'algorithme que tout le monde a également utilisé; il n'y avait pas de choix avec l'exigence de complexité. Je n'ai donc pas besoin d'expliquer trop l'algorithme. En tous cas:

Je dénote par f(n, m)le nombre de partitionnements d' néléments utilisant des parties pas plus grand que m. Je les stocke dans un tableau 2D (déclaré en C commef[65][64] ), où se trouve le premier index net le second m-1. J'ai décidé que soutenirn=65 était trop difficile, alors abandonné ...

Voici le code C qui calcule ce tableau:

#define MAX_M 64
int f[(MAX_M + 1) * MAX_M];
int* f2;
int c; // accumulates the numbers needed to calculate f(n, m)
int m;
int k; // f(k, m), for various values of k, are accumulated
int n1;

for (n1 = 0; n1 <= n; ++n1)
{
    f2 = f;
    f2[n1 * MAX_M] = 1;
    for (m = 2; m <= n; ++m)
    {
        c = 0;
        k = n1;
        while (k >= 0)
        {
            c += f2[k * MAX_M];
            k -= m;
        }
        ++f2;
        f2[n1 * MAX_M] = c;
    }
}

Ce code a un style obscurci, il peut donc être facilement converti en langage assembleur. Il calcule les éléments jusqu'à f(n, n), qui est le nombre de partitionnements d' néléments. Lorsque ce code est terminé, la variable temporairec contient le nombre nécessaire, qui peut être utilisé pour sélectionner un partitionnement aléatoire:

int index = rand() % c;

Plus tard, ce index est converti au format requis (liste de nombres) à l'aide de la table générée.

do {
    if (index == 0)
        break;

    m = 0;
    f2 = &f[n * MAX_M];
    while (f2[m] <= index)
    {
        ++m;
    }

    index -= f2[m-1];
    ++m;
    *result++ = m;
    n -= m;
} while (n > 0);

do {
    *result++ = 1;
    --n;
} while (n > 0);

Ce code est également optimisé pour la conversion en langage assembleur. Il y a un petit "bug": si le partitionnement ne contient aucun1 nombre à la fin, la dernière boucle rencontre n = 0et génère un 1élément inutile . Cela ne fait pas de mal, cependant, car le code d'impression suit la somme du nombre et n'imprime pas ce nombre superflu.

Lorsqu'il est converti en assemblage en ligne, ce code ressemble à ceci:

__declspec(naked) void _fastcall random_partition_asm(int n, int result[])
{
    _asm {
        pushad;

        // ecx = n
        // edx = m
        // bh = k; ebx = k * MAX_M * sizeof(int)
        // ah = n1; eax = n1 * MAX_M * sizeof(int)
        // esp = f
        // ebp = c
        // esi = f2
        // edi = result

        mov edi, edx;
        sub esp, (MAX_M + 1) * MAX_M * 4; // allocate space for table
        xor eax, eax;
    row_loop:
        mov esi, esp;
        xor edx, edx;
        inc edx;
        mov dword ptr [esi + eax], edx;
        inc edx;

    col_loop:
        xor ebp, ebp;
        mov ebx, eax;

    sum_loop:
        add ebp, [esi + ebx];
        sub bh, dl;
        jae sum_loop;

        add esi, 4;
        mov [esi + eax], ebp;
        inc edx;
        cmp edx, ecx;
        jbe col_loop;

        inc ah;
        cmp ah, cl;
        jbe row_loop;

        // Done calculating the table

        // ch = n; ecx = n * MAX_M * sizeof(int)
        // eax = m
        // ebx = 
        // edx = index
        // esp = f
        // esi = f2
        // ebp = c
        // edi = result

        xor edx, edx;
        rdrand eax; // generate a random number
        div ebp; // generate a random index in the needed range
        xchg ch, cl; // multiply by 256

    n_loop:
        test edx, edx;
        jz out_trailing;
        xor eax, eax;
        lea esi, [esp + ecx];

    m_loop:
        cmp [esi + eax * 4], edx;
        ja m_loop_done;
        inc eax;
        jmp m_loop;
    m_loop_done:

        sub edx, [esi + eax * 4 - 4];
        inc eax;
        mov [edi], eax;
        add edi, 4;
        sub ch, al;
        ja n_loop;

    out_trailing:
        inc edx;
    out_trailing_loop:
        mov dword ptr [edi], edx;
        add edi, 4;
        dec ch;
        jg out_trailing_loop;

        dec edx;
        mov dh, (MAX_M + 1) * MAX_M * 4 / 256;
        add esp, edx;
        popad;
        ret;
    }
}

Quelques choses amusantes à noter:

• La génération d'un nombre aléatoire ne prend que 3 octets de code machine (rdrand instruction)
• Par une coïncidence, la taille de la table est de 64, donc la taille d'une ligne est de 256 octets. Je l'utilise pour conserver les index de ligne dans des registres "à octets élevés" ah, ce qui me donne une multiplication automatique par 256. Pour en profiter, j'ai sacrifié le support den = 65 . J'espère que je peux être excusé pour ce péché ...

• L'allocation d'espace sur la pile est effectuée en soustrayant 0x4100 du registre de pointeur de pile esp. Il s'agit d'une instruction de 6 octets! En rajoutant ce numéro, j'ai réussi à le faire en 5 octets:

      dec edx; // here edx = 1 from earlier calculations
      mov dh, (MAX_M + 1) * MAX_M * 4 / 256; // now edx = 0x4100
      add esp, edx; // this deallocates space on stack
  

• Lors du débogage de cette fonction dans MS Visual Studio, j'ai découvert qu'elle se bloque lorsqu'elle écrit des données dans l'espace qu'elle a alloué sur la pile! Après quelques recherches, j'ai découvert une sorte de protection contre le dépassement de pile: le système d'exploitation semble n'allouer qu'une plage très limitée d'adresses virtuelles pour la pile; si une fonction accède à une adresse trop éloignée, le système d'exploitation suppose qu'il s'agit d'un dépassement et tue le programme. Cependant, si une fonction possède de nombreuses variables locales, le système d'exploitation fait un peu de "magie" supplémentaire pour la faire fonctionner. Je dois donc appeler une fonction vide qui a un grand tableau alloué sur la pile. Après le retour de cette fonction, des pages de VM de pile supplémentaires sont allouées et peuvent être utilisées.

      void make_stack()
      {
          volatile int temp[65 * 64];
          temp[0] = 999; // have to "use" the array to prevent optimizing it out
      }