2

我有一套S。它包含N子集(其中又包含一些不同长度的子子集):

1. [[a,b],[c,d],[*]]
2. [[c],[d],[e,f],[*]]
3. [[d,e],[f],[f,*]]
N. ...

我还有一个L包含在集合中的“独特”元素列表S

a, b, c, d, e, f, *

我需要从每个子集的每个子集之间找到所有可能的组合,以便每个结果组合都具有 list 中的一个元素L,但该元素的出现次数为任意数量[*](它是通配符元素)。

因此,使用上述集合的所需函数的结果S应该是(不是 100% 准确):

- [a,b],[c],[d,e],[f];
- [a,b],[c],[*],[d,e],[f];
- [a,b],[c],[d,e],[f],[*];
- [a,b],[c],[d,e],[f,*],[*];

所以,基本上我需要一个执行以下操作的算法:

  1. 从子集中取一个子集1
  2. 2从维护到目前为止获得的“唯一”元素列表的子集中添加一个子集(如果子集包含该*元素,则跳过对“唯一”列表的检查);
  3. 重复2直到N达到。

换句话说,我需要生成所有可能的“链”(它是对、 ifN == 2和三元组 if N==3),但是每个“链”应该只包含列表中的一个元素,L除了可以在每个生成的通配符元素*中出现多次链。

我知道如何做到这一点N == 2(这是一个简单的对生成),但我不知道如何增强算法以使用N.

也许第二种斯特林数在这里会有所帮助,但我不知道如何应用它们来获得所需的结果。

注意:这里使用的数据结构类型对我来说并不重要。

注意:这个问题是从我之前的类似问题中衍生出来的。

4

1 回答 1

0

这些是一些指针(不是完整的代码),可能会带您走向正确的方向:

  1. 我认为您在这里不需要一些高级数据结构(利用 erlang列表推导)。您还必须探索 erlang集合列表模块。由于您正在处理集合和子集列表,因此它们似乎是理想的选择。
  2. 以下是列表推导的问题如何为您轻松解决:[{X,Y} || X <- [[c],[d],[e,f]], Y <- [[a,b],[c,d]]].这里我只是生成一个 {X,Y} 2 元组列表,但对于您的用例,您必须在此处放置真正的逻辑(包括您的明星案例)
  3. 进一步注意,使用列表推导,您可以使用一个生成器的输出作为稍后生成器的输入,例如[{X,Y} || X1 <- [[c],[d],[e,f]], X <- X1, Y1 <- [[a,b],[c,d]], Y <- Y1].
  4. 此外,对于从事物列表中删除重复项L = ["a", "b", "a"].,您可以随时简单地执行sets:to_list(sets:from_list(L)).

使用上述工具,您可以轻松生成所有可能的链,并在生成这些链时强制执行您的逻辑。

于 2012-02-11T00:42:16.443 回答