perl - 了解元素的顺序

Question

我想找到一种有效的方法(最好是 Perl)通过比较单词族在该组的多个子集中的顺序来学习单词族的固定顺序。(它们是作业参数。大约有30个不同的参数。不同的作业需要不同的参数组合，并且每个作业中只有几个参数)

例如，给定:

first
second
third
sixth
seventh
tenth

first
third
fourth
fifth
sixth

third
fifth
seventh
eighth
ninth
tenth

它应该能够记住它看到的相对顺序关系，以计算出顺序是:

first
second
third
fourth
fifth
sixth
seventh
eighth
ninth
tenth

我生成了如下列表:

first.second.third.sixth.seventh.tenth
first.third.fourth.fifth.sixth
third.fifth.seventh.eighth.ninth.tenth

然后按字母顺序对它们进行唯一排序并进行视觉比较，但我有 30 多个参数的数百种不同组合，因此对它们进行排序并手动将它们组合在一起将是一项艰巨的工作。

我认为@daniel-tran已经回答了https://stackoverflow.com/a/48041943/224625中的“如何”并使用它和一些黑客技术，例如:

$order->{$prev}->{$this} = 1;
$order->{$this}->{$prev} = 0;

我已经成功地用 1 或 0 来填充每对连续参数的哈希值，以表明哪个先出现，例如:

$VAR1 = {
    'first' => {
        'second' => 1,
        'third' => 1,
    },
    'second' => {
        'first' => 0,
        'third' => 1,
    },
    'third' => {
        'first' => 0,
        'second' => 0,
        'fourth' => 1,
        'fifth'  => 1,
        'sixth'  => 1,
    },            
    'fourth' => {
        'third' => 0,
        'fifth' => 1,
    },
    ...

但是当我的排序函数被要求对从未被视为直接邻居的一对进行排序(因此没有定义关系)时，我试图弄清楚在排序函数中该怎么做，但我遇到了困难。

有简单的解决办法吗？我以正确的方式处理这件事吗？首先有更好的 WTDI 吗？

谢谢

约翰

Answer 1

您链接到的问题includes another answer使用图和拓扑排序。 Graph模块非常易于使用:

use warnings;
use strict;
use Graph;

my $graph = Graph->new(directed => 1);
my $prev;
while (<DATA>) {
    chomp;
    $graph->add_edge($prev, $_) if length && length $prev;
    $prev = $_;
}
print $_,"\n" for $graph->topological_sort;

__DATA__
first
second
third
sixth
seventh
tenth

first
third
fourth
fifth
sixth

third
fifth
seventh
eighth
ninth
tenth

输出:

first
second
third
fourth
fifth
sixth
seventh
eighth
ninth
tenth