Узнайте порядок элементов

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,
    },
    ...

, но я ударился об стену, пытаясь понять, что делать в функции сортировки, когда его просят отсортировать пару, у которойr рассматривается как непосредственный сосед, поэтому отношения не определены.

Есть ли простое решение?Я иду об этом правильным путем?Есть ли лучший WTDI?

Спасибо,

Джон

Answer 1

Я пытался реализовать наивное решение самостоятельно. Я построил хэш %order, где значения каждого ключа были элементами, которые следовали за ним. Затем я создал транзитивное замыкание этой структуры (то есть, если first было раньше second, а second было раньше third, тогда first должно быть раньше third). Если бы информации было достаточно, каждый ключ имел бы различное количество значений, а сортировка элементов по количеству значений давала бы упорядоченный список.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my @partial = (
    [qw[ first second third sixth seventh tenth ]],
    [qw[ first third fourth fifth sixth ]],
    [qw[ third fifth seventh eighth ninth tenth ]]);

my %order;
my %all;
for my $list (@partial) {
    undef @all{ @$list };
    undef $order{ $list->[ $_ - 1 ] }{ $list->[$_] }
        for 1 .. $#$list;
}

my $changed = 1;
while ($changed) {
    undef $changed;
    for my $from (keys %order) {
        if (my @to = keys %{ $order{$from} }) {
            if (my @to2 = map keys %{ $order{$_} }, @to) {
                my $before = keys %{ $order{$from} };
                undef @{ $order{$from} }{@to2};
                $changed = 1 if $before != keys %{ $order{$from} };
            }
        }
    }
}

my %key_counts;
$key_counts{ keys %{ $order{$_} } }++ for keys %order;
warn "Not enough information\n"
    if keys %key_counts != keys %order;

say join ' ',
    sort { keys %{ $order{$b} } <=> keys %{ $order{$a} } }
    keys %order;

выход

first second third fourth fifth sixth seventh eighth ninth tenth

Answer 2

Это прямое и простое ручное решение.

Собирает все элементы в заданных подпоследовательностях и sort с ними.Критерием сортировки является позиция (индекс) сравниваемых элементов в первой подпоследовательности, которая имеет оба.Если ни одна из подпоследовательностей не имеет обоих элементов, неопределенный (ноль) возвращается из блока сортировки.

use warnings;
use strict;
use feature 'say';    
use List::MoreUtils qw(uniq firstval);

my @all = qw(ant bug frog cat dog elk);  # to draw input (sublists) from

my @s1 = @all[0,1,3,5];
my @s2 = @all[1,2,4,5];
my @s3 = @all[2,3,4];

my @inv = (                              # for index comparison
    { map { $s1[$_] => $_ } 0..$#s1 },  
    { map { $s2[$_] => $_ } 0..$#s2 },  
    { map { $s3[$_] => $_ } 0..$#s3 } 
);

my @sorted = sort { 
    my $fv = firstval { exists $_->{$a} and exists $_->{$b} } @inv;
    ($fv) ? $fv->{$a} <=> $fv->{$b} : 0;
} uniq @s1, @s2, @s3;

say "@sorted";

Сложность этого не так хороша, как может быть, так как некоторые из сравнений могут(в принципе) следует избегать, но это не показывает для небольших проблем.Он печатает правильную последовательность, а также для опубликованной проблемы (замените массивы @sN на предоставленные в вопросе).

Этот код предполагает последовательные и достаточно полные подпоследовательности.

---

Для произвольного числа подмножеств полного списка (3 выше) вспомогательный элемент @inv построен как

my @subseqs = (\@s1, \@s2, \@s3);

my @inv;

for my $rr (@subseqs) {
    push @inv, { map { $rr->[$_] => $_ } 0..$#$rr }
}

Answer 3

Вопрос, который вы связали с , включает другой ответ с использованием графика и топологической сортировки. Модуль 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