Re: how to find combine common elements of an array?

[jaredor]

Thanks to inspiration from BrowserUK and wind (though I still have a ways to go before I grok their replies) I think I have something to share if only for terseness.

#!/usr/bin/env perl

use strict;
use warnings;
use List::Util(qw(min));
use List::MoreUtils(qw(uniq));

my @array = map {[split]} ("11 12", "11 13", "9 8 7", "3 4", "11 4");

my %v2g = ();
my %g2v = ();

for my $i (@array) {
    my @sg = sort {$a<=>$b} uniq grep {defined} (@v2g{@$i}, min @$i);
    my $sg = shift @sg;
    $g2v{$v2g{$_} ||= $sg}->{$_}++ for @$i;
    for my $j (@sg) {
        @v2g{keys %{$g2v{$j}}} = ($sg) x keys %{$g2v{$j}};
        @{$g2v{$sg}}{keys %{$g2v{$j}}} = values %{$g2v{$j}};
        delete $g2v{$j};
    }
}

print join ("\n", map {join " ", sort {$a<=>$b} keys %$_} values %g2v)
+, "\n";

Output

3 4 11 12 13
7 8 9

About the only thing really new to add to the discussion is that this problem seems to be equivalent to finding the disjoint subgraphs of a vertex adjacency matrix of a non-directed graph. So there's probably an algorithm out there that puts this code's efficiency to shame.