0

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

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

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

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

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

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

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

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

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

1 ответ 1

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, [[],[],[],[]])        
2
  • Да, вы абсолютно верно поняли условие. Не могли бы вы чуть более подробно объяснить, как это делается, или может быть название алгоритма или ссылку?
    – mxpnk
    Commented 17 авг. 2020 в 15:50
  • Добавил псевдокод.
    – MBo
    Commented 17 авг. 2020 в 16:07

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.