Freeware JavaScript Editor Perl Tutorials

↑

Main Page |

## Recipe 4.9 Computing Union, Intersection, or Difference of Unique Lists## 4.9.1 Problem
You have a pair of lists, each holding
unduplicated items. You'd like to find out which items are in both
lists ( ## 4.9.2 SolutionThe 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 = ( ); ## 4.9.2.1 Simple solution for union and intersectionforeach $e (@a) { $union{$e} = 1 } foreach $e (@b) { if ( $union{$e} ) { $isect{$e} = 1 } $union{$e} = 1; } @union = keys %union; @isect = keys %isect; ## 4.9.2.2 More idiomatic versionforeach $e (@a, @b) { $union{$e}++ && $isect{$e}++ } @union = keys %union; @isect = keys %isect; ## 4.9.2.3 Union, intersection, and symmetric differenceforeach $e (@a, @b) { $count{$e}++ } @union = keys %count; foreach $e (keys %count) { if ($count{$e} = = 2) { push @isect, $e; } else { push @diff, $e; } } ## 4.9.2.4 Indirect solution@isect = @diff = @union = ( ); foreach $e (@a, @b) { $count{$e}++ } @union = keys %count; foreach $e (keys %count) { push @{ $count{$e} = = 2 ? \@isect : \@diff }, $e; } ## 4.9.3 DiscussionThe first solution most directly computes the union and intersection of two lists, neither containing duplicates. Two hashes are used to record whether a particular item goes in the union or the intersection. We 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 element is already present in the union. If it is, we put it in the intersection as well. In any event, it goes into the union. When we're done, we extract the keys of both the union and intersection hashes. The values aren't needed. The second solution (Recipe 4.8.2.2) is essentially
the same but relies on familiarity with the Perl (and
awk, C, C++, and Java) The third solution uses just one hash to track how many times each element is seen. Once both arrays have their elements recorded in the hash, we grab those keys and put them in the union. Then we process those hash keys one at a time. Keys whose values are 2 were in both arrays, so they go in the intersection array. Keys whose values are 1 were in just one of the two arrays, so they go in the difference array. Elements of the output arrays are not in the same order as those in the input arrays. The last solution, like the previous one, uses just one hash to count
how many times each element is encountered. Here, though, we
dynamically select one of two possible arrays by placing within the
In this recipe we compute the
symmetric difference, not the simple difference. These are terms from
set theory. A ## 4.9.4 See AlsoThe "Hashes" section of Chapter 2 of Programming Perl; Chapter 5; we use hashes in a similar fashion in Recipe 4.7 and Recipe 4.8 |

Main Page |

↓

JavaScript Verifier Perl Tutorials

©