P k (n) bedeutet die Anzahl der Partitionen n
in genau k
Teile. Gegeben n
und k
berechne P k (n).
Tipp: P k (n) = P k (n - k) + P k - 1 (n - 1) mit Anfangswerten p 0 (0) = 1 und p k (n) = 0, wenn n ≤ 0 oder k ≤ 0. [Wiki]
Beispiele
n k Ans
1 1 1
2 2 1
4 2 2
6 2 3
10 3 8
Regeln
- Es gelten die allgemeinen Code-Golf- Regeln.
code-golf
combinatorics
integer-partitions
Matthew Roh
quelle
quelle
8
statt7
.Antworten:
Pyth ,
976 Bytes-1 Byte danke an Erik den Outgolfer !
Probieren Sie es online aus!
Eingaben in das Programm werden umgekehrt (dh
k, n
).quelle
Swift ,
7673 BytesProbieren Sie es online aus!
Erläuterung
Wie funktioniert der Code strukturell?
Zunächst definieren wir unsere Funktion
P
mit zwei ganzzahligen Parameternn
undk
geben ihrInt
mit diesem Code einen Rückgabetyp :func P(_ n:Int,_ k:Int)->Int{...}
. Der coole Trick dabei ist, dass wir den Compiler anweisen, die Namen der Parameter zu ignorieren,_
gefolgt von einem Leerzeichen, das uns beim Aufrufen der Funktion zwei Bytes spart.return
wird offensichtlich verwendet, um das Ergebnis unseres unten beschriebenen verschachtelten Ternärs zurückzugeben.Ein weiterer Trick, den ich verwendet habe, war
n*k>0
, der uns ein paar Bytes mehr erspartn>0&&k>0
. Wenn die Bedingung wahr ist (beide Ganzzahlen sind immer noch höher als0
), rufen wir unsere Funktion rekursiv mitn
dekrementiert vonk
als unsere neue aufn
undk
bleiben gleich, und wir addieren das Ergebnis vonP()
mitn
undk
dekrementiert um 1. Wenn die Bedingung nicht wahr ist geben wir entweder1
oder0
abhängig davon zurück, obn
gleich istk
.Wie funktioniert der rekursive Algorithmus?
Wir wissen, dass das erste Element der Sequenz p 0 (0) ist , und überprüfen daher, ob beide ganzen Zahlen positiv sind (
n*k>0
). Wenn sie nicht höher als 0 sind, prüfen wir, ob sie gleich sind (n==l ?1:0
). Hier sind zwei Fälle:Es gibt genau 1 mögliche Partition, und daher geben wir 1 zurück, wenn die ganzen Zahlen gleich sind.
Es gibt keine Partitionen, wenn eine bereits 0 ist und die andere nicht.
Wenn jedoch beide positiv sind, rufen wir
P
zweimal rekursiv auf und addieren die Ergebnisse vonP(n-k,k)
undP(n-1,k-1)
. Und wir schleifen erneut, bisn
0 erreicht ist.* Hinweis: Die Leerzeichen können nicht entfernt werden.
quelle
Gelee , 6 Bytes
Probieren Sie es online aus!
quelle
Python 2 ,
61555150 Bytes-10 Bytes dank Erik dem Outgolfer. -1 Byte danke an Mr. Xcoder.
Ich werde sagen, ich habe den Hinweis aus OP kopiert und in Python übersetzt. : P.
Probieren Sie es online aus!
quelle
(n>0and k>0)
->n>0<k
+(n==k)
statt tun[0,1][n==k]
.or +
.n>0<k and
durchn*k>0and
Mathematica, 33 Bytes
hier ist nxk tabelle
quelle
Length
->Len`1
undIntegerPartitions
->Int`7
JavaScript (ES6),
424039 ByteIch denke das funktioniert.
Versuch es
quelle
MATL , 14 Bytes
Probieren Sie es online aus!
Erläuterung
Eingaben berücksichtigen
6
,2
.quelle
Haskell, 41 Bytes
Probieren Sie es online aus!
quelle
Haskell , 41 Bytes
Probieren Sie es online aus!
Eine alternative Wiederholung.
quelle
Pari / GP , 35 Bytes
Pari / GP verfügt über eine integrierte Funktion zum Iterieren über ganzzahlige Partitionen.
Probieren Sie es online aus!
quelle
Gelee , 13 Bytes
Ich
habe das Gefühl zuwissen, dass dieser grundlegende Ansatz nicht der beste sein wird!Probieren Sie es online aus!
quelle
05AB1E , 9 Bytes
Probieren Sie es online aus!
quelle
CJam , 18 Bytes
Probieren Sie es online aus!
Erwartet Eingaben in umgekehrter Reihenfolge, dh
k n
anstelle vonn k
.quelle
Scala , 73 Bytes
Nun, dies ist eine einfache, ungehinderte Verwendung der OP-Spitze.
k
undn
sind die Parameter meiner rekursiven Funktionf
. Siehe TIO-Link für den Kontext.Da dies rekursiv ist, sollte ich die Funktion def in die Byteanzahl aufnehmen?
Probieren Sie es online aus!
quelle
C (gcc) , 41 Bytes
Probieren Sie es online aus!
quelle
R (+ Pryr), 49 Bytes
Welches ergibt die rekursive Funktion
(k < 1 | n < 1)
prüft, ob einer der Anfangszustände erfüllt ist.!n + k
ergibt TRUE (1), wenn beiden
undk
0 sind, andernfalls FALSE (0).f(n - k, k) + f(n - 1, k - 1)
behandelt die Rekursion.quelle