Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: treat pairs, set as one item: looking for better way

by LanX (Canon)
on Oct 19, 2013 at 11:59 UTC ( #1058906=note: print w/ replies, xml ) Need Help??


in reply to treat pairs, set as one item: looking for better way

This should be safe! (compare also algorithm of tarjan).

Plz note thiss should also work with sets which are bigger than just pairs.

use strict; use warnings; use Data::Dump qw/pp/; my @key_array = 'a' .. 'z'; my @set_array = ( ['a', 'b'], ['e','f'], ['f','g'] ); my (%neighbors,%group,%mark); # collect all neighbors per vertex for my $pair (@set_array) { for my $vert (@$pair){ push @{$neighbors{$vert}},@$pair; } } #pp \%neighbors; # mark all connected vertices with same group-id my $group=1; for my $vert (@key_array) { mark($vert,$group++); } #pp "group",\%group,"mark",\%mark; # sort result by size and alphabetically pp sort {@$b<=>@$a or $a->[0] cmp $b->[0]} values %group; sub mark { # recursivly (deep) mark neighbors my ($vert,$group)=@_; return if $mark{$vert}; $mark{$vert}=$group; push @{$group{$group}},$vert; for my $neighbor (@{$neighbors{$vert}}) { mark($neighbor,$group) } }

output:

( ["e", "f", "g"], ["a", "b"], ["c"], ["d"], ["h"], ["i"], ["j"], ["k"], ["l"], ["m"], ["n"], ["o"], ["p"], ["q"], ["r"], ["s"], ["t"], ["u"], ["v"], ["w"], ["x"], ["y"], ["z"], )

Cheers Rolf

( addicted to the Perl Programming Language)


Comment on Re: treat pairs, set as one item: looking for better way
Select or Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (6)
As of 2014-08-23 06:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (172 votes), past polls