如何用Perl从一组不等式比较中创建有序列表

Question

我正在用Perl进行历史股市分析。一个方面是分析研究公司过去股票评级的准确性。最基本的评级标准是买入、持有、卖出。然而，其中许多公司使用不同的术语，有些公司的评分超过了3分。

我有一份由数百家不同公司（来自雅虎金融）发布的数千次升级/降级的列表，看起来像这样：

Action      From      To
==================================================
Upgrade     Add           Buy
Downgrade   Add           Hold
Upgrade     Hold          Add
Downgrade   Buy           Outperform
Upgrade     Hold          Outperform
Downgrade   Hold          Reduce
Upgrade     Add           Outperform

所以基本上，这是一个比较列表，比如a>B、 D<C、 B>C、 D<

对于每一家研究公司，我需要的是一个有序的列表，它看起来像这样：

A>B>C>D>E

我对这个问题想了很多，但都想不出解决办法。如果每次升级/降级只跳一个增量，我想我可以做到，但我无法理解如何插入类似C<A、 其中它跳过两个增量。

有人有什么想法吗？

更新：

谢谢@ikegami。我用原始数据进行了测试，你是正确的。

我还通过Graph:：Easy运行了一些数据，它可以渲染图形。

代码：

use Graph::Easy;
my $graph = Graph::Easy->new( );
# Note that these are all in 'Upgrade' direction
$graph->add_edge ('Hold', 'Add');
$graph->add_edge ('Hold', 'Buy');
$graph->add_edge ('Hold', 'Outperform');
$graph->add_edge ('Buy', 'Outperform');
$graph->add_edge ('Reduce', 'Hold');
$graph->add_edge ('Add', 'Buy');
print $graph->as_ascii( );

输出：

               +------------------------+
               |                        v
+--------+     +------+     +-----+     +-----+     +------------+
| Reduce | --> | Hold | --> | Add | --> | Buy | --> | Outperform |
+--------+     +------+     +-----+     +-----+     +------------+
               |                                    ^
               +------------------------------------+

这是一张有明显歧义的图。也许我可以以某种方式使用这两个模块（或Graph的某些功能）来测试歧义。

+------------------------------+
|                              v
+--------+     +---------+     +-----+
| Reduce | --> | Neutral | --> | Buy |
+--------+     +---------+     +-----+
                 ^               ^
                 |               |
                 |               |
               +---------+       |
               |  Sell   | ------+
               +---------+

Answer 1

我不经常使用图形，但这段代码（使用Graph模块）似乎可以完成任务：

use Graph;
use strict;
my $graph = Graph->new;
while (<DATA>) {
    my ($dir, $x, $y) = split;
    if ($dir eq 'Downgrade') {
        ($x, $y) = ($y, $x);
    } elsif ($dir ne 'Upgrade') {
        die qq(Unknown direction "$dir"n);
    }
    $graph->add_edge($x, $y);
}
$graph->is_dag
    or die "Graph has a cycle--unable to analyzen";
$graph->is_weakly_connected
    or die "Graph is not weakly connected--unable to analyzen";
print join(' < ', $graph->topological_sort), "n";
__DATA__
Upgrade     Add           Buy
Downgrade   Add           Hold
Upgrade     Hold          Add
Downgrade   Buy           Outperform
Upgrade     Hold          Outperform
Downgrade   Hold          Reduce
Upgrade     Add           Outperform

这将打印Reduce < Hold < Add < Outperform < Buy。