Über die Serie

Zunächst einmal können Sie dies wie jede andere Code-Golf-Herausforderung behandeln und beantworten, ohne sich Gedanken über die Serie zu machen. Es gibt jedoch eine Rangliste für alle Herausforderungen. Sie finden die Rangliste zusammen mit einigen weiteren Informationen über die Serie im ersten Beitrag .

Obwohl ich eine Menge Ideen für die Serie habe, sind die zukünftigen Herausforderungen noch nicht in Stein gemeißelt. Wenn Sie Vorschläge haben, teilen Sie mir dies bitte auf dem entsprechenden Sandbox-Post mit .

Loch 3: Ganzzahlige Partitionen

Zeit, den Schwierigkeitsgrad etwas zu erhöhen.

Eine Partition einer positiven Ganzzahl nist definiert als ein Multiset von positiven Ganzzahlen, die sich summieren n. Als Beispiel n = 5existieren die folgenden Partitionen:

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

Beachten Sie, dass diese Multimengen sind, so gibt es keine Ordnung zu ihnen {3,1,1}, {1,3,1}und {1,1,3}sind alle identisch betrachtet.

Ihre Aufgabe ist es n, eine zufällige Partition von zu generieren n. Hier sind die detaillierten Regeln:

• Die Verteilung der produzierten Partitionen muss gleichmäßig sein . Das heißt, im obigen Beispiel sollte jede Partition mit einer Wahrscheinlichkeit von 1/7 zurückgegeben werden.

  Aufgrund der technischen Einschränkungen von PRNGs ist eine perfekte Gleichmäßigkeit natürlich nicht möglich. Um die Gleichmäßigkeit Ihrer Einreichung zu beurteilen, werden die folgenden Vorgänge als perfekt gleichmäßige Verteilungen ergebend angesehen:

  • Beziehen einer Nummer von einem PRNG (über einen beliebigen Bereich), von dem dokumentiert wird, dass sie (ungefähr) einheitlich ist.
  • Abbildung einer gleichmäßigen Verteilung über eine größere Menge von Zahlen auf eine kleinere Menge durch Modulo oder Multiplikation (oder eine andere Operation, die Werte gleichmäßig verteilt). Die größere Menge muss mindestens das 1024-fache der möglichen Werte der kleineren Menge enthalten.

• Da es sich bei den Partitionen um Multisets handelt, können Sie sie in beliebiger Reihenfolge zurückgeben, und diese Reihenfolge muss nicht konsistent sein. Für die zufällige Verteilung wird die Reihenfolge jedoch ignoriert. Das heißt, in dem obigen Beispiel {3,1,1}, {1,3,1}und {1,1,3} zusammen müssen eine Wahrscheinlichkeit von 1/7 haben zurückgegeben werden.

• Ihr Algorithmus muss eine deterministische Laufzeit haben. Insbesondere können Sie keine zufälligen Multisets generieren und ablehnen, wenn sie nicht zusammengerechnet werden n.
• Die Zeitkomplexität Ihres Algorithmus muss polynomiell sein n. Insbesondere können Sie nicht einfach alle Partitionen generieren und eine zufällige auswählen (da die Anzahl der Partitionen mit exponentiell wächst n). Sie können davon ausgehen, dass der von Ihnen verwendete PRNG gleichmäßig verteilte Werte in O (1) pro Wert zurückgeben kann.
• Sie dürfen keine eingebaute Funktion verwenden, die diese Aufgabe löst.

Sie können ein vollständiges Programm oder eine Funktion schreiben und Eingaben über STDIN oder die nächstgelegene Alternative, ein Befehlszeilenargument oder ein Funktionsargument vornehmen und Ausgaben über den Rückgabewert oder durch Drucken an STDOUT (oder die nächstgelegene Alternative) erzeugen.

Sie können davon ausgehen, dass n ≤ 65(so dass die Anzahl der Partitionen weniger als 2 ^{21 ist} ). Die Ausgabe kann in einem beliebigen praktischen, eindeutigen Listen- oder Zeichenfolgenformat erfolgen.

Wenn Sie eine Funktion einreichen, sollten Sie auch ein kleines Testprogramm bereitstellen, das die Funktion mehrmals aufruft und die Ergebnisse druckt. Es ist in Ordnung, wenn die Parameter im Code angepasst werden müssen. Dies ist nur so, dass die Leute überprüfen können, ob die Lösung zumindest annähernd einheitlich ist.

Dies ist Codegolf, daher gewinnt die kürzeste Übermittlung (in Bytes). Und natürlich wird die kürzeste Einreichung pro Benutzer auch in die Gesamt-Bestenliste der Serie aufgenommen.

Bestenliste

Der erste Beitrag der Serie generiert eine Rangliste.

Um sicherzustellen, dass Ihre Antworten angezeigt werden, beginnen Sie jede Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

(Die Sprache wird derzeit nicht angezeigt, das Snippet erfordert sie jedoch und analysiert sie. Ich füge möglicherweise in Zukunft eine Bestenliste nach Sprachen hinzu.)

Python 2, 179 Bytes

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

Ich habe die Formel (39) aus diesem Knuth-Extrakt verwendet , die die Anzahl der Partitionen angibt n, die genau mTeile haben. Dies entspricht der Anzahl der Partitionen n, die mals maximales Element angegeben sind. Dies ist die Interpretation, die ich verwende. Die Elemente der Partition werden vom größten bis zum kleinsten erzeugt. In jeder Phase wird die Formel mit dem aktuellen Rest nund dem maximal zulässigen Element wiederverwendet .

Dyalog APL, 67 59 51 Bytes

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

pist ein Vektor von Vektoren, in dem p[n][k]die Anzahl von Partitionen nin kSummanden oder äquivalent die Anzahl von Partitionen mit dem größten Summanden ist k. Wir bauen, pindem wir mit dem leeren Vektor beginnen ⍬, lesen n(die ⎕Leseeingabe) und wiederholt Folgendes anwenden:

{⍵,⊂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

Nach napplications ( ⍣⎕) haben wir gebaut p.

fwählt eine zufällige Partition. n f kist eine zufällige Partition von höchstens k Summanden. f nist 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

Einige Verbesserungen:

• Inline pauf Kosten einer etwas schlechteren (aber immer noch guten) Leistung

• in der Berechnung pneu anordnen ⌽und 1,einen Charakter speichern

• biegen Sie {1++/(?+/⍵)>+\⍵}in einen Zug mit 1+vor:1+(+/(?+/)>+\)

• Machen Sie feine anonyme Funktion und liefern Sie ⎕(ausgewertete Eingabe) als Argument, um ein vollständiges Programm zu erhalten

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

Test mit n = 5

Test mit n = 65

Und der folgende Link wird n = 5 tausend Mal ausgeführt und sammelt Statistiken über die Häufigkeit jeder Partition: ⎕rl←0 ⋄ {⍺,⍴⍵}⌸ {⍵=0:⍬⋄a,a∇⍵-a←1+(+/(?+/)>+\)⍺↑⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬}⍨ ¨10000⍴5

Weitere Verbesserungen mit Hilfe von Roger Hui :

• ersetzen {⍵=0:A⋄B}mit {×⍵:B⋄A}. Signum ( ×⍵) gibt true für ⍵>0und false für zurück ⍵=0.

• Ersetzen (+/(?+/)>+\)durch +/b<?⊃⌽b←+\, speichert ein Zeichen

• Verwenden Sie zum Berechnen eine Matrix anstelle eines Vektors aus Vektoren p: Ersetzen ⍵⊃{⍵,⊂⌽1,+/¨⍵↑¨⍨⌽⍳⍴⍵}⍣⍵⊢⍬durch ⊃↓(0,⍨⊢⍪⍨1 1⍉+\)⍣⍵⍪1.

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

Test n = 5 ; Test n = 65 ; freq stats

GolfScript, 90 Bytes

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

Online-Demo

Dies ist eine Anpassung meines (einfacheren) Partitionszählcodes, der anstelle einer bloßen Verfolgung einer Zählung sowohl eine Zählung als auch ein einheitlich ausgewähltes der gezählten Elemente verfolgt.

Side-by-Side-Vergleich der beiden:

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

Unterschiede:

• Der Anfang ~ist, weil dies eher ein Programm als ein Ausschnitt ist.
• Das [1.]Ersetzen 1entspricht der Änderung des Verfolgten.
• Das zusätzliche {(\{)}%+}%erhöht jedes Element in dieser Partition und das {1+}%fügt 1der Partition hinzu.
• 0wird [0](golfen 1,) als Teil der Änderung dessen, was verfolgt wird, aber weil es ein Array bleiben muss, wenn es einem anderen vorangestellt wird, braucht es das Extra [ ].
• Die einfache Summe {+}*wird zu einer gewichteten Auswahl aus den Partitionen, kombiniert mit einer Summierung ihrer Anzahl.
• Das (;`entfernt die Zählung von dem Ausgang und legt die Partition in ein schönes Format.

Test Framework

;7000,{;
  '5'

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

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

Optimieren Sie die ersten 7000, wenn Sie eine andere Anzahl von Versuchen ausführen möchten. Beachten Sie, dass dies für eine Online-Demo viel zu langsam ist.

Java, 285 267 Bytes

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;}

Dies ist die gleiche Methode wie die Antwort von TheBestOne, verwendet jedoch ein einfaches Array anstelle einer Karte. Anstatt die zufällige Partition als "a" zurückzugeben List, werden sie auch auf der Konsole gedruckt.

Unten ist ein Testprogramm, das es 100000-mal ausführt. Für das Beispiel n=5lagen alle Sätze bei meinem letzten Lauf innerhalb von 0,64% eines perfekten 1/7.

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 Bytes

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

Sie können es mit diesem Skript testen:

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

Erläuterung

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 Bytes

Verwendet /programming//a/2163753/4230423, mit der Ausnahme, dass a) kein Cache vorhanden ist, da Pyth automatisch ein Memo erstellt, b) jeder druckt, anstatt an die Liste anzuhängen, und c) in Pyth übersetzt wird.

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

Ich werde eine Erklärung dazu veröffentlichen, wenn ich Zeit habe, aber hier ist der entsprechende Python-Code:

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: Ich bin endlich dazu gekommen, die Erklärung zu machen:

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

Oktave, 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

Ungolfed:

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

Konstruieren Sie eine quadratische Matrix, in der jede Zelle (m, n) die Anzahl der Partitionen widerspiegelt, mderen größte Anzahl nnach dem so freundlich zitierten Knuth-Extrakt @feersum ist. Zum Beispiel 5,2gibt uns 2, weil es zwei gültige Partitionen 2,2,1und gibt 2,1,1,1. 6,3gibt uns 3 für 3,1,1,1, 3,2,1und 3,3.

Wir können nun deterministisch die p-te Partition finden. Hier erzeugen wir peine Zufallszahl, aber Sie können das Skript leicht ändern, so pist ein Parameter:

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

Wir können nun deterministisch zeigen, dass jedes Ergebnis ausschließlich von p abhängt:

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

Wenn wir also zum Original zurückkehren, in dem p zufällig generiert wird, können wir sicher sein, dass jedes Ergebnis gleich wahrscheinlich ist.

R, 198 Bytes

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}

Ungolfed:

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)
}

Es folgt der gleichen Struktur wie @ dcsohls großartige Lösung in Octave und basiert daher auch auf dem von @feersum veröffentlichten Knuth-Extrakt .

Ich bearbeite das später, wenn ich eine kreativere Lösung in R finden kann. In der Zwischenzeit ist jede Eingabe natürlich willkommen.

Java, 392 Bytes

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;}

Mit anrufen a(n). Gibt a Listvon Integers zurück

Eingerückt:

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;
}

Adaptiert von /programming//a/2163753/4230423 und golfen

So funktioniert es: Wir können berechnen, wie viele Partitionen einer ganzen Zahl n in der O ( n ² ) -Zeit vorhanden sind . Als Nebeneffekt erzeugt dies eine Tabelle der Größe O ( n ² ), die wir dann verwenden können, um die k- te Partition von n für eine beliebige ganze Zahl k in der O ( n ) -Zeit zu erzeugen .

Also sei total = die Anzahl der Partitionen. Wählen Sie eine Zufallszahl k von 0 bis total - 1. Generieren Sie die k- te Partition.

Wie üblich , Vorschläge sind willkommen :)

Python 2, 173 Bytes

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]

Erstellt rekursiv ein Wörterbuch dmit Schlüsseln, kdie ein Paar darstellen, (n,m)indem k=67*n+m(unter Verwendung der Garantie n<=65). Der Eintrag ist das Tupel der Anzahl der Partitionen nin mTeile und eine zufällige solche Partition. Die Zählungen werden nach der rekursiven Formel berechnet (danke an feersum für den Hinweis)

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

und die zufällige Partition wird aktualisiert, indem einer der beiden Zweige mit einer Wahrscheinlichkeit ausgewählt wird, die proportional zu seiner Anzahl ist. Die Aktualisierung erfolgt durch Hinzufügen von a 1für den ersten Zweig und Inkrementieren jedes Elements für den zweiten Zweig.

Ich hatte große Probleme, Werte von mund nNull zu ermitteln. Zuerst habe ich ein Wörterbuch verwendet, das standardmäßig 0 und eine leere Liste enthält. Hier verwende ich eine Liste und fülle sie stattdessen mit diesem Standardeintrag auf. Negative Indizes bewirken, dass die Liste von ihrem Ende gelesen wird, was bedeutet, dass ein Standardeintrag nicht mehr in der Nähe des Endes ist, als jemals erreicht, und dass Umgehungen nur einen Bereich berühren, in dem m>n.

80386 Maschinencode, 105 Bytes

Hexdump des Codes:

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

Als C - Funktion: void random_partition(int n, int result[]);. Das Ergebnis wird als Liste von Zahlen im angegebenen Puffer zurückgegeben. es markiert in keiner Weise das Ende der Liste, aber der Benutzer kann das Ende durch Akkumulieren der Zahlen erkennen - die Liste endet, wenn die Summe gleich ist n.

Wie benutzt man (in 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');
}

Beispielausgabe (mit n = 64):

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

Dies erfordert viele Erklärungen ...

Natürlich habe ich den Algorithmus verwendet, den auch alle anderen verwendet haben. Es gab keine andere Wahl als die Komplexität. Deshalb muss ich den Algorithmus nicht zu viel erklären. Sowieso:

Ich bezeichne durch f(n, m)die Anzahl der Partitionen von nElementen mit Teilen nicht größer als m. Ich speichere sie in einem 2-D-Array (in C als deklariert f[65][64]), wobei der erste Index nund der zweite Index ist m-1. Ich entschied, dass das Unterstützen n=65zu viel Mühe war, also gab ich es auf ...

Hier ist C-Code, der diese Tabelle berechnet:

#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;
    }
}

Dieser Code hat einen etwas verschleierten Stil, sodass er leicht in die Assemblersprache konvertiert werden kann. Es berechnet die Elemente bis f(n, n), dh die Anzahl der Partitionen von nElementen. Wenn dieser Code fertig ist, centhält die temporäre Variable die erforderliche Nummer, mit der eine zufällige Partitionierung ausgewählt werden kann:

int index = rand() % c;

Diese indexwird später anhand der generierten Tabelle in das gewünschte Format (Nummernliste) konvertiert.

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);

Dieser Code ist auch für die Konvertierung in Assemblersprache optimiert. Es gibt einen kleinen "Bug": wenn die Partitionierung keine enthält1 am Ende Nummer , trifft die letzte Schleife auf n = 0ein nicht benötigtes 1Element und gibt es aus . Es tut jedoch nicht weh, weil der Druckcode die Summe der Zahlen verfolgt und diese fremde Zahl nicht druckt.

Bei der Konvertierung in eine Inline-Assembly sieht dieser Code folgendermaßen aus:

__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;
    }
}

Einige lustige Dinge zu beachten:

• Das Generieren einer Zufallszahl benötigt nur 3 Byte Maschinencode (rdrand Anweisung)
• Zufällig beträgt die Größe der Tabelle 64, sodass die Größe einer Zeile 256 Byte beträgt. Ich verwende dies, um Zeilenindizes in "High-Byte" -Registern zu halten ah, was mir eine automatische Multiplikation mit 256 ermöglicht. Um dies zu nutzen, habe ich die Unterstützung für geopfertn = 65 . Ich hoffe, ich kann für diese Sünde entschuldigt werden ...

• Das Zuweisen von Speicherplatz auf dem Stapel wird ausgeführt, indem 0x4100 vom Stapelzeigerregister subtrahiert wird esp. Dies ist eine 6-Byte-Anweisung! Als ich diese Zahl wieder hinzufügte, schaffte ich es in 5 Bytes:

      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
  

• Beim Debuggen dieser Funktion in MS Visual Studio habe ich festgestellt, dass sie abstürzt, wenn Daten in den Speicher geschrieben werden, den sie auf dem Stapel zugewiesen hat! Nach einigem Stöbern entdeckte ich eine Art Stapelüberlaufschutz: Das Betriebssystem weist dem Stapel anscheinend nur einen sehr begrenzten Bereich virtueller Adressen zu. Wenn eine Funktion auf eine zu weit entfernte Adresse zugreift, geht das Betriebssystem von einem Überlauf aus und beendet das Programm. Wenn eine Funktion jedoch viele lokale Variablen enthält, führt das Betriebssystem eine zusätzliche "Magie" aus, damit sie funktioniert. Ich muss also eine leere Funktion aufrufen, die ein großes Array auf dem Stack hat. Nachdem diese Funktion zurückgegeben wurde, werden zusätzliche Stapel-VM-Seiten zugewiesen und können verwendet werden.

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