Перебор всех вариантов при помощи рекурсии

Question

У меня есть 4 набора карандашей (set из объектов). В каждом наборе по 3 карандаша (set из объектов).

{1} {2} {3}
{4} {5} {6}
{7} {8} {9}
{10}{11}{12}

Допустим, 2, 4, 6, 8, 10, 12 карандаши можно перекладывать в другие наборы. Исходя из условий, я нашел, какие карандаши и куда можно переложить. Сделал ArrayList с вложенным еще одним ArrayList. В каждом внутреннем следующее:

2 карандаш можно кинуть в набор 3
2 карандаш можно кинуть в набор 4

В другом внутреннем листе:

4 карандаш можно кинуть в набор 1

И так же в остальных.

Уже голова кипит. Не могу сообразить, как составить метод, который переберет все варианты перекладывания всех карандашей (каждый карандаш 1 раз).

Не прошу решения задачи. Достаточно подтолкнуть в нужном направлении или нужной ссылке.

Answer 1

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

1:  1
2:  1, 3, 4
3:  1
4:  2, 1
...

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

псевдокод:

function generate(Pencils, index, sets)
    if index >= Pencils.length():
         print(sets)
    else:
        for x in Pencils[index]:
            sets[x].включить(index)
            generate(Pencils, index + 1, sets) 
            sets[x].удалить(index)
         
 
generate(Pencils, 0, [[],[],[],[]])

БЛОГ НА HUSL

Перебор всех вариантов при помощи рекурсии

Ответы (1 шт):