Алгоритм обхода

[fenix710]

Всем доброго,

не могу описать алгоритм математически, попробую описать словами и примером. Надо обойти все варианты определенным образом, на выходе надо иметь список всех вариантов. Язык реализации не имеет значения.
Например есть 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
...

Сообщение отредактировано: fenix710 - 23.04.19, 10:26

[OpenGL]

Сложная постановка задачи. Предлагаю переформулировать - нужно собрать число 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)) ...

[MIF]

Данную задачу можно сформулировать попроще: перебрать все варианты распределения М шаров в N корзин .
В примере ТСа М=4, N=4.

Сообщение отредактировано: MIF - 23.04.19, 11:50

[OpenGL]

Цитата OpenGL @ 23.04.19, 11:32

Сами же наборы проще всего генерировать рекурсивно

Или даже не рекурсивно, а послойно. Пусть a[i, j] это все наборы с суммой i длины j. Тогда a[i, 1] = {i}, и циклом наподобие

for j in 2..k:
   for i in 1..n:
      # заполняешь a[i, j]

[Pavia]

Пусть Б от 1 до 1<<К:
 Пусть Л от 1 до 1<<К:  
  Пусть М от 1 до 1<<К:  
   Пусть Н от 1 до 1<<К:
    Если (М & Н=0) &&
         (Л & М=0) && (Л & Н=0) &&    
         (Б & Л=0) && (Б & М=0) && (Б & Н=0)
           то выводим(Б, Л, М, Н);

Сообщение отредактировано: Pavia - 23.04.19, 12:17