Perl Cookbook

Computing Union, Intersection, or Difference of Unique Lists

Problem

You have a pair of lists, each having unduplicated items. You’d like to find out which items are in both lists (intersection), one but not the other (difference), or either (union).

Solution

The following solutions need the listed initializations:

@a = (1, 3, 5, 6, 7, 8);
@b = (2, 3, 5, 7, 9);

@union = @isect = @diff = ();
%union = %isect = ();
%count = ();

Simple solution for union and intersection

foreach $e (@a) { $union{$e} = 1 }

foreach $e (@b) {
    if ( $union{$e} ) { $isect{$e} = 1 }
    $union{$e} = 1;
}
@union = keys %union;
@isect = keys %isect;

More idiomatic version

foreach $e (@a, @b) { $union{$e}++ && $isect{$e}++ }

@union = keys %union;
@isect = keys %isect;

Union, intersection, and symmetric difference

foreach $e (@a, @b) { $count{$e}++ }

foreach $e (keys %count) {
    push(@union, $e);
    if ($count{$e} == 2) {
        push @isect, $e;
    } else {
        push @diff, $e;
    }
}

Indirect solution

@isect = @diff = @union = ();

foreach $e (@a, @b) { $count{$e}++ }

foreach $e (keys %count) {
    push(@union, $e);
    push @{ $count{$e} == 2 ? \@isect : \@diff }, $e;
}

Discussion

The first solution most directly computes the union and intersection of two lists, neither containing duplicates. Two different hashes are used to record whether a particular item goes in the union or the intersection. We first put every element of the first array in the union hash, giving it a true value. Then processing each element of the second array, we check whether that ...