Все комбинации деления целого числа на несколько "групп"

Допустим, у меня есть 5 конфет, и я хочу найти все возможные комбинации, чтобы поделиться ими с моими 3 детьми.

Это будет примерно так:

5 for kid_A, 0 for kid_B, 0 for kid_3
0 for kid_A, 5 for kid_B, 0 for kid_3
....
4 for kid_A, 1 for kid_B, 0 for kid_3
4 for kid_A, 0 for kid_B, 1 for kid_3
....
and so on

Есть ли алгоритм для поиска этой комбинации?

До сих пор мне удалось вычислить первые 3 комбинации, где я отдаю все свои сладости одному из моих детей, а остальные получают 0; но я потерян на том, как разделить, как только я закончу с этой первой итерацией.

Источник

2 ответа

Решение

Есть три аспекта этой проблемы:

  • Сколько способов я могу дать одному ребенку до N конфет? (перестановок на ребенка)
  • Сколько способов я могу дать другому ребенку оставшиеся N сладостей для каждого из них? (рекурсия, может быть)
  • Когда я прекращаю делить сладости? (Окончание)

Сколько способов вы можете дать ребенку n сладостей, просто: вы получаете одну перестановку для каждого из 0 -> n, например, первому ребенку можно дать 0, 1, 2, 3, 4 или 5 сладостей.

Для второго ребенка вы можете повторить это после того, как вычтете количество сладостей первого ребенка. Итак, для 0 -> m, где m = 5 - n.

Для каждой из этих перестановок n и m третий потомок просто получает остаток: t = 5 - (n + m).

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

Источник

Код

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Example {
    public static void main(final String... args) {
        for (final List<Integer> option : divide(5, 3)) {
            System.out.printf("%d for kid_A, %d for kid_B, %d for kid_3%n", option.toArray());
        }
    }

    private static List<List<Integer>> divide(final int count, final int groups) {
        if (groups == 1) {
            final List<Integer> inner = new ArrayList<>(1);
            inner.add(count);
            final List<List<Integer>> outer = new ArrayList<>(1);
            outer.add(inner);
            return outer;
        }
        return IntStream.range(0, count + 1)
            .mapToObj(Integer::valueOf)
            .flatMap(p -> {
                return divide(count - p, groups - 1).stream()
                    .map(q -> {
                        q.add(p);
                        return q;
                    });
            }).collect(Collectors.toList());
    }
}

Как это устроено

Это начинается с базового предположения, что если у вас есть 1 ребенок, вы даете им все сладости.

Если у вас есть более одного ребенка, он определяет, сколько дать первого, а затем проверяет, сколько других может быть.

FlatMap получает все параметры и добавляет количество конфет, которые получает текущий ребенок.

Источник
Другие вопросы по тегам