Author: Gerd Isenberg
Date: 13:57:53 02/27/06
Go up one level in this thread
On February 27, 2006 at 16:42:13, F. Huber wrote:
>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.
>>
>>Thanks,
>>Gerd
>
>Hallo Gerd,
>
>ich hoffe ich hab das hier richtig verstanden, daß Du von einer beliebigen
>Bit-Folge/Menge alle Teil-Folgen/Mengen brauchst (also praktisch das, was die
>Mathematik ´Potenzmenge´ nennt). (?)
>
>Da ich vor kurzem mal ein Kombinatorik-Programm geschrieben habe, das unter
>anderem auch Kombinationen berechnet, läßt sich das natürlich recht einfach
>auch auf die Potenzmenge erweitern.
>Ich hab dieses Programm mal schnell komplett reduziert auf genau jene Aufgabe,
>die Du anscheinend brauchst - vielleicht kannst Du ja etwas damit anfangen.
>Es ist zwar in Pascal geschrieben, und außerdem für Strings (als Eingabe)
>ausgelegt, aber das sollte sich recht einfach auf ´C´ (und auf Bitfolgen statt
>Strings) umschreiben lassen.
>Außerdem ist es recht kurz, weil der Hauptteil (nämlich die Berechnung der
>Kombinationen) als rekursive Prozedur realisiert ist - das hat mich damals
>einiges Nachdenken gekostet. ;-)
>
>Falls Du´s brauchen kannst, freut es mich - wenn nicht, dann ist´s auch ok. ;-)
>
>Grüße,
>Franz.
>
>----------------------------------------------------
>
>program SubSets;
>
>procedure comb_rec(in_str,out_str:string;k:integer);
>var i,n:integer;
> c:char;
> s:string;
>begin
> if k=0 then writeln(out_str)
> else
> begin
> n:=length(in_str);
> for i:=1 to n do
> begin
> c:=in_str[i];
> s:=copy(in_str,i+1,n-i);
> comb_rec(s,out_str+c,k-1);
> end;
> end;
>end;
>
>var s:string;
> k,i:integer;
>
>begin
> s:=paramstr(1);
> k:=length(s);
> for i:=0 to k do comb_rec(s,'',i);
>end.
>
>----------------------------------------------------
Hallo Franz,
ja genau die Potenzmenge.
Sehr nett, danke für deinen Algorithmus - werde ich mir bei Gelegenheit mal
genauer anschauen. Für binäre "Strings" in From von 64-Bit Worten ist Steffans
Ansatz genau das was ich brauche - glaub kaum das da was schneller geht ;-)
Gruss,
Gerd
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.