每个元素都有随机数的列表列表，如何将同一列中的相同元素对齐？

如果列表中有随机数的随机元素，您将如何创建一个矩阵，以便相同的元素出现在同一列中？每个元素都有随机数的列表列表，如何将同一列中的相同元素对齐？

每行至少有一个元素/列，但不同的行可以有不同数量的元素/列。每个元素每行最多显示一次。

元素不必保留其原始列，但应该以最小距离出现在生成矩阵的原始列中。

输入中元素y之前出现的每个元素x也必须出现在输出中的y之前。

例如：

a|c 
a|b|c 
c|e 
a|d|e 
b|d

应该事后看起来是这样的：

a| |c| | 
a|b|c| | 
| |c| |e 
a| | |d|e 
|b| |d|

这只是一个简单的例子，colums和每列元素的正数的任意正数应包括在内。

什么是高效算法？

来源

2014-02-07 user3280015

通过您的数据一次，构建一个图形，其中每个元素是一个节点，每个元素和直接出现在该元素后面的元素之间应该有一个有向边。

然后执行图的topological sort：

甲拓扑排序或一个有向图的拓扑排序是其顶点的线性排序，使得从顶点每向边UV u到顶点V，U在排序中的v之前。例如，图的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个之前执行的约束;在这个应用程序中，拓扑排序只是这些任务的有效顺序。

这将返回一个有序的元素列表，这些元素将对应于元素到列的排序。

来源

2014-02-07 08:31:48 Dukeling

谢谢，这是否最大限度地减少元素之间原始距离的偏差？ – user3280015

这主要是为了维护元素的顺序（如果在输入中出现'a | b'，'b'总是出现在输出中的'a'后面），假设这实际上是可能的，所以这可能不是什么你在追求。我可能错过了“最小距离”要求，尽管我也不完全确定你在说什么距离 - 虽然人们可以确实能够通过这种方式来实现这种距离的最小化。 – Dukeling

其实我明白你的意思是尽量减少到原始列的距离，但这可能与拓扑排序的结果相冲突，即如果在输入中出现'a | b'，则最小化距离可能涉及将'b ''在'a'之前，这与拓扑排序冲突，它总是在'b'之前放置'a'。所以不，它并没有真正努力将距离最小化（它可能*一般*给出了很好的距离，但肯定会有例外）。 – Dukeling

每个元素都有随机数的列表列表，如何将同一列中的相同元素对齐？

回答

相关问题