如何从Erlang的约束的三个子集中找到所有可能的对？ [英] How to find all possible pairs from three subsets of a set with constraints in Erlang?

问题描述

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

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

$ b $ A和B的元素可以在一对中的两个位置中的每个位置（即$ code> {a1，a2} 和 {b1，a1} 可以在一个子集S中，但不再有元素 {a1，_}和{_，a1} 在这个子集S中允许）; C中的元素可以在子集S中发生1-N次（即 {a，c}，{b，c }，{x，c} 可以发生在一个子集S中），但是我想为子集S中C的所有可能数量的元素S获取子集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}; 
  - 等
  

我倾向于认为，首先我需要找到所有可能的子集M只包含A的一个元素，B和1..N元素的一个元素为C （1）。之后，我应该以某种方式从中生成一组对（2）。但是我不确定这是否是正确的策略。

所以，更详细的问题是：

• 如果集合M的元素为整数，则在Erlang中创建集合和查找子集的最佳方式是什么？


• 是否有任何现成的工具在Erlang中找到一个集合的子集？


• 是否有任何现成的工具在Erlang中生成集合中所有可能的元素对？


• 如何解决Erlang中的上述问题？

解决方案

有一个 集 module * ，但我怀疑你最好先考虑一个算法，其实现在Erlang之后就是这样的问题。 （也许你会注意到它实际上是一个图形算法（例如，二分匹配的东西），以及你会很高兴与Erlang的有向图模块。）

长篇小说，当你提出一个算法时，Erlang很有可能被用来实现它。是的，有一定的支持套。但是，需要所有可能的子集的问题的解决方案往往是指数型的（即，给定 n 元素，有 2 ^ n 子集;对于每个元素，您都可以在子集中使用它），因此不好。

I have a set M which consists of three subsets A,B and C.

Problem: I would like to calculate all possible subsets S(1)...S(N) of M which contain all possible pairs between elements of A, B and C in such manner that:

1. elements of A and B can happen in a pair only once for each of two positions in a pair (that is {a1,a2} and {b1,a1} can be in one subset S, but no more elements {a1,_} and {_,a1} are allowed in this subset S);
2. elements of C can happen 1-N times in a subset S (that is {a,c}, {b,c}, {x,c} can happen in one subset S), but I would like to get subsets S for all possible numbers of elements of C in a subset S.

For example, if we have A = [a1,a2], B = [b1,b2], C = [c1,c2], then some of the resulting subsets S would be (remember, they should contain pairs of elements):

- {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.

I tend to think that first I need to find all possible subsets of M, which contain only one element of A, one element of B and 1..N elements of C (1). And after that I should somehow generate sets of pairs (2) from that. But I am not sure that this is the right strategy.

So, the more elaborated question would be:

• what is the best way to create sets and find subsets in Erlang if the elements of the set M a integers?
• are there any ready-made tools to find subsets of a set in Erlang?
• are there any ready-made tools to generate all possible pairs of elements of a set in Erlang?
• How can I solve the aforementioned problem in Erlang?

解决方案

There is a sets module*, but I suspect you're better off thinking up an algorithm first -- its implementation in Erlang is the problem (or not) that comes after this. (Maybe you notice its actually a graph algorithm (like, bipartite matching something something), and you'll get happy with Erlang's digraph module.)

Long story short, when you come up with an algorithm, Erlang can very probably be used to implement it. Yes, there is a certain support for sets. But solutions to a problem requiring "all possible subsets" tend to be exponential (i.e., given n elements, there are 2^n subsets; for every element you either have it in your subset or not) and thus bad.

(* there are some modules concerning sets)

这篇关于如何从Erlang的约束的三个子集中找到所有可能的对？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！