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

Basically you're trying to merge all sets with related values.

Well, the below logic isn't pretty, but it works. Not sure what the problem was with your code

#!/usr/bin/perl -w

use strict;
use warnings;

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

my %index = ();
for my $i (0..$#array) {
    for my $val (@{$array[$i]}) {
        push @{$index{$val}}, $i;
    }
}

for my $i (0..$#array) {
    my $arr = $array[$i] or next;
    $array[$i] = undef;

    my %values = ();
    for my $val (@$arr) {
        next if $values{$val}++;

        for my $ind (@{$index{$val}}) {
            my $related = $array[$ind] or next;
            $array[$ind] = undef;
            push @$arr, @$related;
        }
    }
    
    print join(' ', sort {$a <=> $b} keys %values), "\n";
}
[download]

Outputs

3 4 11 12 13
7 8 9
[download]

Comment on Re: how to find combine common elements of an array? Select or Download Code

Replies are listed 'Best First'.
Re^2: how to find combine common elements of an array? by wind (Priest) on Apr 26, 2011 at 02:13 UTC
Someone posted a related question recently, How can sets be recursively concatenated when intersecting with each other an so I've revisited my solution here. My primary concern with this particular algorithm is that it not duplicate effort. However, given more consideration I decided to go with a solution that was easier to understand in my new suggestion, Re: How can sets be recursively concatenated when intersecting with each other: `use strict; use warnings; my @array = map {[split]} ('11 12', '11 13', '9 8 7', '3 4', '11 4'); ORIG: for (my $i=0; $i<=$#array; $i++) { for my $j ($i+1..$#array) { my %seen; my @unique = grep {! $seen{$_}++} @{$array[$i]}, @{$array[$j]} +; if (@unique < @{$array[$i]} + @{$array[$j]}) { $array[$i] = \@unique; splice @array, $j, 1; redo ORIG; } } $array[$i] = join ' ', @{$array[$i]}; } print "$_\n" for (@array);` [download] However, my favorite solution is jaredor's below: Re^2: how to find combine common elements of an array?	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: how to find combine common elements of an array?
by wind (Priest) on Apr 26, 2011 at 02:13 UTC

Someone posted a related question recently, How can sets be recursively concatenated when intersecting with each other an so I've revisited my solution here. My primary concern with this particular algorithm is that it not duplicate effort. However, given more consideration I decided to go with a solution that was easier to understand in my new suggestion, Re: How can sets be recursively concatenated when intersecting with each other:

use strict;
use warnings;

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

ORIG: for (my $i=0; $i<=$#array; $i++) {
    for my $j ($i+1..$#array) {
        my %seen;
        my @unique = grep {! $seen{$_}++} @{$array[$i]}, @{$array[$j]}
+;
        if (@unique < @{$array[$i]} + @{$array[$j]}) {
            $array[$i] = \@unique;
            splice @array, $j, 1;
            redo ORIG;
        }
    }
    $array[$i] = join ' ', @{$array[$i]};
}

print "$_\n" for (@array);
[download]

However, my favorite solution is jaredor's below: Re^2: how to find combine common elements of an array?

[reply]
[d/l]