программа для получения всех комбинаций приложения для шариков

Question

Я новичок в сочетании и алгоритмах, связанных с перестановкой. У кого-нибудь есть мысли о том, как программировать, чтобы решить эту классическую проблему? Есть 3 коробки (A, B, C) и 10 шаров (1,2,3, ..., 10), мы хотим поместить все шары в коробки. Результат должен быть {Box A: ball 1; Вставка B: шарик 2,3,4; Коробка C: мяч 5 6 7 8 9 10}, {коробка A: мяч 1 2; Вставка B: мяч 3 4 5; Ящик C: 7 8 9 10}, .... Я хочу получить все комбинации (а не количество разных комбинаций).
Кроме того, что, если есть ограничение, что каждый ящик содержит не более 4 шаров?

спасибо.

Answer 1

Вы можете поместить первый мяч в любую из трех коробок, так что у вас есть три варианта.
Существует три варианта для второго шара, три для третьего и т. Д.

Они независимы, поэтому у вас есть варианты 3^10, и каждый вариант имеет отображение 1: 1 с числом в диапазоне 0..3^10-1.

Рассмотрим число в тройной системе чисел, поэтому k-я тройная цифра номера сообщает нам, в какую ячейку (a = 0, b = 1, c = 2) принадлежит k-й шар.

Пример 3 шариков:
Number 14 = 112 трехкомпонентных, поэтому первый шар в С, второго и третьим в B

В случае ограниченного размера коробки простого подхода является рекурсивным поколением - аргументы рекурсии являются списком доступные шары и комбинацию тока (список ящиков с шарами и вакантными местами).