Все возможные комбинации, объединяющие n списков, по крайней мере, по одному элементу каждого списка - PullRequest
Новая
       13

Все возможные комбинации, объединяющие n списков, по крайней мере, по одному элементу каждого списка

0 голосов
/ 25 июня 2018

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

input 1: {1,2}
input 2: {3,4}

expected result: 
{{1,3}, {1,4}, {2,3}, {2,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}

, расширяемыми до n списков ввода с n элементами

1 Ответ

0 голосов
/ 25 июня 2018

В основном вы можете считать двоичный код от 1 до 2^n - 1. Это для каждого набора. Затем вы выбираете один номер для каждого набора, давая (2^n - 1)^n комбинаций. Двоичное число говорит вам, какие элементы включать (1), а какие нет (0).

В приведенном выше примере (при условии, что {1, 2, 3, 4} действительно является частью ожидаемого результата), у вас будет 9 = 3^2 = (2^2 - 1)^2 комбинаций.

Поскольку ответ недостаточно объяснил, дальнейшее объяснение.

Позвольте мне придерживаться вашего примера. У нас есть

  • 1 = 01b -> {2} для set1, {4} для set2
  • 2 = 10b -> {1} для set1, {3} для set2
  • 3 = 11b -> {1, 2} для set1, {3, 4} для set2

Поскольку 0 = 00b опущено, гарантируется, что выбран хотя бы один элемент из каждого набора.

Теперь мы выбираем номер для каждого набора. Это дает

(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2) и (3, 3).

Если вы замените первое число соответствующим набором элементов из первого набора, а второе число - соответствующими элементами из второго набора, вы получите желаемый результат:

  • (1, 1) -> {2, 4}
  • (1, 2) -> {2, 3}
  • (1, 3) -> {2, 3, 4}
  • (2, 1) -> {1, 4}
  • (2, 2) -> {1, 3}
  • (2, 3) -> {1, 3, 4}
  • (3, 1) -> {1, 2, 4}
  • (3, 2) -> {1, 2, 3}
  • (3, 3) -> {1, 2, 3, 4}

По сути, вы просто считаете в системе счисления 2 ^ n - 1. Здесь есть цифры от 0 до 2 ^ n - 2. Таким образом, у нас есть 00, 01, 02, 10, 11, 12, 20, 21, 22, что в точности соответствует приведенному выше списку, только цифры на 1 меньше, чем число, которому они соответствуют.

...