Perl Monk, Perl Meditation PerlMonks

### 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??

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)

Create A New User
Node Status?
node history
Node Type: note [id://1058906]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (4)
As of 2017-08-21 23:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (326 votes). Check out past polls.

Notices?