交错稀疏排序数组

Question

我有一套事件清单.事件总是以给定的顺序发生,但不是每个事件总是发生.这是一个示例输入:

[[ do, re, fa, ti ],
 [ do, re, mi ],
 [ do, la, ti, za ],
 [ mi, fa ],
 [ re, so, za ]]

输入值没有任何固有顺序.它们实际上是"创建符号链接"和"重新索引搜索"等消息.它们在单个列表中排序,但是没有办法只查看第一个列表中的"fa"和第二个列表中的"mi",并确定哪个位于另一个列表之前.

我希望能够获取该输入并生成所有事件的排序列表:

[ do, re, mi, fa, so, la, ti, za ]

或者更好的是,有关每个事件的一些信息,如计数:

[ [do, 3], [re, 3], [mi, 2],
  [fa, 2], [so, 1], [la, 1],
  [ti, 1], [za, 2] ]

我正在做什么名字？有接受的算法吗？我在Perl中写这个,如果这很重要,但伪代码会这样做.

我知道,根据我的示例输入,我可能无法保证"正确"的顺序.但我真正的输入有万吨以上的数据点,我有信心,有一些聪明这将是95%权(这实在是我所需要的).如果我不需要,我只是不想重新发明轮子.

Answer 1

您可以根据您观察到的顺序tsort推断出合理的\xe2\x80\x94，尽管不一定是唯一的\xe2\x80\x94排序顺序（称为拓扑顺序）。您可能有兴趣阅读tsort\ 的原始用途，其结构与您的问题类似。

\n\n

请注意，这tsort需要非循环图。就您的示例而言，这意味着您无法在一个序列中看到 do 后跟 re，而在另一个序列中看不到 re 后跟 do。

\n\n

#! /usr/bin/perl\n\nuse warnings;\nuse strict;\n\nuse IPC::Open2;\n\nsub tsort {\n  my($events) = @_;\n\n  my $pid = open2 my $out, my $in, "tsort";\n\n  foreach my $group (@$events) {\n    foreach my $i (0 .. $#$group - 1) {\n      print $in map "@$group[$i,$_]\\n", $i+1 .. $#$group;\n    }\n  }\n\n  close $in or warn "$0: close: $!";\n\n  chomp(my @order = <$out>);\n  my %order = map +(shift @order => $_), 0 .. $#order;\n  wantarray ? %order : \\%order;\n}\n

\n\n

由于您将数据描述为稀疏数据，因此上面的代码提供了tsort有关事件邻接矩阵的尽可能多的信息。

\n\n

有了这些信息，计算直方图并对其成分进行排序就很简单了：

\n\n

my $events = [ ... ];\n\nmy %order = tsort $events;\n\nmy %seen;\ndo { ++$seen{$_} for @$_ } for @$events;\n\nmy @counts;\nforeach my $event (sort { $order{$a} <=> $order{$b} } keys %seen) {\n  push @counts => [ $event, $seen{$event} ];\n  print "[ $counts[-1][0], $counts[-1][1] ]\\n";\n}\n

\n\n

对于您提供的问题中的输入，输出是

\n\n

[ do, 3 ]\n[ la, 1 ]\n[ re, 3 ]\n[ so, 1 ]\n[ mi, 2 ]\n[ fa, 2 ]\n[ ti, 2 ]\n[扎, 2 ]

\n\n

这看起来很有趣，因为我们知道 solf\xc3\xa8ge 的顺序，但是 re 和 la 在定义的偏序$events中是不可比较的：我们只知道它们必须都在 do 之后。

\n