#HTML:Handle (finite) sets.<BR>

package set;

# Since I want to use nested data structure,
require 5;
use strict 'refs';

sub setset {
  local($set) = shift;
  local($i, $val, $n);

  while (@_) {
    ($i, $val) = splice(@_, 0, 2);
    $n = length($set);
    substr($set, $n) = '0' x ($i - $n) if ($i > $n);
    substr($set, $i, 1) = $val ? '1' : '0';
  }
  $set;
}

sub setunion {
  local($set, $n) = shift;

  foreach (@_) {
    $n = length($_);
    substr($set, 0, $n) = substr($set, 0, $n) | $_;
  }
  $set;
}

sub setintersection {
  local($set, $n) = shift;

  foreach (@_) {
    $n = length($_);
    substr($set, 0, $n) = substr((substr($set, 0, $n) & $_) . '0' x $n, 0, $n);
  }
  $set;
}

sub setcomplement {
  local($sub, $n) = @_;

  $n = length($sub) if (!defined($n));
  $sub =~ tr/01/10/;
  substr($sub . '0' x $n, 0, $n);
}

sub setminus {
  local($set, $n) = shift;

  foreach (@_) {
    $n = length($_);
    substr($set, 0, $n) = substr((substr($set, 0, $n) & &setcomplement($_)) . '0' x $n, 0, $n);
  }
  $set;
}

sub setno {
  local($sum, @sum);

  foreach (@_) {
    @sum = /(1)/g;
    $sum += @sum;
  }
  $sum;
}

sub partitions {
  local($sum, $nmax, $nmin, $max) = @_;

  $nmax = $sum if (!defined($nmax));
  $nmin = 1 if (!defined($nmin));
  $max = $sum - $nmin + 1 if (!defined($max));
  &partitions_loop($sum, $nmax, $nmin, $max);
}

sub partitions_loop {
  local($sum, $nmax, $nmin, $max, @partition) = @_;
  local(@new);

  if ($nmax > 0 && $sum > 0) {
    local($min, $xmax) = ($sum / $nmax--, $sum - ($nmin > 0 ? --$nmin : 0));
    
    $max = $xmax if ($max > $xmax);
    for (; $max >= $min ; --$max) {
      push(@new, &partitions_loop($sum - $max, $nmax, $nmin, $max, @partition, $max));
    }
  }
  elsif ($sum <= 0 && $nmin <= 0) {
    @new = ([@partition]);
  }
  @new;
}

sub partition_rectangles {
  local(@ns);

  if (@_) {
    local($prev, $i, $n);

    $prev = $_[0];
    for ($i = $n = 1 ; $i < @_ ; ++$i, ++$n) {
      if ($_[$i] != $prev) {
	push(@ns, $n);
	$n = 0;
	$prev = $_[$i];
      }
    }
    push(@ns, $n) if ($n > 0);
  }
  @ns;
}

@permvv = ([['0']]);

sub permutations {
  if ($_[0] > @permvv) {
    local($i) = $_[0] - 1;
    local($j, $k, $old, @new, @perm);

    &permutations($i) if ($i > @permvv);
    foreach ($j = 0 ; $j < $i ; ++$j) {
      foreach (@{$permvv[$j]}) {
	@perm = (@$_, $j + 1 .. $i);
	for ($k = $i ; $k > 0 ;) {
	  --$k;
	  push(@new, [@perm[0 .. $k - 1], $i, @perm[$k .. $i - 1]]);
	}
      }
    }
    push(@permvv, [@new]);
  }
}

sub apply_permutation {
  local($perm, $set) = @_;

  join('', (split(//, $set, @$perm))[@$perm, @$perm .. length($set) - 1]);
}

sub permutations_leave_partition {
  local($part, @temp) = @_;

  if (@temp < @$part) {
    local($i, @perms);

    for ($i = $$part[@temp] ; $i > 0 ;) {
      &permutations($i);
      foreach (@{$permvv[--$i]}) {
	push(@perms, &permutations_leave_partition($part, @temp, $_));
      }
    }
    @perms;
  }
  else {
    local(@perm, $perm);

    foreach (@$part) {
      $perm = shift(@temp);
      push(@perm, @$perm, @$perm .. $_);
    }
    ([@perm]);
  }
}

1;