2

私はこの問題を抱えています:いくつかの配列が与えられた場合(たとえば、Perlまたは他の言語で):

1. (A,B,C)
2. (B,D,E,F)
3. (C,H,G)
4. (G,H)

各配列では、最初の要素が親で、残りはその子です。この場合、要素 A には 2 つの子 B と C があり、B には 3 つの子 D、E、F があります。この配列のセットを処理し、正しい順序を含むリストを生成したいと思います。この場合、A がルート要素なので B と C が続き、B の下には D、E、F があり、C の下には G と H があり、G も子として H を持っています (つまり、要素は複数の親を持つことができます)。 ）。これが結果の配列になるはずです。

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

(A,B,C,D,E,F,G,H) または (A,C,B,D,E,F,G,H) または (A,B,C,G,H,D,E) 、F)

その配列を作成する再帰的な方法があればいいのですが、必須ではありません。御時間ありがとうございます..

4

2 に答える 2

1

ノードに複数の親がある可能性がなければ、これは単純な注文後のトラバーサルになります。

これを回避するための最も簡単な方法は、各ノードに層レベルを割り当てることです。この場合H、ティア3とティア4の両方に表示され、必要なのは常に最大のティア番号です。

このコードはその設計を実装します。

use strict;
use warnings;

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

# Build the tree from the set of rules
#
my %tree;

for (@rules) {
  my ($parent, @kids) = @$_;
  $tree{$parent}{$_}++ for @kids;
}

# Find the root node. There must be exactly one node that
# doesn't appear as a child
#
my $root = do {
  my @kids = map keys %$_, values %tree;
  my %kids = map {$_ => 1} @kids;
  my @roots = grep {not exists $kids{$_}} keys %tree;
  die qq(Multiple root nodes "@roots" found) if @roots > 1;
  die qq(No root nodes found) if @roots < 1;
  $roots[0];
};

# Build a hash of nodes versus their tier level using a post-order
# traversal of the tree
#
my %tiers;
my $tier = 0;
traverse($root);

# Build the sorted list and show the result
#
my @sorted = sort { $tiers{$a} <=> $tiers{$b} } keys %tiers;
print "@sorted\n";

sub max {
  no warnings 'uninitialized';
  my ($x, $y) = @_;
  $x > $y ? $x : $y;
}

sub traverse {
  my ($parent) = @_;
  $tier++;
  my @kids = keys %{ $tree{$parent} };
  if (@kids) {
    traverse($_) for @kids;
  }
  $tiers{$parent} = max($tiers{$parent}, $tier);
  $tier--;
}

出力

A B C F E D G H

編集

これは、配列のハッシュとして少しきれいに機能します。これがそのリファクタリングです。

use strict;
use warnings;

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

# Build the tree from the set of rules
#
my %tree;

for (@rules) {
  my ($parent, @kids) = @$_;
  $tree{$parent} = \@kids;
}

# Find the root node. There must be exactly one node that
# doesn't appear as a child
#
my $root = do {
  my @kids = map @$_, values %tree;
  my %kids = map {$_ => 1} @kids;
  my @roots = grep {not exists $kids{$_}} keys %tree;
  die qq(Multiple root nodes "@roots") if @roots > 1;
  die qq(No root nodes) if @roots < 1;
  $roots[0];
};

# Build a hash of nodes versus their tier level using a post-order
# traversal of the tree
#
my %tiers;
traverse($root);

# Build the sorted list and show the result
#
my @sorted = sort { $tiers{$a} <=> $tiers{$b} } keys %tiers;
print "@sorted\n";

sub max {
  no warnings 'uninitialized';
  my ($x, $y) = @_;
  $x  > $y ? $x : $y;
}

sub traverse {

  my ($parent, $tier) = @_;
  $tier //= 1;

  my $kids = $tree{$parent};
  if ($kids) {
    traverse($_, $tier + 1) for @$kids;
  }
  $tiers{$parent} = max($tiers{$parent}, $tier);
}

複数の正しい順序がある場合、出力は前のソリューションと同等です。A常に最初とH最後になり、可能性があることに注意してくださいA C B F G D E H。

于 2012-04-25T20:17:13.973 に答える
0

このバージョンも機能しますが、すべての正解の順列が得られるため、毎回正しい結果が得られますが、以前の結果とは異なる場合があります (多くの空き時間がない限り...:-))。

#!/usr/bin/perl -w

use strict;
use warnings;

use Graph::Directed qw( );

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

print @rules;

my $graph = Graph::Directed->new();

for (@rules) {
   my $parent = shift(@$_);
   for my $child (@$_) {
  $graph->add_edge($parent, $child);
   }
}

$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(); # for eks A C B D G H E F
于 2012-04-29T10:22:34.923 に答える