Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

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

by LanX (Chancellor)
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) } }


( ["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)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1058906]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (5)
As of 2017-06-23 07:46 GMT
Find Nodes?
    Voting Booth?
    How many monitors do you use while coding?

    Results (536 votes). Check out past polls.