Author: F. Huber
Date: 13:42:13 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.
>
>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.
----------------------------------------------------
This page took 0.01 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.