Re^3: Algorithm to convert combinations to bitstring

Hi L~R,

  1 use List::AllUtils qw/sum/;
  2 use Bit::Vector;
  3 
  4 my $k = 2;
  5 
  6 my @letters = split '',"ABCDE";
  7 my $n = scalar(@letters);
  8 
  9 my $vec = Bit::Vector->new($n);
 10 
 11 while(!$vec->increment){
 12     my $i = $vec->to_Bin; # current bitstring
 13     my $s = sum(split '',$i); # sum up to find out how many bits a
+re lit
 14 
 15     next unless ($s == $k); # just the ones with $k bits lit
 16 
 17 
 18     my $str = # convert bitstring to string
 19         join '',
 20         map { $letters[$_]  }
 21         grep { $vec->contains($_);  }
 22         0..$n-1 ;
 23 
 24     print "$s $i $str\n";
 25 };
[download]

The seen and set_seen routines are incorporated in the check at line 15.

The output for this is:

2 00011 AB
2 00101 AC
2 00110 BC
2 01001 AD
2 01010 BD
2 01100 CD
2 10001 AE
2 10010 BE
2 10100 CE
2 11000 DE
[download]

Comment on Re^3: Algorithm to convert combinations to bitstring Select or Download Code

Replies are listed 'Best First'.
Re^4: Algorithm to convert combinations to bitstring by Limbic~Region (Chancellor) on Jan 01, 2010 at 19:49 UTC
spx2, This doesn't meet the requirements. Since this thread is several years old, let me explain again what I was trying to accomplish. You have a function that will perform an expensive operation the first time it is passed a unique argument list but is free to short circuit and return early if it has been called with the same arguments again. This is typically accomplished using a %seen hash or the Memoize module. Unfortunately, the number of possible argument variations is too large to use standard tools - hence the desire to use a bit string. In my case, the arguments will always be a subset of a known set and they will always be a fixed size. On the other hand, we are not generating them - they will be passed to us. We need to convert the subset into an integer and either set that single bit if not already set and perform the expensive operation or return if already set. In summary, if we are doing N Choose K with K = 13 and N = 26 then there are 10,400,600 total possible combinations. This means our seen should be exactly 1,300,075 bytes (1 bit representing each possible combination). If your solution requires more memory than that or is not able to take an arbitrary subset and convert it into an integer to see if the bit is set or not then it doesn't meet the requirements. Cheers - L~R	[reply]
Re^5: Algorithm to convert combinations to bitstring by spx2 (Deacon) on Jan 10, 2010 at 14:57 UTC
ok you're right :) how did you solve the problem ?	[reply]
Re^6: Algorithm to convert combinations to bitstring by Limbic~Region (Chancellor) on Jan 10, 2010 at 15:26 UTC
spx2, See How many words does it take?. If I remember correctly, I modified blokhead's solution to Java. Since I was dealing with a powerset, I had 26 bitstrings - 1 for each possible length of string. Cheers - L~R	[reply]