Die Partitionsnummer einer positiven Ganzzahl ist definiert als die Anzahl der Möglichkeiten, wie sie als Summe positiver Ganzzahlen ausgedrückt werden kann. Mit anderen Worten, die Anzahl der Integer-Partitionen. Beispielsweise hat die Nummer 4die folgenden Partitonen:

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

Daher hat es 5Partitionen. Dies ist OEIS A000041 .

Aufgabe

Bei einer positiven Ganzzahl N bestimmen Sie deren Partitionsnummer.

• Es gelten alle Standardregeln.

• Die Eingabe und Ausgabe kann auf jede vernünftige Weise erfolgen.

• Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes.

Testfälle

Eingabe | Ausgabe

1 | 1
2 | 2
3 | 3
4 | 5
5 | 7
6 | 11
7 | 15
8 | 22
9 | 30
10 | 42

Pyth , 3 Bytes

l./

Probieren Sie es hier aus! oder Probieren Sie eine Testsuite aus.

Das Formatieren der Antwort dauerte viel länger als das Schreiben des Codes selbst: P.

Wie?

Pyth ist das richtige Werkzeug für den Job.

l. / Volles Programm mit impliziter Eingabe.

 ./ Integer-Partitionen. Gibt alle sortierten Listen positiver Ganzzahlen zurück, die zur Eingabe hinzugefügt werden.
l Länge.
      Das Ergebnis implizit ausgeben.

Mathematica, 11 Bytes

PartitionsP

Erläuterung

¯\_(ツ)_/¯

Python 2 , 85 83 Bytes

-2 Bytes dank @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

Probieren Sie es online!

Verwendung einer rekursiven Formel aus OEIS A000041 .

Emojicode 0.5, 204 201 Bytes

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

Probieren Sie es online!

-3 Bytes bei Verwendung von "kleiner oder gleich 1" anstelle von "kleiner als 2", da das Emoji "kleiner als" eine recht lange UTF-8-Codierung aufweist. Außerdem wurde teine Warnung eingefroren, um sie zum Schweigen zu bringen, ohne die Byteanzahl zu beeinflussen.

Erweitert die Klasse 🚂 (Ganzzahl) mit einer Methode mit dem Namen 🅰️. Sie können ein einfaches Programm schreiben, das eine Zahl aus der Eingabe entnimmt, die Zahl mit 🅰️ aufruft und das Ergebnis wie folgt ausgibt:

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

Dieser Teil könnte durch das Weglassen der Meldungen und der Fehlerbehandlung erheblich verbessert werden, ist jedoch nicht in der Partitur enthalten. Ich bevorzuge es, stattdessen mehr Funktionen von Emojicode zu zeigen und gleichzeitig die Lesbarkeit zu verbessern.

Ungolfed

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

Erläuterung

Hinweis: Viele Emojis machen in Emojicode 0.5 wenig Sinn. Immerhin ist es 0.x. 0.6 wird dies beheben.

Emojicode ist eine objektorientierte Programmiersprache mit Generika, Protokollen, Optionen und Abschlüssen. Dieses Programm verwendet jedoch keine Abschlüsse. Alle Generika und Protokolle können als implizit betrachtet werden, während die einzige Option im E / A-Stub angezeigt wird.

Das Programm arbeitet nur mit wenigen Typen: 🚂 ist der Integer-Typ, 🔡 ist der String-Typ und ⏩ ist der Range-Typ. Einige Boolesche Werte (👌) werden ebenfalls angezeigt, sie werden jedoch nur unter Bedingungen verwendet. Boolesche Werte können einen Wert von 👍 oder 👎 annehmen, der true bzw. false entspricht.

Derzeit gibt es in Emojicode keine Operatoren. Daher werden Additionen, Vergleiche und andere Operationen, die normalerweise Operatoren sind, als Funktionen implementiert, sodass die Ausdrücke die Präfixnotation verwenden . Betreiber sind auch in 0.6 geplant.

Lassen Sie uns zuerst das Testprogramm in Angriff nehmen.

🏁

Dies ist der 🏁-Block, der mit dem Hauptblock aus anderen Sprachen verglichen werden kann.

🍇 ... 🍉

Trauben und Wassermelonen deklarieren Codeblöcke in Emojicode.

🍦str🔷🔡😯🔤Please enter a number🔤

Dies deklariert einen "eingefrorenen" Namen strund setzt diesen Wert auf eine neue Zeichenfolge, die mit dem Initialisierer (Konstruktor) erstellt wurde. Er nimmt eine Eingabeaufforderung als Zeichenfolge und gibt dann eine Zeile vom Benutzer ein. Warum ein Frozen anstelle einer Variablen verwenden? Es ändert sich nicht, sodass eine Variable eine Warnung ausgibt.

🍊🍦num🚂str 10

Lassen Sie es uns aufschlüsseln. 🚂str 10ruft die 🚂 -Methode für das streingefrorene Objekt mit dem Argument 10 auf. Konventionell konvertieren Methoden mit dem Namen eines Typs das Objekt in diesen Typ. 10 ist die Basis für die Ganzzahlkonvertierung. Diese Methode gibt eine optionale, 🍬🚂. Optionals können einen Wert vom Basistyp oder Nichts enthalten, ⚡. Wenn die Zeichenfolge keine Zahl enthält, wird ⚡ zurückgegeben. Um den Wert zu verwenden, muss man das optionale mit 🍺 auspacken, was einen Laufzeitfehler auslöst, wenn der Wert ⚡ ist. Aus diesem Grund ist es empfehlenswert, vor dem Auspacken eines optionalen Geräts zu prüfen, ob keine Informationen vorliegen. Tatsächlich ist es so üblich, dass Emojicode eine Abkürzung dafür hat. Normalerweise 🍊ist ein "wenn".🍊🍦 variable expressionbedeutet: bewerte den Ausdruck. Wenn das optionale Element nichts enthält, wird die Bedingung mit false (falsch) bewertet. Andernfalls wird ein eingefrorener Name variablemit dem nicht umbrochenen Wert der Option erstellt, und die Bedingung wird mit to (wahr) ausgewertet. Daher wird im normalen Gebrauch der 🍇 ... 🍉Block eingegeben , der der Bedingung folgt.

😀🔡🅰️num 10

🅰️ ist die Methode, die der Hauptcode zu 🚂 hinzufügt, indem er 🐋 verwendet, um die Anzahl der Partitionen zu berechnen. Dies ruft 🅰️ auf der numeingefrorenen Bedingung auf, die wir in der Bedingung deklariert haben, und konvertiert das Ergebnis mit der Methode 🔡 zur Basis 10 in einen String. Dann druckt 😀 das Ergebnis.

🍓🍇 ... 🍉

🍓 bedeutet "else", daher wird dieser Block eingegeben, wenn der Benutzer eine Nummer nicht korrekt eingegeben hat.

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

Gibt das String-Literal aus.

Nun schauen wir uns das Hauptprogramm an. Ich werde die ungolfed Version erklären; Bei der Golf-Version wurde nur das Leerzeichen entfernt und die Variablen in Einzelbuchstaben umbenannt.

🐋🚂🍇 ... 🍉

Erweitern Sie die Klasse 🚂. Dies ist eine Funktion, die in Programmiersprachen nicht häufig vorkommt. Anstatt eine neue Klasse mit 🚂 als Oberklasse zu erstellen, wird, direkt geändert.

🐖🅰️➡🚂🍇 ... 🍉

Erstellt eine neue Methode mit dem Namen 🅰️, die ein 🚂 zurückgibt. Es gibt die Anzahl der Partitionen zurück, die mit der Formel berechnet wurdena(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k)

🍊⬅🐕1🍇
 🍎1
🍉

🐕 ähnelt thisoder stammt selfaus anderen Sprachen und bezieht sich auf das Objekt, für das die Methode aufgerufen wurde. Diese Implementierung ist rekursiv, daher ist dies die Abschlussbedingung: Wenn die Zahl, auf die die Methode aufgerufen wurde, kleiner oder gleich 1 ist, wird 1 zurückgegeben.

🍮sum 0

Erstellen Sie eine neue Variable sumund setzen Sie sie auf 0. Nimmt implizit den Typ 🚂 an.

🔂k⏩0🐕

🔂 iteriert über alles, was das Protokoll implementiert, während ⏩ ein Bereichsliteral ist, das gerade implementiert. Ein Bereich hat einen Startwert, einen Stoppwert und einen Schrittwert, der als 1 wenn start < stopoder -1 sonst angenommen wird. Sie können den Schrittwert auch angeben, indem Sie mit ⏭ das Bereichsliteral erstellen. Der Startwert ist inklusive, während der Stoppwert exklusiv ist. Dies ist also äquivalent zu for k in range(n)oder Sum_{k=0..n-1}in der Formel.

🍦nmk➖🐕k

Wir müssen Sigma (n - k) oder mit n - kanderen Worten die Summe der Teiler von berechnen , und das Argument wird einige Male benötigt, sodass es n - kin der Variablen gespeichert wird nmk, um einige Bytes zu sparen.

🍮sig nmk
🔂i⏩1 nmk

Dies setzt die sigVariable auf das Argument von Sigma und durchläuft alle Zahlen von 1 bis nmk - 1. Ich könnte die Variable auf 0 initialisieren und über 1..nmk iterieren, aber dies ist kürzer.

🍊😛🚮nmk i 0

🚮 berechnet den Rest oder Modul und 😛 prüft auf Gleichheit, so dass die Bedingung 👍 ist, wenn iein Teiler von ist nmk.

🍮➕sig i

Dies ist eine telefonische Aufgabe, ähnlich der += -= >>=Bedienerfamilie in einigen der minderwertigen, emojifreien Sprachen. Diese Zeile kann auch als geschrieben werden 🍮 sig ➕ sig i. Enthält daher nach Beendigung der inneren Schleife sigdie Summe der Teiler von n - kodersigma(n - k)

🍮➕sum✖sig🅰️k

Eine weitere Zuweisung per Anruf, dies addiert sigma(n - k) * A(k)sich also genau wie in der Formel zur Gesamtsumme.

🍎➗sum🐕

Schließlich wird die Summe durch n dividiert und der Quotient zurückgegeben. Diese Erklärung hat wahrscheinlich dreimal so lange gedauert wie das Schreiben des Codes selbst ...

Pari / GP , 8 Bytes

numbpart

Probieren Sie es online!

Oktave, 18 Bytes

partcnt(input(''))

Verwendet die eingebaute Funktion partcnt.

Wenn Sie eine anonyme Funktion mit @ nicht verwenden können, ist eine gewisse Hilfe hilfreich.

Retina , 34 Bytes

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

%O`1+
@`.+

Probieren Sie es online!

Erläuterung

.+
$*

Konvertieren Sie die Eingabe in Unary.

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

Dies berechnet alle 2 ^n-1 Partitionen der Liste der unären Ziffern. Wir tun dies durch wiederholtes ( +) Anpassen der ersten ( 1) Nicht-Wort-Grenze ( \Bdh einer Position zwischen zwei 1s) in jeder Zeile ( %) und Ersetzen durch ;alles danach ( $'), einen Zeilenvorschub ( ¶) und alles davor es ( $`) und, . Beispiel:

1;1,111

Wird

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

Wo vmarkiert das Ergebnis von $'und ^markiert das Ergebnis$` . Dies ist eine gebräuchliche Redewendung, um das Ergebnis von zwei verschiedenen Ersetzungen gleichzeitig zu erhalten (wir fügen im Grunde genommen sowohl die ;als auch die ein, Ersetzung als auch die fehlenden "Hälften" der Zeichenkette ein, um zwei vollständige Ersetzungen abzuschließen).

Wir werden ;als tatsächliche Partitionen und ,nur als Platzhalter behandeln, die eine spätere \BÜbereinstimmung dort verhindern. Also weiter ...

,

... wir entfernen diese Kommas. Das gibt uns alle Partitionen. Zum Beispiel für die Eingabe erhalten 4wir:

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

Die Reihenfolge ist uns allerdings egal:

%O`1+

Dies sortiert die Läufe von 1 s in jeder Zeile, so dass wir ungeordnete Partitionen erhalten.

@`.+

Schließlich zählen wir die eindeutigen ( @) Übereinstimmungen .+, dh wie viele verschiedene Linien / Partitionen wir erhalten haben. Ich habe diese @Option vor langer Zeit hinzugefügt , sie dann komplett vergessen und erst kürzlich wiederentdeckt. In diesem Fall wird ein Byte über die erste Deduplizierung der Zeilen mit gespeichert D`.

Python 2 , 54 53 Bytes

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

Probieren Sie es online!

Wie es funktioniert

Jede Partition von n kann als Liste x = [x ₁ ,,, x _m ] dargestellt werden, so dass x ₁ + ⋯ + x _m = n . Diese Darstellung wird eindeutig, wenn wir x ₁ ≤ ⋯ ≤ x _m benötigen .

Wir definieren eine Hilfsfunktion f (n, k) , die die Partitionen mit der Untergrenze k , dh die Listen x, so zählt, dass x ₁ + ⋯ + x _m = n und k ≤ x ₁ ≤ ⋯ ≤ x _m . Für die Eingabe n fragt die Abfrage nach der Ausgabe von f (n, 1) .

Für positive ganze Zahlen n und k , so daß k ≤ n , gibt es mindestens eine Trennwand mit Untergrenze k : Die Singleton - Liste [n] . Wenn n = k (insbesondere wenn n = 1 ), ist dies die einzige in Frage kommende Partition. Wenn andererseits k> n ist , gibt es überhaupt keine Lösungen.

Wenn k <n ist , können wir die verbleibenden Partitionen rekursiv zählen, indem wir sie wie folgt von links nach rechts erstellen. Für jeden j , so dass k ≤ j ≤ n / 2 , wir Partitionen bauen [x ₁ , ⋯, x _m ] = [j, y ₁ , ⋯, Y _m-1 ] . Wir haben x ₁ + ⋯ + x _m = n genau dann, wenn y _{1 ist} + ⋯ + y _m-1 = n - j . Außerdem ist x ₁ ≤ ⋯ ≤ x _m genau dann, wenn j ≤ y ₁ ≤ ⋯ ≤ y _{m-1 ist} .

Daher können die Partitionen x von n , die mit j beginnen , als f (n - j, j) berechnet werden , wobei die gültigen Partitionen y gezählt werden . Indem wir j ≤ n / 2 voraussetzen, stellen wir sicher, dass j ≤ n - j ist , also gibt es mindestens ein y . Wir können also alle Partitionen von n zählen, indem wir 1 (für [n] ) und f (n - j, j) für alle gültigen Werte von j addieren .

Der Code ist eine einfache Implementierung der mathematischen Funktion f . Außerdem wird k standardmäßig auf 1 gesetzt , sodass f(n)der Wert von f (n, 1) für die Eingabe von n berechnet wird .

J , 37-35 Bytes

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

Probieren Sie es online!

Erläuterung

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

JavaScript, 125 121 Bytes

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

Probieren Sie es online!

Warnung: Die zeitliche und räumliche Komplexität ist exponentiell. Funktioniert sehr langsam bei großen Stückzahlen.

Python 2 , 89 Bytes

-9 bytes von Mr.Xcoder -1 byte von 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)}

Probieren Sie es online!

Gelee , 13 Bytes

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

Probieren Sie es online!

Die Lösung von n = 1000 auf TIO dauert 5 Sekunden.

Java 8 (229 Byte)

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

Ungolfed:

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

Gelee , 3 Bytes

Das ŒṗAtom wurde kürzlich hinzugefügt und bedeutet "Ganzzahlige Partitionen".

ŒṗL

Probieren Sie es online!

ŒṗL - Volles Programm.

Œṗ - Ganzzahlige Partitionen.
  L - Länge.
      - Implizit ausgeben.

Pyt , 2 Bytes

←ᵱ

Erläuterung:

←          Get input
 ᵱ         Number of partitions

JavaScript ES7, 69 Bytes

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 Bytes

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

Zeitkomplexität O (n ^ n), also seien Sie vorsichtig (eine offensichtliche Verzögerung erscheint auf meinem Computer für F(6))