(Set)从与列表组对应的图表中的集合(笛卡尔积)的列表

Question

列表集(A):

{[a,b,d,f],
 [a,c,d,f],
 [a,b,e,f],
 [a,c,e,f]}

其中a,b,c,d,e和f是项目(不一定是单词中的字符),可以作为有向非循环图(DAG,B,所有边缘从左边指向 - >到右边):

  b-->d
 / \ / \
a   X   f
 \ / \ /
  c-->e

或作为4组项目的笛卡尔积(C,称为轴):

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

Guava有一个从集合列表(C)生成一组列表(A)的好方法.

我正在尝试接受像B这样的图形的算法,并返回像C这样的轴列表(实际上是一个或多个,见下面的例子),它可以与上面的方法一起使用来生成一组像A这样的列表.

但是,不能保证列表集是笛卡尔积.例如:

{[a,b,d,f],
 -missing-
 [a,b,e,f],
 [a,c,e,f]}

对应DAG:

  b-->d
 / \   \
a   \   f
 \   \ /
  c-->e

不能表示为1笛卡尔积,但可以表示为2:

{a}*{b}*{d,e}*{f}    and    {a}*{c}*{e}*{f}

对应图表:

      d
     / \
a-->b   f            and     a-->c-->e-->f 
     \ /
      e

列表应该有一定程度的相关性(想想:一个非常大的笛卡尔积的随机样本).

注意:不同长度的列表不能共享同一组轴.

有没有一个算法可以做到这一点,我只是没有用Google搜索正确的术语？如果没有,我们可以创建吗？

算法的复杂性可能是一个问题,因为该集合可能具有10 ^ 2个列表,并且每个列表可以具有10 ^ 2个项目,即相当大的图形.我可以保证输入图表具有可能代表列表集的最小节点数...,并且连接的非分支节点(a-> c-> e-> f)可以汇总为单个对象(acef).

PS.我不认为这与图的笛卡尔积相同,但可能存在一些重叠.

Answer 1

如果我正确理解你的问题，那么你在（A）之后并且只想要（C）作为中间步骤。使用例如Dijkstra 算法生成穿过图表的最短路径- 这将生成列表集 (A)。如果此时您仍然需要笛卡尔积（即，如果您不只是生成笛卡尔积作为生成 (A) 的中间步骤），那么从 (A) 生成它比从 (B) 生成要容易得多。