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 回答