Author: Gerd Isenberg
Date: 10:36:52 02/27/06
Hi,
while i indulge my current morbus knuth attack, which hits me so one, two times
a year, i like to ask a question related to the "rotated" De Bruijn generator.
I have a word "d" with a setwise interpretation ( a bitboard) and maximum
cardinality of N (N bits set, let say 8). I like to enumerate all subsets,
including the empty set and the original complete set. Looking for a smarter
algorithm.
What i actually do is to isolate all bits and store them in an array:
Bitboard d = ..., t, bit[N];
// d is the set i like traverse all subsets
for (int n=0, t=d; t; n++) {
assert(n<N);
bit[n] = t & -t; // lsb
t &= t-1; // reset lsb
}
Now i loop over all 2**n (1<<n) possible combinations and synthesize the
subsets inside an inner loop.
for (int i=0; i < 1<<n; i++) {
// and build subset(i) with a loop
// combining all saved bits according to the
// the bits set in i
for (ont j=0, t=0; j < n; j++) {
if ( i & (1<<j) ) t |= bit[j];
}
// here t is one subset if d
...
}
I guess there is a much smarter approach - without storing the isolated bits as
atomic subsets - and doing a loop to synthesize the subsets.
Hints and suggestions appreciated.
Thanks,
Gerd
This page took 0.02 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.