#! perl -slw
use strict;
use List::Util qw[ max sum ];

our $W ||= 2; my( $W1, $W2, $S2 ) = ( 'a'x$W, 'z'x$W, 'b'x$W );
our $I ||= 2; my( $I1, $I2 )      = ( 'a'x$I, 'z'x$I );
our $NODETAILS;
our $SRAND ||= 12345;

srand( $SRAND ) if $SRAND;

my @allWords = 'k'.$W1 ... 'k'.$W2;						## All the words
my @stopWords = 'k'.$W1 ..'k'.$S2;						## Those rejected as 'noise'
my @keyWords = @allWords[ @stopWords .. @allWords ];	## Only the ones we are interested in
print "Keywords: " . @keyWords;

## The item names
my @items = 'i'.$I1 .. 'i'.$I2;
print "Items: " . @items;

## Builds the same dataset as the example datasets generator
## Just represents it in a more compact and malleable form.
my @itemMap;
for my $item ( 0 .. $#items ) {
	my $count = 4 + int rand( 8 * (1+ (($W-2) * 26)) );
	my $vector = '';
	vec( $vector, int( rand() * rand() * @keyWords ), 1 ) = 1 while $count--;
	$itemMap[ $item ] = $vector;
}

## Partition items into nonoverlapping sets
my %partns;
OUTER: for my $itemno ( 0 .. $#items ) {
	for my $partn ( keys %partns ) {
		next unless $partns{ $partn }; ## Skip old ones
		my $common = unpack '%b*', ( $itemMap[ $itemno ] & $partn );
		next unless $common;

		my $newPartn = $partn & $itemMap[ $itemno ];## Form a new partition key
		$partns{ $newPartn } = $partns{ $partn };	## move over the old item numbers
		push @{ $partns{ $newPartn } }, $itemno;	## Add the new one
		delete $partns{ $partn } unless $partn eq $newPartn;	## delete the old partiton
		next OUTER;
	}
	## If we got here, this item had no keywords in common with any existing partition
	## So start a new one
	$partns{ $itemMap[ $itemno ] } = [ $itemno ];
}

unless( $NODETAILS ) {
	print "[ @$_ ]" for values %partns;
}
print scalar keys %partns, " partitons found.";

exit;