lib/bitvector/t/06_____subset.t

   1 #!perl -w
   2
   3 use strict;
   4 no strict "vars";
   5
   6 use Bit::Vector;
   7
   8 # ======================================================================
   9 #   $set1->subset($set2);
  10 # ======================================================================
  11
  12 $bits = 6;
  13
  14 print "1..$bits\n";
  15
  16 $n = 1;
  17 for ( $b = 1; $b <= $bits; ++$b )
  18 {
  19
  20     $set1 = new Bit::Vector($b);
  21     $set2 = new Bit::Vector($b);
  22
  23     $c1 = 0;
  24     $c2 = 0;
  25
  26     for ( $k = 0; $k <= $b; ++$k )
  27     {
  28         $c1 += (1<<$k) * &binomial($b,$k);
  29     }
  30
  31     for ( $i = 0; $i < (1<<$b); ++$i )
  32     {
  33         $c = $i;
  34         for ( $k = 0; $k < $b; ++$k )
  35         {
  36             if ($c & 1) { $set1->Bit_On($k); } else { $set1->Bit_Off($k); }
  37             $c >>= 1;
  38         }
  39         for ( $j = 0; $j < (1<<$b); ++$j )
  40         {
  41             $c = $j;
  42             for ( $k = 0; $k < $b; ++$k )
  43             {
  44                 if ($c & 1) { $set2->Bit_On($k); } else { $set2->Bit_Off($k); }
  45                 $c >>= 1;
  46             }
  47             if ($set1->subset($set2)) { ++$c2; }
  48         }
  49     }
  50
  51     if ($c1 == $c2)
  52     {print "ok $n\n";} else {print "not ok $n\n";}
  53     $n++;
  54 }
  55
  56 exit;
  57
  58 sub binomial
  59 {
  60     my($n,$k) = @_;
  61     my($prod) = 1;
  62     my($j) = 0;
  63
  64     if (($n <= 0) || ($k <= 0) || ($n <= $k)) { return(1); }
  65     if ($k > $n - $k) { $k = $n - $k; }
  66     while ($j < $k)
  67     {
  68         $prod *= $n--;
  69         $prod /= ++$j;
  70     }
  71     return(int($prod + 0.5));
  72 }
  73
  74 __END__
  75