如何从多个列表中生成父子元素的有序列表? [英] How to generate an ordered list of parent-child elements from multiple lists?

问题描述

我有这个问题:给定许多数组(例如Perl或任何其他语言):

I have this problem: Given a number of arrays (for example in Perl, or any other language):

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

在每个数组中，第一个元素是父元素，其余元素是其子元素.在这种情况下，元素A有两个孩子B和C，而B有三个孩子D，E和F等.我想处理这组数组，并生成一个包含正确顺序的列表.在这种情况下，A是根元素，因此B和C出现，然后在B下是D，E和F，在C下是G和H，并且G也有H作为子元素(这意味着一个元素可以有多个父元素).这应该是结果数组.

In each array, the first element is the parent, the rest are its children. In this case, element A has two children B and C, and B has three children D, E, and F, etc. I would like to process this set of arrays, and generate a list which contains the correct order. In this case, A is the root element, so comes B and C, then under B is D, E and F, and under C is G and H, and G also has H as children (which means an element can have multiple parent). This should be the resulting array.

重要:请看数组3，H在G之前，即使它是第四个数组中G的子代.因此，每个数组中的子级没有特定的顺序，但是在最终结果(如下所示)中，子级之前必须有任何父级.

Important: Look at array number 3, H comes before G, even though it's a child of G in the fourth array. So there is not particular order of children in each array, but in the final result (as shown below), must have any parent before it's child/ren.

(A，B，C，D，E，F，G，H)或(A，C，B，D，E，F，G，H)或(A，B，C，G，H， D，E，F)

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

最好有一些创建该数组的递归方法，但不是必需的. 谢谢您的时间..

Would be nice to have some recursive way of creating that array, but not a requirement. Thanks for your time..

推荐答案

如果不是因为一个节点有多个父节点，这将是一个简单的后遍历.

This would be a simple post-order traversal if it wasn't for the possibility that a node has multiple parents.

要解决这个问题，最简单的方法是为每个节点分配一个 tier 级别.在这种情况下，H出现在第3层和第4层上，并且始终是最高层号.

To get around this, the easiest method is to assign a tier level to each node. In this case H appears on both tiers 3 and 4, and it is always the highest tier number that is required.

此代码实现了该设计.

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

---

修改

这可以更干净地用作数组的哈希.这就是重构.

This works slightly more cleanly as a hash of arrays. Here is that refactor.

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是可能的.

The output is equivalent to the previous solution, given that there are multiple correct orderings. Note that A will always be first and H last, and A C B F G D E H is a possiblity.

这篇关于如何从多个列表中生成父子元素的有序列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！