On Jan 29, 2008 10:57 AM, David Golden <[EMAIL PROTECTED]> wrote:
> On Jan 29, 2008 12:11 PM, Tolkin, Steve <[EMAIL PROTECTED]> wrote:
> > I want to reconstruct the underlying list. In other words the order of
> > the elements agrees in all the lists, but there is no sort condition.
> >
> > Example:
> > List 1: dog, cat, mouse
> > List 2: dog, shark, mouse, elephant
> >
> > There are 2 possible outputs, and I do not care which one I get.
> >
> > The reason that I have not just coded this up is that it seems it
> > require an unbounded amount of look ahead. Also, when there are more
> > than 2 lists, I think I need to read from all of them before making a
> > decision about which element can be safely output.
Yes, this is true. You need an unbounded look ahead. Because you
might have 5 lists, and the last item of list 1 might be the first
item of list 2, the last of list 2 might be the first of last 3, etc.
Until you've read each list in full you can't know how to solve it.
> What comes to mind is indexing all of the words on the maximum depth
> they occur in any list. Then you output all the elements of max_depth
> 1 (dog), all the elements of max_depth 2 (cat, shark), max_depth 3
> (mouse), max_depth 4 (elephant).
List 1: dog, cat, mouse, rat, chimp
List 2: chimp, gorilla, kangaroo
The algorithm you described would output gorilla before rat.
> You still have to read all the lists at least once, though.
That is logically unavoidable.
Here is some lightly tested code to do what is asked. It has, though,
no error checking.
sub merge_lists {
my @list_infos
= map { {
list => $_,
depth => {},
position => 0,
done => 0,
} } @_;
# Create indexes.
for my $list_info (@list_infos) {
my $list = $list_info->{list};
my $depth = $list_info->{depth};
for my $i (0..$#$list) {
$depth->{$list->[$i]} = $i;
}
}
my @merged_list;
FIND_ELEMENT: while (@list_infos) {
LIST: for my $list_info (@list_infos) {
my $element = $list_info->{list}->[ $list_info->{position} ];
# Is this element one that can go next?
for my $other_list_info (@list_infos) {
my $other_position = $other_list_info->{position};
my $other_depth = $other_list_info->{depth}->{$element};
if ($other_depth and $other_depth > $other_list_info->{position}) {
# Oops, we'll have to take an element from another list.
next LIST;
}
}
# We've found our element, let's do bookkeeping
push @merged_list, $element;
for my $other_list_info (@list_infos) {
my $other_list = $other_list_info->{list};
my $other_position = $other_list_info->{position};
if ( $element eq $other_list->[$other_position] ) {
if ($other_position == $#$other_list) {
$other_list_info->{done} = 1;
}
else {
$other_list_info->{position}++;
}
}
}
# And cleanup.
@list_infos = grep {not $_->{done}} @list_infos;
next FIND_ELEMENT;
}
}
return @merged_list;
}
And to run it just call:
merge_list([qw(dog cat mouse)], [qw(dog shark mouse elephant)];
Cheers,
Ben
_______________________________________________
Boston-pm mailing list
Boston-pm@mail.pm.org
http://mail.pm.org/mailman/listinfo/boston-pm
