Re: Set intersection problem

[hv]

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.