Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

Re: "Intelligent" array joining (topological sort)

by tye (Sage)
on Feb 05, 2004 at 22:56 UTC ( [id://326925]=note: print w/replies, xml ) Need Help??


in reply to "Intelligent" array joining

#!/usr/bin/perl -w use strict; sub tsort { my( %pred, %succ ); for my $av ( @_ ) { for my $i ( 1 .. $#$av ) { $pred{$av->[$i]}{$av->[$i-1]} ||= 1; $succ{$av->[$i-1]}{$av->[$i]} ||= 1; } $succ{$av->[-1]} ||= {}; } my @output; while( %succ ) { my( $best, $count ); for my $item ( keys(%succ) ) { my $preds= keys %{$pred{$item}}; if( ! defined($count) || $preds < $count ) { $best= $item; $count= $preds; last if 0 == $count; } } warn "Data contains a cycle, breaking at $best.\n" if 0 < $count; push @output, $best; for my $succ ( keys %{$succ{$best}} ) { delete $pred{$succ}{$best}; } delete $succ{$best}; } return wantarray ? @output : \@output; } my @array1= ( 1, 3, 4, 6 ); my @array2= ( 1, 2, 4, 6 ); my @array3= ( 1, 2, 3, 5 ); my @output= tsort( \( @array1, @array2, @array3 ) ); print "@output\n"; @output= tsort( [1,2,3,4], [1,3,2,4] ); print "@output\n";
output is
1 2 3 4 5 6 Data contains a cycle, breaking at 2. 1 2 3 4

- tye        

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://326925]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (5)
As of 2024-03-19 10:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found