in reply to Re: Algorithm to convert combinations to bitstring
in thread Algorithm to convert combinations to bitstring

spx2,
Would you mind coding up a complete example? I ask because I haven't used Bit::Vector that much and don't immediately see how it could be used to accomplish this task. I solved this problem a long time ago but am always interested in seeing how abstraction modules can make my life easier.

Keep in mind that the goal would be to have a known set ( say 'A' .. 'Z') and a known subset size (say 5). Then, given a valid subset of the specified size (say AMTXZ), determine if that subset has been "seen" before. If not, perform some action and then mark it as being "seen". Here is some starter code to give you an idea of what I have already accomplished: 

my @set = 'A' .. 'Z';
my $subset_size = 5;
my @subset = qw/A M T X Z/;

process_subset(@subset);
process_subset(@subset);

sub process_subset {
    if (seen(@_)) {
        print "Already processed '@_'\n";
        return;
    }
    print "Performing expensive operation on '@_'\n";
    set_seen(@_);
}

sub seen {
    # For you to implement
    # ...
}

sub set_seen {
    # For you to implement
    # ...
}

[download]

Keep in mind that @set, @subset_size and @subset are all subject to change - so it has to be a general purpose solution.

Cheers - L~R

Replies are listed 'Best First'.
Re^3: Algorithm to convert combinations to bitstring
by spx2 (Deacon) on Jan 01, 2010 at 06:50 UTC
    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]
[reply]
[d/l]
[select]
      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]
        ok you're right :) how did you solve the problem ?
[reply]

In Section Seekers of Perl Wisdom