Eingeschränkte Integer-Partitionen

8

P k (n) bedeutet die Anzahl der Partitionen nin genau kTeile. Gegeben nund kberechne 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

Matthew Roh
quelle
1
Sie sollten klar sagen, dass dies Code-Golf ist , obwohl es markiert ist.
Herr Xcoder
2
Kann jemand dafür einen Link zum OEIS erstellen (ich nehme an, es gibt einen mit der Anzahl der Partitionssequenzen, auf die wir im CnR OEIS-Beitrag gestoßen sind)
Stephen
3
Ich denke, der letzte Testfall sollte 8 sein
H.PWiz
2
Ich stimme mit H.PWiz , dass der letzten Testfall soll 8statt 7.
Erik der Outgolfer
2
A008284
Meilen

Antworten:

3

Swift , 76 73 Bytes

func P(_ n:Int,_ k:Int)->Int{return n*k>0 ?P(n-k,k)+P(n-1,k-1):n==k ?1:0}

Probieren Sie es online aus!


Erläuterung

Wie funktioniert der Code strukturell?

Zunächst definieren wir unsere Funktion Pmit zwei ganzzahligen Parametern nund kgeben ihr Intmit 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. returnwird 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 erspart n>0&&k>0. Wenn die Bedingung wahr ist (beide Ganzzahlen sind immer noch höher als 0), rufen wir unsere Funktion rekursiv mit ndekrementiert von kals unsere neue auf nund kbleiben gleich, und wir addieren das Ergebnis von P()mit nund kdekrementiert um 1. Wenn die Bedingung nicht wahr ist geben wir entweder 1oder 0abhängig davon zurück, ob ngleich ist k.

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 Pzweimal rekursiv auf und addieren die Ergebnisse von P(n-k,k)und P(n-1,k-1). Und wir schleifen erneut, bis n0 erreicht ist.


* Hinweis: Die Leerzeichen können nicht entfernt werden.

Mr. Xcoder
quelle
2

Python 2 , 61 55 51 50 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.

P=lambda n,k:n*k>0and P(n-k,k)+P(n-1,k-1)or+(n==k)

Probieren Sie es online aus!

total menschlich
quelle
1
Dies bricht auf dem letzten Testfall von 10, 3. Zu viel Rekursion
jkelm
1
(n>0and k>0)->n>0<k
Erik der Outgolfer
1
Auch können Sie +(n==k)statt tun [0,1][n==k].
Erik der Outgolfer
1
Sie brauchen keinen Platz in or +.
Erik der Outgolfer
1
50 Bytes , ersetzen n>0<k anddurchn*k>0and
Mr. Xcoder
2

Mathematica, 33 Bytes

Length@IntegerPartitions[#,{#2}]&

hier ist nxk tabelle

 \k->
 n1  0  0   0   0   0   0   0   0   0  
 |1  1  0   0   0   0   0   0   0   0  
 v1  1  1   0   0   0   0   0   0   0  
  1  2  1   1   0   0   0   0   0   0  
  1  2  2   1   1   0   0   0   0   0  
  1  3  3   2   1   1   0   0   0   0  
  1  3  4   3   2   1   1   0   0   0  
  1  4  5   5   3   2   1   1   0   0  
  1  4  7   6   5   3   2   1   1   0  
  1  5  8   9   7   5   3   2   1   1  
J42161217
quelle
1
Na sicher. Ich wusste, dass es ein eingebautes gab.
Matthew Roh
Ein vereinfachter Mathematica- Port würde hier meiner Meinung nach 13 Bytes sparen ( Length-> Len`1und IntegerPartitions->Int`7
Jonathan Allan
@ JonathanAllan Ich mache tatsächlich eine superkurze Version davon. Hoffentlich kann ich es bis Ende des Monats
beenden
2

JavaScript (ES6), 42 40 39 Byte

Ich denke das funktioniert.

f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y

Versuch es

k.value=(
f=(x,y)=>x*y>0?f(x-y,y)+f(--x,--y):x==y
)(i.value=10,j.value=3)
onchange=_=>k.value=f(+i.value,+j.value)
*{font-family:sans-serif}input{margin:0 5px 0 0;width:100px;}#j,#k{width:50px;}
<label for=i>n: </label><input id=i type=number><label for=j>k: </label><input id=j type=number><label for=k>P<sub>k</sub>(n): </label><input id=k readonly>

Zottelig
quelle
2

MATL , 14 Bytes

y:Z^!S!Xu!Xs=s

Probieren Sie es online aus!

Erläuterung

Eingaben berücksichtigen 6, 2.

y     % Implicitly take the two inputs. Duplicate from below
      % STACK: 6, 2, 6
:     % Range
      % STACK: 6, 2, [1 2 3 4 5 6]
Z^    % Cartesian power
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 1; 2 2; ...; 6 6]
!S!   % Sort each row
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 1 2; 2 2; ...; 6 6]
Xu    % Unique rows
      % STACK: 6, [1 1; 1 2; ... 1 5; 1 6; 2 2; ...; 6 6]
!Xs   % Sum of each row, as a row vector
      % STACK: 6, [2 3 ... 6 7 4 ... 12]
=     % Equals, element-wise
      % STACK: [0 0 ... 1  0 0 ... 0]
s     % Sum. Implicitly display
      % STACK: 3
Luis Mendo
quelle
Ehrlich gesagt bin ich überrascht, dass MATL keine "Integer-Partition" eingebaut hat oder so.
Erik der Outgolfer
@ Franchise Es sollte jetzt funktionieren. Danke, dass du es mir gesagt hast!
Luis Mendo
Kein Problem. Ich habe nur damit gespielt, um Ihre Methode zu verstehen (was in kleinen Fällen im Allgemeinen einfacher ist), als ich auf den Fehler stieß.
Sanchises
0

Gelee , 13 Bytes

Ich habe das Gefühl zu wissen, dass dieser grundlegende Ansatz nicht der beste sein wird!

RŒṖL€€Ṣ€QṀ€=S

Probieren Sie es online aus!

Jonathan Allan
quelle
Ja, ist es nicht (siehe meine Jelly-Antwort ganz unten).
Erik der Outgolfer
Oh nein Code Bowling
Matthew Roh
@EriktheOutgolfer Wenn es funktioniert, warum wird es gelöscht?
Jonathan Allan
@ Jonathan Refresh
Matthew Roh
@ JonathanAllan Es wurde gelöscht, bevor ein Testfall behoben wurde.
Erik der Outgolfer
0

Scala , 73 Bytes

Nun, dies ist eine einfache, ungehinderte Verwendung der OP-Spitze.

kund nsind die Parameter meiner rekursiven Funktion f. Siehe TIO-Link für den Kontext.

Da dies rekursiv ist, sollte ich die Funktion def in die Byteanzahl aufnehmen?

(k,n)match{case(0,0)=>1
case _ if k<1|n<1=>0
case _=>f(n-k,k)+f(n-1,k-1)}

Probieren Sie es online aus!

V. Courtois
quelle
0

R (+ Pryr), 49 Bytes

f=pryr::f(`if`(k<1|n<1,!n+k,f(n-k,k)+f(n-1,k-1)))

Welches ergibt die rekursive Funktion

function (k, n) 
if (k < 1 | n < 1) !n + k else f(n - k, k) + f(n - 1, k - 1)

(k < 1 | n < 1)prüft, ob einer der Anfangszustände erfüllt ist. !n + kergibt TRUE (1), wenn beide nund k0 sind, andernfalls FALSE (0). f(n - k, k) + f(n - 1, k - 1)behandelt die Rekursion.

JAD
quelle