Рекурсия для получения количества различных комбинаций из n человек и k групп

Question

Я практикую рекурсию с использованием Java и столкнулся с проблемой. Я пытаюсь создать метод, который я называю «группы», который принимает количество людей и количество групп и возвращает количество различных комбинаций людей и групп. Кроме того, не имеет значения порядок людей в группах и порядок групп.

Код, который у меня есть на данный момент:

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

Однако он возвращает неправильные значения. Первые две строки - это базовые случаи, в которых говорится, что если есть 1 группа, то есть только один способ разделить людей, имеет смысл. Другой случай, когда существует столько же людей, сколько и групп, и в этом случае есть только один способ разделить их, по одному человеку в каждой группе. Последнее утверждение, где я думаю, что у меня проблемы, я думаю, что каждый раз, когда он делает рекурсивный вызов, нужно убрать одного человека (n - количество людей, поэтому n-1), и этот человек может эфир присоединиться к группе (k) или создать собственную группу (k-1).

У меня просто небольшая проблема с выяснением того, как работает рекурсия, и я мог бы воспользоваться небольшой помощью.

Вот значения, которые я ожидаю:

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

Чего-то не хватает в реализации этой части

... и этот человек может присоединиться к группе (k) ...

Я думаю,человек может присоединиться к группам 'k', поэтому код должен быть

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

(при умножении на k)

Answer 2

Существует гораздо более простой (более быстрый) способ вычисления комбинаций - это биномиальный коэффициент . Хотя я понимаю, что ваш учитель может захотеть, чтобы вы написали рекурсивную функцию таким образом, чтобы ознакомиться с рекурсией, вы можете использовать эту формулу в качестве проверки.

В вашем случае вы сообщаете неверные ожидаемые значения здесь. То, что вы хотите, это

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

и код, который вы опубликовали, верен, если приведенные выше значения должны быть возвращены.

(Если нет, возможно, вы можете лучше прояснить проблему, объяснив более четко, чем решаемая проблема отличается от биномиального коэффициента .)