Rekursion zur Ermittlung der Anzahl der verschiedenen Kombinationen von n Personen und k Gruppen

Question

Ich übe gerade Rekursion mit Java und bin auf ein Problem gestoßen. Ich versuche, eine Methode zu erstellen, die ich "Gruppen" nenne und die eine Anzahl von Personen und die Anzahl der Gruppen annimmt und die Anzahl der verschiedenen Kombinationen von Personen und Gruppen zurückgibt. Auch die Reihenfolge der Personen in den Gruppen spielt keine Rolle, ebenso wenig wie die Reihenfolge der Gruppen.

Der Code, den ich bis jetzt habe, lautet:

public long groups(int n, int k) {
    if(k==1) return 1;
    if(k==n) return 1;
    else return groups(n-1, k) + groups(n-1, k-1);
}

Es werden jedoch die falschen Werte zurückgegeben. Die ersten beiden Zeilen sind die Basisfälle, die besagen, dass es nur eine Möglichkeit gibt, die Personen aufzuteilen, wenn es nur eine Gruppe gibt, was Sinn macht. Der andere Fall ist, wenn es genau so viele Personen wie Gruppen gibt, in diesem Fall gibt es nur eine Möglichkeit, sie aufzuteilen, eine Person in jede Gruppe. Die letzte Aussage ist der Punkt, an dem ich glaube, dass ich Probleme habe. Ich würde denken, dass jedes Mal, wenn ein rekursiver Aufruf erfolgt, eine Person herausgenommen werden muss (n ist die Anzahl der Personen, also n-1) und diese Person entweder einer Gruppe (k) beitreten oder eine eigene Gruppe (k-1) bilden kann.

Ich habe gerade ein wenig Mühe herauszufinden, wie Rekursion funktioniert und könnte ein wenig Hilfe gebrauchen.

Das sind die Werte, die ich erwarte:

groups(2,1) = 1
groups(2,2) = 1
groups(3,2) = 3
groups(4,2) = 7
groups(4,3) = 6
groups(5,3) = 25

Answer 1

Bei der Umsetzung dieses Teils fehlt noch etwas

... und diese Person kann entweder einer Gruppe beitreten (k) ...

Ich denke, die Person kann "k"-Gruppen beitreten, also muss der Code lauten

    public long groups(int n, int k) {
        if(k==1) return 1;
        if(k==n) return 1;
        else return k * groups(n-1, k) + groups(n-1, k-1);
    }

(es fehlte die Multiplikation mit k )

Answer 2

Es gibt einen viel einfacheren (schnelleren) Weg, Kombinationen zu berechnen - das ist die Binomialkoeffizient . Ich kann zwar verstehen, dass Ihr Lehrer vielleicht möchte, dass Sie eine rekursive Funktion auf diese Weise schreiben, um sich mit der Rekursion vertraut zu machen, aber Sie können diese Formel zur Kontrolle verwenden.

In Ihrem Fall geben Sie hier die falschen erwarteten Werte an. Was Sie wollen, ist

groups(2,1) = 2
groups(2,2) = 1
groups(3,2) = 3
groups(4,2) = 6
groups(4,3) = 4
groups(5,3) = 10

und der Code, den Sie gepostet haben, ist korrekt, wenn die oben genannten Werte das sind, was er zurückgeben soll.

(Falls nicht, können Sie das Problem vielleicht besser erklären, indem Sie deutlicher darlegen, wie sich das Problem, das Sie lösen, von dem der Binomialkoeffizient .)