如何从 Erlang 中具有约束的集合的三个子集中找到所有可能的对？

Question

我有一个集合 M，它由三个子集 A、B 和 C 组成。

问题： 我想计算 M 的所有可能的子集 S(1)...S(N)，其中包含所有可能的子集A、B 和 C 的元素之间的对的方式如下：

1. 对于一对中的两个位置中的每一个，A 和 B 的元素只能在一对中出现一次（即 {a1,a2} 且{b1,a1} 可以是在一个子集 S 中，但该子集 S 中不允许有更多元素 {a1,_} 和 {_,a1})；
2. C 的元素可以在子集 S 中出现 1-N 次（即 {a,c}, {b,c}, {x,c} 可以在一个子集 S 中出现），但是 I想要获得子集 S 中 C 的所有可能元素数量的子集 S。

例如，如果我们有 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) 集。但我不确定这是否是正确的策略。

因此，更详细的问题是：

• 如果集合 M 的元素是整数，那么在 Erlang 中创建集合并查找子集的最佳方法是什么？
• Erlang 中有没有现成的工具可以查找集合的子集？
• Erlang 中是否有任何现成的工具可以生成集合中所有可能的元素对？
• 在Erlang中如何解决上述问题？

Answer 1

有一个 sets 模块*，但我怀疑你最好先想出一个算法——它在 Erlang 中的实现是接下来出现的问题（或不是问题）。 （也许你注意到它实际上是一个图算法（比如，二分匹配某物），并且Erlang 的 digraph 模块会让你感到高兴。 ）

长话短说，当你想出一个算法时，Erlang 很可能可以用来实现它。是的，对集合有一定的支持。但是，需要“所有可能的子集”的问题的解决方案往往是指数级的（即，给定 n 个元素，有 2^n 子集；对于每个元素，您要么拥有它无论是否在您的子集中），因此很糟糕。

（*有一些关于集合的模块）