Perl Monk, Perl Meditation PerlMonks

### Re: Set intersection problem

by hv (Prior)
 on May 23, 2023 at 12:45 UTC Need Help??

in reply to Set intersection problem

I think a possible approach to this would look roughly like: create an individual hash lookup for each array, and an additional results hash containing all the elements; then for each element of the results hash, check its presence in each of the individual hashes and build up a representation (such as a bitvector) to reflect that. If you need to group elements by the type of intersection, you can store a result by the bitvector in yet another hash.

```my \$grouped = intersector([1..5], [3..7], [2, 6]);
print join(' ', @\$_), "\n" for values %\$grouped;
# output (in some order):
# 2
# 6
# 1
# 5 3 4
# 7
exit 0;

sub intersector {
# accept a list of arrayrefs
my @ar = @_;
my(%all, @single);
# initialize the results hash %all and all the individual hashes in
+@single
for my \$i (0 .. \$#ar) {
my \$a = \$ar[\$i];
@all{@\$a} = (undef) x @\$a;
\$single[\$i] = { map +(\$_ => undef), @\$a };
}
# now for each element, find its signature
for my \$el (keys %all) {
my \$sig = '';
for my \$i (0 .. \$#ar) {
vec(\$sig, \$i, 1) = 1 if exists \$single[\$i]{\$el};
}
# store the final signature in the results array if needed
\$all{\$el} = \$sig;
# store the element by its signature if needed
push @{ \$grouped{\$sig} }, \$el;
}
# now analyse further, or return a result
return \%grouped;
}

A space saving can be made by combining the two main loops, removing the need for @single; I'll leave that as an exercise for the reader.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11152388]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others cooling their heels in the Monastery: (5)
As of 2024-09-20 10:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The PerlMonks site front end has:

Results (25 votes). Check out past polls.

Notices?
 • erzuuli ‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.