Как найти все возможные пары из трех подмножеств множества с ограничениями в Erlang?

Question

У меня есть набор M, который состоит из трех подмножеств A, B и C.

Проблема: Я хотел бы рассчитать все возможные подмножества S (1) ... S (N) из M, которые содержат все возможные пары между элементами A, B и C, таким образом, чтобы:

1. элементы A и B могут встречаться в паре только один раз для каждой из двух позиций в паре (то есть {a1,a2} и {b1,a1} могут находиться в одном подмножестве S, но больше элементов {a1,_} and {_,a1} не допускается в это подмножество S);
2. элементы C могут встречаться 1-N раз в подмножестве S (то есть {a,c}, {b,c}, {x,c} может происходить в одном подмножестве S), но я хотел бы получить подмножества S для всех возможных количеств элементов C в подмножестве .

Например, если у нас есть A = [a1,a2], B = [b1,b2], C = [c1,c2], то некоторые из результирующих подмножеств S будут (помните, что они должны содержать пары элементов):

- {a1,b1}, {b1,a2}, {a2,b2}, {b2,c1};
- {a1,b1}, {b1,a2}, {a2,b2}, {b2,c1}, {c1,c2};
- {a1,c1}, {c1,a2}, {c1,b2}, {b1,c1};
- etc.

Я склонен думать, что сначала мне нужно найти все возможные подмножества M, которые содержат только один элемент A, один элемент B и 1..N элементов C (1). И после этого я должен как-то генерировать наборы пар (2) из этого. Но я не уверен, что это правильная стратегия.

Итак, более сложный вопрос будет:

• каков наилучший способ создания множеств и поиска подмножеств в Erlang, если элементы множества M a целые числа?
• есть ли готовые инструменты для поиска подмножеств набора в Erlang?
• Есть ли готовые инструменты для генерации всех возможных пар элементов набора в Erlang?
• Как я могу решить вышеупомянутую проблему в Erlang?

Answer 1

Существует модуль sets *, но я подозреваю, что вам лучше сначала придумать алгоритм - проблема его реализации в Erlang (или нет) что идет после этого. (Может быть, вы заметили, что на самом деле это алгоритм графов (например, двустороннее сопоставление чего-то с чем-то), и вы будете счастливы с модулем digraph Эрланга .)

Короче говоря, когда вы придумали алгоритм, Erlang вполне может быть использован для его реализации. Да, есть определенная поддержка наборов. Но решения проблемы, требующие «всех возможных подмножеств», имеют тенденцию быть экспоненциальными (т. Е. При заданных n элементах имеется 2^n подмножеств; для каждого элемента, у которых оно есть в вашем подмножестве или нет), и, таким образом, это плохо.

(* есть несколько модулей, касающихся наборов)