Как создать упорядоченный список в Perl из набора сравнений неравенства? - PullRequest
Новая
       9

Как создать упорядоченный список в Perl из набора сравнений неравенства?

2 голосов
/ 20 января 2012

Я играю с историческим анализом фондового рынка в Perl. Один аспект связан с анализом точности исследовательских компаний прошлых рейтингов акций. Самая элементарная рейтинговая шкала будет «Купить, Держать, Продавать». Однако многие из этих фирм используют различную терминологию, некоторые с оценкой более 3 баллов.

У меня есть список тысяч улучшений / понижений, выпущенных сотнями различных фирм (из Yahoo Finance), который выглядит примерно так: 

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, D

Что мне нужно для каждой исследовательской фирмы, если взять длинный список этих сравнений, так это упорядоченный список, который выглядит следующим образом:

A> B> C> D> E

Я много думал об этой проблеме и не могу найти решение. Если бы каждое повышение / понижение уровня прыгало только на один шаг, я думаю, что смогу это сделать, но я не могу обернуться, как вставить сравнение, например C

У кого-нибудь есть идеи?




Обновление:

Спасибо @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   | ------+
               +---------+

1 Ответ

5 голосов
/ 20 января 2012

Я не часто использую графики, но этот код (использующий модуль 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 analyze\n";
$graph->is_weakly_connected
    or die "Graph is not weakly connected--unable to analyze\n";

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.

...