perl - 如何从具有多个根的多个列表中生成有序的父子元素列表？

Question

我最近在这里问了一个问题，并得到了一些非常优雅的答案。这里是：

访问如何从多个列表中生成一个有序的父子元素列表？

我有一个类似的问题，其中可以有多个根，这意味着有单独的树。这是一个示例（在 perl 中）；

my @rules = (
  [ qw( A B C ) ],
  [ qw( B D E ) ],
  [ qw( C H G ) ],
  [ qw( G H   ) ],
  [ qw( Z C   ) ]
);

在列表列表中@rules，A 是 B 和 C 的父元素。通常，第一个元素是列表中其余元素的父元素。

我想处理这组数组，并生成一个包含正确顺序的列表。在这里，A 和 Z 必须在其他元素之前（A 和 Z 的顺序并不重要，因为它们是独立的）。以下是两个示例解决方案：

(A,Z,B,C,D,E,F,G,H), or (Z,A,B,D,E,F,C,G,H)

重要提示：查看数组编号 3；H 在 G 之前，即使它是第四个数组中 G 的子元素。因此，每个数组中没有特定的子元素顺序，但在最终结果中（如上所示）必须在子元素/人之前有任何父元素。

Answer 1

这个怎么样？不过，这很简单。

my @rules = (
  [ qw( A B C ) ],
  [ qw( B D E F ) ],
  [ qw( C H G ) ],
  [ qw( G H   ) ],
  [ qw( Z C   ) ]
);

my %weight_for;
for (@rules) {
  my ($parent, @children) = @{$_};
  $weight_for{$_}++ for ($parent, @children);
  $weight_for{$_} += $weight_for{$parent} 
    for @children; 
}

print "$_ = $weight_for{$_}\n" 
  for sort { $weight_for{$a} <=> $weight_for{$b} } keys %weight_for;