Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re: Set intersection problem

by hv (Prior)
on May 23, 2023 at 12:45 UTC ( [id://11152388]=note: print w/replies, xml ) 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.

Log In?
Username:
Password:

What's my password?
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 rifling through the Monastery: (5)
As of 2024-03-29 11:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found