Subj : Re: Unique sets from {1..n} ?
To   : comp.programming
From : TC
Date : Mon Jul 11 2005 12:55 am


Willem wrote:
> TC wrote:
> ) Hi Willem
> )
> ) I am aware of the pattern! It was just the algorithym that defeated me.
> ) And I had not thought of using the bit pattern to select the items. I'm
> ) currently using that approach:
> )
> ) for k = 1 to n
> )    for j=1 to 32(or whatever)
> )        if bit j=1, add item #j to set #k
>
> The two variables (j and k) don't loop to the right amounts.
> This algorithm won't work as such.
> (Except for a very specific value for n, which I doubt you had in mind.)


Um, the two variables /do/ loop to the right amounts and the algorithym
will and does work exactly as shown (with a clarification noted below).

All it assumes is that the counter k is implemented as a 32-bit
unsigned integer, and that n is constrained to the corresponding
maximum value. If not (ie. k is signed, and/or some other bit size, or
n exceeds 2 to the bitsize of k), adjust the 32 accordingly. That's why
I said: "(or whatever)".

The only language missing from the algortithm, is to add the words: "of
the binary implementation of the value k", after the words "if bit j".
Fairly obvious, methinks. There's no value /other than/ k, that you
would be testing the bits of, in that algorithym.

HTH,
TC

.