Сложный алгоритм. Задание на комбинаторику

Рейтинг: -1Ответов: 1Опубликовано: 12.11.2014

Не могу придумать алгоритм. Исходная задача такая. Переменные:

  1. Количество позиций (в моем случае это будет число от 2-х до 6-ти).
  2. Сумма всех стеков (фишек).
  3. Шаг изменения стека (фишек).
  4. С учетом/без учета порядка.

После того как я задам переменные, программа должна будет составлять большую таблицу, в которой будут все ситуации распределения фишек. Вот пример:

6 человек; в сумме на всех 3000 фишек; шаг 10 фишек. Без учета порядка. Программа начинает с 10/10/10/10/10/2950 (пусть будет так, что размер стека не может быть меньше шага), затем идет, например, 20/10/10/10/10/2940, и далее начинает перебирать всевозможные сочетания размеров стека (НО обязательно дающие в сумме одну и ту же цифру, которую мы зададим в качестве суммы стеков). В общем, каждый стек будет кратным шагу, и при перемене стеков местами не должно быть совпадений.

Т.е. в этом случае, например, 10/20/30/40/50/2850 и 30/40/2850/50/10/20 будут одинаковыми ситуациями, и в нашу таблицу внесется лишь одна из них (думаю, не столь важно, какая именно). В случае если я нажму галочку "с учетом порядка", то в таком это уже будут разные ситуации и обе будут внесены в нашу таблицу. Стек уже будет привязываться к номеру позиции.
У меня тяжеловато с комбинаторикой, так что я вряд ли смогу определить примерное количество подобных сочетаний.

Код

c# алгоритм комбинаторика
Источник: Stack Overflow на русском

Ответы

▲ 2

В случае, когда порядок важен, число вариантов будет равно числу композиций числа (Количество позиций / Шаг изменения стека), состоящих из (Количество позиций) слагаемых. Как их перечислять, можно прочитать тут. Предупреждаю, что число композиций растет очень быстро. Оно равно числу сочетаний из (n-1) по (k-1). Для вашего примера это будет (299 choose 5) = 19256456934 ~ 10^10, что уже на грани возможностей обычных компьютеров. Можно грубо оценить: чтобы сохранить каждую комбинацию, нужно 5 * 9 бит, поэтому чтобы сохранить их все, нужно порядка 100 Гб. Ну и времени на вычисления понадобится порядка суток.

Для случая, когда порядок не важен, число вариантов будет равно числу разбиений фиксированной длины. Про алгоритм перечисления можно прочитать тут. Число разбиений будет меньше, но я подозреваю, что зависимость тоже экспоненциальная. Точной формулы вроде бы нет.