Объединяя список вещей, две вещи одновременно, пробуя каждую возможную комбинацию

Question

Я не уверен, как это объяснить очень хорошо, поэтому, пожалуйста, отредактируйте и спросите, если это будет необходимо. Я думаю, что это может иметь математическое решение. Я пытаюсь найти все способы, которыми элементы могут быть объединены вместе, чтобы предварительно вычислять их. Каждый из элементов имеет определенные веса и значения, и конечная цель состоит в том, чтобы минимизировать стоимость объединения заданного количества элементов. Когда предметы объединены, порядок имеет значение.

Скажем, есть три предмета. Есть левый и правый слот, в который можно помещать предметы. Имеет значение, если предметы объединены с одним предметом, находящимся в другом слоте. Я ищу помощь в поиске всех возможных способов объединения количества предметов. Таким образом, направление объединения двух предметов имеет значение, а также порядок объединения предметов.

Примеры:

a, b можно объединить как

1. a- > b
2. b-> a

a, b, c можно комбинировать как

1. a-> b -> c
2. c -> a-> b
3. a -> c -> b
4. b -> a -> c
5. b-> a -> c
6. c -> b-> a
7. b -> c -> a
8. a -> b -> c
9. c -> b -> a
10. a -> c -> b
11. c -> a -> b
12. b -> c -> a

Более короткие стрелки указывают, какая из них объединяется первой, а более длинная указывает на быть объединенным после того, как первые два пункта объединены. Я не делал вручную с 4-мя предметами и далее. «Направление» объединения двух предметов ie. b -> c -> a vs c -> a -> b - это то, что мне действительно трудно вставить в код.

Напоминает ли это кому-либо о математических отношениях или Алгоритм, который был использован ранее? Я использую java, я пробовал перестановки и комбинировал их в порядке перестановки, но он не учитывает "направление" объединения двух предметов.

Answer 1

По сути, вы перечисляете все способы объединения двух разных структур. Во-первых, вам нужно перечислить все возможные упорядочения n элементов, что является проблемой перестановок. Этот довольно хорошо изучен, и есть много хороших рекурсивных алгоритмов, которые вы можете использовать для него.

Затем вам нужно перечислить все способы группировки терминов перестановки вместе, что сводится к перечислению всех возможных способов Заключение в скобки выражения с n-1 слагаемыми (это количество примененных стрелок). Есть несколько способов сделать это, и хорошим рекурсивным является следующее:

• Пустая строка сбалансированных скобок - единственный способ создать строку из 0 сбалансированных скобок.
• В противном случае любая последовательность из n сбалансированных скобок принимает форму (P1) P2, где P1 и P2 - серии сбалансированных скобок. Чтобы сформировать все варианты, сосчитайте от k = 0, 1, 2, ..., n-1 и сформируйте все возможные P1, используя k сбалансированных скобок, и все возможные P2, используя nk-1 сбалансированных скобок.

Надеюсь, это поможет!