math is hard (to remember)

Randal L. Schwartz merlyn at stonehenge.com
Fri Jul 13 15:41:56 CDT 2001


~sdpm~
>>>>> "cabney" == cabney  <cabney at cyberpass.net> writes:

cabney> On 12 Jul 2001, Randal L. Schwartz wrote:
>> my @list = qw(red orange yellow green blue purple);
>> for (my $i = 1; $i < 1 << @list; $i++) {
>> my $bits = unpack "B*", pack "N", $i;
>> my @out = grep $bits =~ s/(.)$// && $1, @list;
>> print "$i = @out\n";
>> }
>> 
>> Works up to 32 items.  More requires a nicer bit-increment algorithm,
>> but when are you going to do this with 32 items or more? :)

cabney> while the count is -lt 2**N,
cabney> 	get a string representative of the count's value in binary format.
cabney> 	for each value in @list
cabney> 		knock off the last "bit" from the bit string
cabney> 			if this succeeds (it goes through the /entire/ bitstring?)
cabney> 				the "bit" is the return value for the grep
cabney> 				push out the current @list value if return is "true"
cabney> 	print the count and @out.

cabney> If this goes through the whole bitstring, could you get a significant
cabney> optimization removing zero's from the high end?

No, it only removes bits from the right end for as many items as there
are in the list.  No savings there.  And the "unpack" is fast, because
the integer is already bit-ish.  I doubt you'd find a much faster
algorithm.

-- 
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<merlyn at stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
~sdpm~

The posting address is: san-diego-pm-list at hfb.pm.org

List requests should be sent to: majordomo at hfb.pm.org

If you ever want to remove yourself from this mailing list,
you can send mail to <majordomo at happyfunball.pm.org> with the following
command in the body of your email message:

    unsubscribe san-diego-pm-list

If you ever need to get in contact with the owner of the list,
(if you have trouble unsubscribing, or have questions about the
list itself) send email to <owner-san-diego-pm-list at happyfunball.pm.org> .
This is the general rule for most mailing lists when you need
to contact a human.




More information about the San-Diego-pm mailing list