citromatik has asked for the wisdom of the Perl Monks concerning the following question:

Hi all, I'm trying to merge lists of words into a tree-like structure. For example, given the following input: 
my @list1 = qw/Truck Car Byke/;
my @list2 = qw/Truck Car Scooter/;
my @list3 = qw/Truck Trailer Skates/;

[download]
Obtain a tree-like structure like this: 
Truck
   |_____ Car
   |       |_______Byke
   |       |_______Scooter
   |
   |_____Trailer
           |_______Skates

[download]

Maybe implementing the tree as a hash of hash refs would be a good solution: 

{'Truck' => {
              'Car' => {
                   'Byke' => ?,
                   'Scooter' => ?
              },
             'Trailer' => {
                  'Skates' => ?
            }
}

[download]

But every attemp to implement an algorithm to make the conversion ends with a too obfuscated code involving too much recursion. (Well, surely, the obfuscation comes from me)

Maybe I'm missing a simpler solution. Any idea on how to solve this would be highly appreciated

Thank you very much in advance

citromatik

Replies are listed 'Best First'.
Re: trees of word lists
by GrandFather (Saint) on Jan 22, 2009 at 20:02 UTC

    I'm not sure what you might consider obscure so the following non-recursive code might be either obscure or elegant:

    use strict;
use warnings;
use Data::Dump::Streamer;

my @list1 = qw/Truck Car Byke/;
my @list2 = qw/Truck Car Scooter/;
my @list3 = qw/Truck Trailer Skates/;
my %tree;

for my $list (\@list1, \@list2, \@list3, ) {
    my $node = \%tree;
    
    $node = $node->{shift @$list} ||= {} while @$list;
}

Dump \%tree;

    [download]

    Prints:

    $HASH1 = { Truck => {
           Car     => {
                        Byke    => {},
                        Scooter => {}
                      },
           Trailer => { Skates => {} }
         } };

    [download]
    Perl's payment curve coincides with its learning curve.
[reply]
[d/l]
[select]

      Every day I realize I have more to learn. Your code is much more elegant than my recursive solution.

      use warnings;
use strict;
use Data::Dumper;

my @lists = ([qw/Truck Car Bike/],
             [qw/Truck Car Scooter/],
             [qw/Truck Trailer Skates/]);

my %tree;

for my $list (@lists) {
    to_tree(\%tree, $list);
}

print Dumper(\%tree);

sub to_tree {
    my ($head, $list) = @_;
    my $node = shift @$list;

    return unless defined $node;

    $head->{$node} ||= {};
    to_tree($head->{$node}, $list);
}

      [download]
[reply]
[d/l]

        I am not even sure I would call your code inelegant. I find it very easy to understand, and very much what I would have written.

        --MidLifeXis

[reply]
Re: trees of word lists
by apl (Monsignor) on Jan 22, 2009 at 18:44 UTC
    You could try a hash with concatenated keys (i.e. $table{'Truck.Car.Scooter'} rather than $table{Truck}{Car}{Scooter}), and determine when to display a new subtree when looping through the sorted keys of the hash after you've preprocessed your table.

    When doing the display you'd have to keep track of how far down you are in the "structure" (i.e. how many periods are in the key) and what the previous key had been (so you'd know whether or not to start a new branch).

[reply]
[d/l]
[select]
Re: trees of word lists
by zentara (Cardinal) on Jan 22, 2009 at 19:52 UTC
[reply]
Re: trees of word lists
by MidLifeXis (Monsignor) on Jan 22, 2009 at 18:38 UTC

    What have you tried? This sounds an awful lot like a good homework problem. Since you have been here a while, I am guessing that How (not) to ask a question does not apply here :-).

    Personally, I would think that recursion would be an ideal solution in this case.

    If there is a memory issue due to a large data set, then the recursion can be addressed, and you might want to look at DBM::Deep for storage instead of an in-memory hash.

    --MidLifeXis

[reply]
Re: trees of word lists
by JavaFan (Canon) on Jan 22, 2009 at 19:52 UTC
    Edge cases are important here. Your example has word lists all of the same length. In that the case with your real data as well? If not, can you have the following two lists: 
        @list1 = qw [Truck Car];
    @list2 = qw [Truck Car Byke];

    [download]
    If you can, how must the resulting structure look time?
[reply]
[d/l]
      JavaFan,
      I agree that edge cases are important here but I think the requirements are very ill defined to even point them out. Is each list to be read from left to right as item 1 is parent to item to which is parent to item 3? Is there any way for a branch to have more than one child in a single list? Does the order of the words matter? I think a lot is implied that should be stated explicitly.

      Cheers - L~R

[reply]

Back to Seekers of Perl Wisdom