Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.220.154.41] |
|
Сообщ.
#1
,
|
|
|
Всем доброго,
не могу описать алгоритм математически, попробую описать словами и примером. Надо обойти все варианты определенным образом, на выходе надо иметь список всех вариантов. Язык реализации не имеет значения. Например есть 4(может быть любым) группы, в каждой группе может быть до 8-и элементов(может быть и больше, но не меньше кол-ва групп), 1-есть, 0-нет. В двух группах не может быть больше одного и того-же элемента как и в каждой группе всегда есть по крайней мере один элемент. В этом примере перебор вариантов будет следующим: 1. 00011111 00100000 01000000 10000000 2. 00001111 00110000 01000000 10000000 3. 00001111 00010000 01100000 10000000 4. 00001111 00010000 00100000 11000000 5. 00000111 00111000 01000000 10000000 6. 00000111 00011000 01100000 10000000 7. 00000111 00011000 00100000 11000000 8. 00000111 00001000 01110000 10000000 9. 00000111 00001000 00110000 11000000 10. 00000111 00001000 00010000 11100000 11. 00000011 00111100 01000000 10000000 ... |
Сообщ.
#2
,
|
|
|
Сложная постановка задачи. Предлагаю переформулировать - нужно собрать число n из k слагаемых. Наборы, отличающиеся порядком слагаемых, считаются разными. В твоём случае n = 8, k = 4, и твоим вариантам соответствуют такие наборы:
(5, 1, 1, 1), (4, 2, 1, 1), (4, 1, 2, 1) и т.д. По такому набору табличка получается естественным образом. Сами же наборы проще всего генерировать рекурсивно, задавая очередное число в нём в 1, 2 и т.д пока это имеет смысл, т.е. как-то так: (1, (список всех наборов с суммой n - 1 и длиной k - 1)), (2, (список всех наборов с суммой n - 2 и длиной k - 1)) ... |
Сообщ.
#3
,
|
|
|
Данную задачу можно сформулировать попроще: перебрать все варианты распределения М шаров в N корзин .
В примере ТСа М=4, N=4. |
Сообщ.
#4
,
|
|
|
Цитата OpenGL @ Сами же наборы проще всего генерировать рекурсивно Или даже не рекурсивно, а послойно. Пусть a[i, j] это все наборы с суммой i длины j. Тогда a[i, 1] = {i}, и циклом наподобие for j in 2..k: for i in 1..n: # заполняешь a[i, j] |
Сообщ.
#5
,
|
|
|
Пусть Б от 1 до 1<<К: Пусть Л от 1 до 1<<К: Пусть М от 1 до 1<<К: Пусть Н от 1 до 1<<К: Если (М & Н=0) && (Л & М=0) && (Л & Н=0) && (Б & Л=0) && (Б & М=0) && (Б & Н=0) то выводим(Б, Л, М, Н); |