Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

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

by LanX (Bishop)
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 surveying the Monastery: (6)
As of 2018-06-19 22:55 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (115 votes). Check out past polls.