Simple algorithms for bag operations

test_bags.pl

use Data::Dumper;
use strict;
sub randlists {
    sort { @$a <=> @$b } map([sort { $a <=> $b } map(int(rand() * 20), 0.. (15 + int(30 * rand())))], 0..2);
}
my(@bb) = randlists();
#$bb[1] = [-2];
my @b = map([@$_], @bb);
$Data::Dumper::Terse = 1;
$Data::Dumper::Indent = 0;
print("Input: ", Dumper($_), "\n") for @b;
my $bc = @b - 1;
my @r;
outer: while(@{$b[0]}) {
    my $e = $b[0]->[0];
    my $g = 1;
    for my $j (1 .. $bc) {
        shift @{$b[$j]} while @{$b[$j]} && $b[$j]->[0] < $e;
        last outer unless @{$b[$j]};
        $g &&= $b[$j]->[0] == $e;
    }
    #push @r, $e if $g;
    #shift @$_ for @b;
    if($g) {
        push @r, $e;
        shift @$_ for @b[1..$bc];
    }
    shift @{$b[0]};
}

print("Intersect: ", Dumper(\@r), "\n");

my(%p, %n);
(@b) = map([@$_], @bb);
@r = ();
for my $c (@b) {
    %n = ();
    for my $d (@$c) {
        push @r, $d if ++($n{$d}) > ($p{$d} || 0);
    }
    for(keys %n) {
        $p{$_} = $n{$_} if $n{$_} > ($p{$_} || 0);
    }
}

print("Union: ", Dumper(\@r), "\n");

(@b) = map([@$_], @bb);
my @h = map(+{}, 0..$bc);
my %m;
@r = ();
for my $i (0..$bc) {
    for(@{$b[$i]}) {
        ($h[$i]->{$_})++;
        $m{$_} = 1;
    }
}
#print Dumper(\@h);
for my $v (sort { $a <=> $b } keys %m) {
    my $x = 1;
    $x *= ($h[$_]->{$v} || 0) for 0..$bc;
    #print "$v x $x, ";
    push @r, (0+$v) x $x;
}
print("Product: ", Dumper(\@r), "\n");

(@b) = map([@$_], @bb);
(@h) = map(+{}, 0..$bc);
(%m) = ();
@r = ();
for my $i (0..$bc) {
    for(@{$b[$i]}) {
        ($h[$i]->{$_})++;
        $m{$_} = 1;
    }
}
#print Dumper(\@h);
for my $v (sort { $a <=> $b } keys %m) {
    my $x = ($h[0]->{$v} || 0);
    $x = ($h[$_]->{$v} || 0) < $x ? ($h[$_]->{$v} || 0) : $x for 1..$bc;
    #print "$v x $x, ";
    push @r, (0+$v) x $x;
}

print("Intersect2: ", Dumper(\@r), "\n");

# Trivial op...
(@r) = sort { $a <=> $b } map((@$_), @bb);
print("Concatenate: ", Dumper(\@r), "\n");