BitSubsetIterator - Feedback?



  • Auch das war ein Flüchtigkeitsfehler. Ich sollte meine Beiträge genauer probelesen. Also die Nullen bleiben, sonst wären das ja auch keine Untermengen der Ursprungszahl.



  • bei einer gegebenen Zahl alle Untermengen durchläuft.

    Was sind die Untermengen einer Zahl?

    Bitfolge 11100 habe, soll er mir 11100 ausgeben, danach 11000, 10100, 01100 ausgeben und daraufhin 10000, 01000, 00100.

    Sind das alle oder warum darf keine 1 in die letzten beiden Bit.



  • Na ja, war mir klar, dass das so formuliert falsch ist, aber ich dachte, das reicht zum Verständnis sinngemäß aus.

    Betrachtet man eine Zahl als eine Kombination von Bits, könnte man sie als Menge schreiben der Form:
    {BIT1, BIT2, BIT5} für 10011

    Hier von möchte ich alle Untermengen, die also entsprechend wären:
    {BIT1, BIT2} für 00011, {BIT1, BIT5} für 10001, {BIT2, BIT5} für 10010. Das nenne ich hier Level1, während Level2 ein zweites Bit abzieht, was sich somit darin äußert, dass nur ein Bit auf Level2 gesetzt ist.

    Tatsächliche Ausgabe ist eine Zahl, die der entsprechenden Verknüpfung genannter Bits entspricht.

    Sind das alle oder warum darf keine 1 in die letzten beiden Bit.

    Ja, das sind alle. Die 1 darf nicht in das letzte Bit, weil diese Bits in der Ausgangszahl nicht besetzt sind und die Zahl somit nach obiger Repräsentation/Interpretation keine Obermenge einer Zahl wie 00010 darstellt. Nochmal: mir ist bewusst, dass eine Zahl keine (nicht-triviale? ich bin kein Mathematiker) Menge ist, das wollte ich einfach nur zur Veranschaulichung nutzen.

    Man könnte auch sagen, ich suche alle x bei gegebenem y, sodass gilt: x BIT_AND y = x



  • Du willst durch die Potenzmenge iterieren. D.h. 110010 -> {1,2,5}. Weglassen bei Level 0: {}, Level 1: {1}, {2}, {5}, Level 2: {1,2}, {1,5}, {2, 5}, Level 3: {1,2,3}. Algorithmen zum erzeugen der Potenzmenge sollten beim iterieren helfen. Auch sind die Stellen mit 0 irrelevant, D.h. man kann von 111 ausgehen und beim generieren der Zahlen auf die Position mappen.

    Suche dir eine Version heraus, die deine Ordnung (Levels) erzeugt: http://rosettacode.org/wiki/Power_set , beispielsweise kann man vielleicht in Clojure's subset Funktion nachsehen. Oder hier: http://www.martinbroadhurst.com/combinatorial-algorithms.html#power-set , wo ein Ansatz ohne Container angerissen wird.

    Gegenfrage: Wofuer brauchst du das?



  • Super, vielen Dank. 🙂

    Brauchen tue ich das mittlerweile nicht mehr. Es handelt sich um viele Flags, die mit Strings versehen werden. Kombiniert man Flags, erhält man jedoch u.U. andere Strings als String1 + String2. Es ist jedoch viel zweckdienlicher einfach die Strings mit ihren Bitkombinationen nach Anzahl der Bits zu sortieren und darüber zu iterieren. Die Potenzmenge ist einfach viel zu groß.

    Aber ich wollte eben üben Mal einen Iterator zu schreiben.

    Danke und beste Grüße, die Algorithmen für Potenzmengen schaue ich mir dennoch an!

    Beste Grüße,
    Eisflamme



  • Wenn Deine Reihenfolge nicht so komisch sein müßte, hätte ich was recht leckeres.

    Maske:
    111010
    
    Ausgabe:
    111010
    111000
    110010
    110000
    101010
    101000
    100010
    100000
    11010
    11000
    10010
    10000
    1010
    1000
    10
    
    #include <iostream>
    
    class BitSubsetGenerator{
        uint32_t bits;
        uint32_t mask;
    public:
        BitSubsetGenerator(uint32_t bits)
        :bits(0)
        ,mask(bits){
        }
        uint32_t peek(){
            return bits^mask;
        }
        void pop(){
            bits=((bits|~mask)+1)&mask;
        }
        bool isEmpty(){
            return bits==mask;
        }
    };
    
    struct bin{
        uint32_t n;
        explicit bin(uint32_t n)
        :n(n){
        }
        friend std::ostream& operator<<(std::ostream& out,bin b){
            if(b.n>=2)
                out<<bin(b.n/2);
            return out<<char('0'+b.n%2);
        }
    };
    
    int main(){
       BitSubsetGenerator bsg(58);
       std::cout<<bin(58)<<'\n'<<'\n';
       while(!bsg.isEmpty()){
            std::cout<<bin(bsg.peek())<<'\n';
            bsg.pop();
       }
    }
    


  • Ja, muss halt Level-Order sein, weil 111 ja einen anderen Namen haben kann als string(110) + string(001).

    Sonst aber echt super. Wie kommt man auf so was? Bin das schrittweise durchgegangen und sehe, dass es klappt, aber verstehen tue ich's nicht.



  • Eisflamme schrieb:

    Ja, muss halt Level-Order sein, weil 111 ja einen anderen Namen haben kann als string(110) + string(001).

    Sonst aber echt super. Wie kommt man auf so was? Bin das schrittweise durchgegangen und sehe, dass es klappt, aber verstehen tue ich's nicht.

    Der Trick ist ganz einfach.

    Grundmenge sei mal:
    111000110010001100

    bits sei irgendwann
    ???000??00?000??00

    Jetzt will ich dafür sorgen, daß ich wenn ich das rechte Fragezeichen umklappe, daß dann wenn es von 0 nach 1 umklappt, war alles gut, aber wenn es von 1 nach 0 umklappt, soll es seinen linken Nachbarn umklappen. Also ganz normales binäres addieren. Klappt der linke Nachbar um von 1 nach 0, soll er wiederum seinen linken Nachbarn mitnehmen, nur daß der jetzt drei Stellen weiter links ist.
    Und das geht ganz einfach, ich baue eine Hühnerleiter aus zwangsgesetzten Bits!!!
    ???000??00?000??00
    Dann setze ich die inverse Grundmenge rein
    ???111??11?111??11
    Jetzt kann ich einfach das ganz rechte Bit mit +1 klappen und falls ein Überlauf von einem ? in eine Hühnerleiter reinfällt, trägt die Hühnerleiter ihn sicher auch wieder hinaus ins nächste ?.

    Damit ist
    bits=((bits|~mask)+1)&mask
    erklärt.

    Jo, und die bits lasse ich bei 0 beginnen und bei Vollsein enden. Wegen +1 war das praktisch. Es hat nur mit +1 funktioniert, mit -1 nicht. Voll doof! Darum laufe ich aufwärts, und deswegen geschieht mit
    return bits^mask
    die Anzeige rückwärts.

    ➡ 💡
    Haha, wie doof war das denn? Natürlich geht -1 auch. Dazu muss nur die Hühnerleiter aus 0-en bestehen. Das führt zu deutlich verbessertem Code.

    class BitSubsetGenerator{
        uint32_t bits;
        uint32_t mask;
    public:
        BitSubsetGenerator(uint32_t bits)
        :bits(bits)
        ,mask(bits){
        }
        uint32_t peek(){
            return bits;
        }
        void pop(){
            bits=(bits-1)&mask;
        }
        bool isEmpty(){
            return bits==0;
        }
    };
    

    Jo, da sehe ich jetzt nicht mehr viel Spielraum für Verbesserungen. 🤡



  • Volkard unser Bitfriemler ❤

    Danke für dies Lehrstunde.



  • Okay, super, vielen Dank 🙂

    Ich hätte jetzt noch iterator-bezogene Fragen:
    - Findet ihr einen Iterator hier sinnvoll? (die anderen Fragen sind dennoch weiter interessant :))
    - Braucht ein Iterator unbedingt mehr Operatoren? Würdet ihr euch welche wünschen?
    - Habe ich etwas misdesigned, sodass der Iterator gar nicht als Input-Iterator überall brav funktioniert?
    - Wie würdet ihr die "atEnd"-Problematik lösen? Meine Kristallkugel sagt mir, anders.

    Wenn ihr dazu auch noch Infos hätte, wäre auch dieser Tag gerettet. 🙂



  • Eisflamme schrieb:

    - Wie würdet ihr die "atEnd"-Problematik lösen? Meine Kristallkugel sagt mir, anders.

    Ich weiß nicht, was Dein atEnd() macht, ex wäre nett gewesen, ein ganzes Programm zu posten incl main(). Falls Du wolltest, daß man aus der main() das atEnd aufruft, dann ist es unhübsch.
    Eigentlich ist es eine range oder ein Generator.
    Was als InputIterator rein muss, steht eigentlich da: http://en.cppreference.com/w/cpp/concept/InputIterator

    Mal ein paar ganz wirre Gedanken dazu, streich die 95%, die Mist sind und nimm, falls ein guter Gedanke drin ist, den auf.

    Eine steinharte Lösung, wenn man sich nur auf atEnd() stützen kann, wäre

    #include <iostream>
    #include <cassert>
    
    class BitSubsetIterator{
        uint32_t bits;
        uint32_t mask;
        bool ended;
    public:
        BitSubsetIterator(){
            ended=true;
        }
        explicit BitSubsetIterator(uint32_t bits)
        :bits(bits)
        ,mask(bits){
            ended=false;
        }
        uint32_t operator*(){
            return bits;
        }
        BitSubsetIterator operator++(){
            bits=(bits-1)&mask;
            if(atEnd())
                ended=true;
            return *this;
        }
        bool atEnd(){
            return bits==0;
        }
        friend bool operator==(BitSubsetIterator a,BitSubsetIterator b){
            if(a.ended==b.ended)
                return true;
            if(a.ended!=b.ended)
                return false;
            return a.bits==b.bits;
        }
        friend bool operator!=(BitSubsetIterator a,BitSubsetIterator b){
            return !(a==b);
        }
    };
    
    struct bin{
        uint32_t n;
        explicit bin(uint32_t n)
        :n(n){
        }
        friend std::ostream& operator<<(std::ostream& out,bin b){
            if(b.n>=2)
                out<<bin(b.n/2);
            return out<<char('0'+b.n%2);
        }
    };
    
    int main(){
       for(BitSubsetIterator i=BitSubsetIterator(58),end;i!=end;++i)
            std::cout<<bin(*i)<<'\n';
    }
    

    Manchmal hebe ich ein globales end-Objekt aus.

    #include <iostream>
    #include <cassert>
    
    class BitSubset{
        public:
        uint32_t bits;
        BitSubset(uint32_t bits)
        :bits(bits){
        }
        class iterator{
            uint32_t bits;
            uint32_t mask;
            iterator(){//only fpr the End
            }
            friend class BitSubset;
        public:
            explicit iterator(uint32_t bits)
            :bits(bits)
            ,mask(bits){
            }
            uint32_t operator*(){
                return bits;
            }
            iterator operator++(){
                bits=(bits-1)&mask;
                return *this;
            }
            bool atEnd(){
                return bits==0;
            }
            static iterator theEnd;
            friend bool operator==(iterator a,iterator b){
                if(&b==&theEnd)
                    return a.atEnd();
                if(&a==&theEnd)
                    return b.atEnd();
                return a.bits==b.bits;
            }
            friend bool operator!=(iterator a,iterator b){
                return !(a==b);
            }
        };
        iterator begin(){
            return iterator(bits);
        }
        iterator end(){
            return iterator::theEnd;
        }
    };
    BitSubset::iterator BitSubset::iterator::theEnd;
    
    struct bin{
        uint32_t n;
        explicit bin(uint32_t n)
        :n(n){
        }
        friend std::ostream& operator<<(std::ostream& out,bin b){
            if(b.n>=2)
                out<<bin(b.n/2);
            return out<<char('0'+b.n%2);
        }
    };
    
    int main(){
        BitSubset bs(58);
       for(BitSubset::iterator i=bs.begin();i!=bs.end();++i)
            std::cout<<bin(*i)<<'\n';
    }
    

    Aber wenn irgend möglich. nicht so prüfen, sondern das end-Objekt so gestalten, daß mit einem evtl leicht modifizierten op== der Vergleich klappt. Hier gehts gerade mal leicht, Glück gehabt.

    #include <iostream>
    #include <cassert>
    
    class BitSubset{
        public:
        uint32_t bits;
        BitSubset(uint32_t bits)
        :bits(bits){
        }
        class iterator{
            uint32_t bits;
            uint32_t mask;
            iterator()
            :bits(0){//only fpr the End
            }
            friend class BitSubset;
        public:
            explicit iterator(uint32_t bits)
            :bits(bits)
            ,mask(bits){
            }
            uint32_t operator*(){
                return bits;
            }
            iterator operator++(){
                bits=(bits-1)&mask;
                return *this;
            }
            static iterator theEnd;
            friend bool operator==(iterator a,iterator b){
                return a.bits==b.bits;
            }
            friend bool operator!=(iterator a,iterator b){
                return !(a==b);
            }
        };
        iterator begin(){
            return iterator(bits);
        }
        iterator end(){
            return iterator::theEnd;
        }
    };
    BitSubset::iterator BitSubset::iterator::theEnd;
    
    struct bin{
        uint32_t n;
        explicit bin(uint32_t n)
        :n(n){
        }
        friend std::ostream& operator<<(std::ostream& out,bin b){
            if(b.n>=2)
                out<<bin(b.n/2);
            return out<<char('0'+b.n%2);
        }
    };
    
    int main(){
        BitSubset bs(58);
       for(BitSubset::iterator i=bs.begin();i!=bs.end();++i)
            std::cout<<bin(*i)<<'\n';
    }
    

    Und bettelt darum, wieder rückgebaut zu werden.

    #include <iostream>
    #include <cassert>
    
    class BitSubset{
        public:
        uint32_t bits;
        BitSubset(uint32_t bits)
        :bits(bits){
        }
        class iterator{
            uint32_t bits;
            uint32_t mask;
        public:
            iterator()
            :bits(0){//only fpr the End
            }
            explicit iterator(uint32_t bits)
            :bits(bits)
            ,mask(bits){
            }
            uint32_t operator*(){
                return bits;
            }
            iterator operator++(){
                bits=(bits-1)&mask;
                return *this;
            }
            friend bool operator==(iterator a,iterator b){
                return a.bits==b.bits;
            }
            friend bool operator!=(iterator a,iterator b){
                return !(a==b);
            }
        };
        iterator begin(){
            return iterator(bits);
        }
        static iterator end(){
            return iterator();
        }
    };
    
    struct bin{
        uint32_t n;
        explicit bin(uint32_t n)
        :n(n){
        }
        friend std::ostream& operator<<(std::ostream& out,bin b){
            if(b.n>=2)
                out<<bin(b.n/2);
            return out<<char('0'+b.n%2);
        }
    };
    
    int main(){
        BitSubset bs(58);
        for(BitSubset::iterator i=bs.begin();i!=bs.end();++i)
            std::cout<<bin(*i)<<'\n';
    }
    

    Oft halten meine Iteratoren eine Referenz auf den Container.

    #include <iostream>
    #include <cassert>
    
    class BitSubset{
        public:
        uint32_t bits;
        BitSubset(uint32_t bits)
        :bits(bits){
        }
        class iterator{
            uint32_t bits;
            BitSubset& subset;
        public:
            explicit iterator(uint32_t bits,BitSubset& subset)
            :bits(bits)
            ,subset(subset){
            }
            uint32_t operator*(){
                return bits;
            }
            iterator& operator++(){//uups, die ganze Zeit das & vergessen
                bits=(bits-1)&subset.bits;
                return *this;
            }
            friend bool operator==(iterator a,iterator b){
                assert(&a.subset==&b.subset);//Hier frue ich mich immer, zugegeben, paranoid. :)
                return a.bits==b.bits;
            }
            friend bool operator!=(iterator a,iterator b){
                return !(a==b);
            }
        };
        iterator begin(){
            return iterator(bits,*this);//Ja, hier wandert regelmäßig auch 
        }
        iterator end(){
            return iterator(0,*this);//ein wenig Iteratorlogik hon. 
        }
    };
    
    struct bin{
        uint32_t n;
        explicit bin(uint32_t n)
        :n(n){
        }
        friend std::ostream& operator<<(std::ostream& out,bin b){
            if(b.n>=2)
                out<<bin(b.n/2);
            return out<<char('0'+b.n%2);
        }
    };
    
    int main(){
        for(auto i:BitSubset(58))
            std::cout<<bin(i)<<'\n';
    }
    


  • Ja, ist bei mir dann unhübsch. 🙂

    Und danke für die Codes! Also ergibt es Sinn eine Klasse drum herum zu basteln und den Iterator nicht einfach für sich stehen zu lassen. Gefällt mir. 🙂 Den Zeiger auf den Container hältst Du nur wegen dem assert (nicht, dass ich das nicht auch sinnvoll fände)?



  • Eisflamme schrieb:

    Ja, ist bei mir dann unhübsch. 🙂

    Und danke für die Codes! Also ergibt es Sinn eine Klasse drum herum zu basteln und den Iterator nicht einfach für sich stehen zu lassen.

    Also die main() finde ich so hübscher.

    Eisflamme schrieb:

    Den Zeiger auf den Container hältst Du nur wegen dem assert (nicht, dass ich das nicht auch sinnvoll fände)?

    Nee, das ist nur ein kostenloses Bonbon, wenn ich mich wegen anderer Gründe entscheide, eine Referenz auf den Container zu halten, nämlich wenn der Iterator zu viele Informationen kennen müßte, die der Container eh auch kennt, wenn der Iterator zu schwer werden würde, zu viele Status-Variablen, langsames Kopieren. Oder gar die vollkommene Unmöglichkeit von einem Kind zum nächsten zu springen, ohne den Container zu sehen, ein Iterator über eine Hashtable wäre so ein Fall, keine Zelle weiß, wo die nächste ist, sondern nur den Container selbst könnte es verraten. Wollte das Container-Kennen nur der Vollständigkeit halber nennen, manchmal brauche ist es.


Anmelden zum Antworten