10

列表集 (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

这些列表应该具有某种程度的相关性（想想：一个非常大的笛卡尔积的随机样本）。

注意：不同长度的列表不能共享同一组轴。

有没有一种算法可以做到这一点，而我只是没有用谷歌搜索正确的术语？如果没有，我们可以创建它吗？

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

PS。我认为这与graphs 的笛卡尔积不同，但可能存在一些重叠。

4

1 回答 1

1

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

于 2013-06-18T03:14:47.713 回答