Author: Dann Corbit
Date: 12:26:06 02/27/06
Go up one level in this thread
On February 27, 2006 at 13:36:52, Gerd Isenberg wrote:
>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.
Here is a Fortran subset algorithm by Nijenhuis and Wilf:
c-----------------------------------------------------------
c Chapter 1: Next subset of an n-set(p19)
c-----------------------------------------------------------
c Name of Subroutine: NEXSUB
c
c Algorithm:Generating all of the subsets of the set
c {1,2,...,n} in an order specified by the
c gray code
c
c input: n=5
c compiler: f77 nexsub_2.f
c-----------------------------------------------------------
c Use of nexsub
logical mtc
dimension in(5)
n=5
mtc=.false.
10 call nexsub(n,in,mtc,ncard,j)
print 20,(in(i),i=1,n)
20 format(1x ,5(i2,1x))
if(mtc) goto 10
stop
end
c-----Subroutine begins here--------------------------------
subroutine nexsub(n,in,mtc,ncard,j)
logical mtc
dimension in(n)
if(mtc)goto 20
do 11 i=1,n
11 in(i)=0
ncard=0
mtc=.true.
return
20 j=1
if(mod(ncard,2).eq.0)goto 30
40 j=j+1
if(in(j-1).eq.0)goto 40
c if(j.gt.n)j=n
30 in(j)=1-in(j)
ncard=ncard+2*in(j)-1
mtc=ncard.ne.in(n)
return
end
Crude modification of f2c output of the combination subroutine part (less the
driver):
/* -----Subroutine begins here-------------------------------- */
int nexsub(int * n, int * in, logical * mtc, int *ncard, int * j)
{
/* System generated locals */
int i1;
/* Local variables */
static int i;
/* Parameter adjustments */
--in;
/* Function Body */
if (*mtc) {
goto L20;
}
i1 = *n;
for (i = 1; i <= i1; ++i) {
in[i] = 0;
}
*ncard = 0;
*mtc = TRUE;
return 0;
L20:
*j = 1;
if (*ncard % 2 == 0) {
goto L30;
}
L40:
++(*j);
if (in[*j - 1] == 0) {
goto L40;
}
/* if(j.gt.n)j=n */
L30:
in[*j] = 1 - in[*j];
*ncard = *ncard + (in[*j] << 1) - 1;
*mtc = *ncard != in[*n];
return 0;
}
It could easily be made structured. Also, some of the pass by pointer calls
could easily be made pass by value. I would also make the static permuation
holder a parameter.
This page took 0 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.