1

最近ここで質問したところ、非常にエレガントな回答が得られました。ここにあります：

複数のリストから親子要素の順序付きリストを生成する方法を参照してください。

複数のルートが存在する可能性があるという同様の問題があります。つまり、別々のツリーがあります。以下は例です (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 は独立しているため、順序は重要ではありません)。2 つの解決策の例を次に示します。

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

重要:配列番号 3 を見てください。H は、4 番目の配列では G の子ですが、G の前に来ます。したがって、各配列には特定の子の順序はありませんが、最終結果 (上に示すように) では、子/連の前に親が必要です。

ここで、A と H は互いに独立していますが、共通のノードを使用します。

4

1 に答える 1

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;
于 2012-05-03T16:50:23.800 に答える