Schnelle Auswahl n aus m (Kombinationen ohne Zurücklegen) gesucht



  • Ich habe häufig den Fall, dass ich aus einem Array mit m Einträgen n unterschiedliche zufällig heraussuchen muss. Bisher mache ich das ungefähr so:

    memset(taken,0,m*sizeof(unsigned char));
    for(i=0;i<n;++i)
    {
       do
       {
          index = rand(m);
       } while(taken[index]);
       taken[index] = 1;
       ... mach was mit index ...
    }
    

    Das läuft leider um so langsamer, je näher n an m ist, und je mehr Einträge schon benutzt wurden, weil in der do-Schleife immer mehr taken-Einträge mit 1 erwischt werden.
    Gibt es dafür eine schnellere Methode?



  • Ab n=m/2 könntest du den Ansatz ja umkehren - du wählst dir m-n Objekte aus deinem Haufen aus und verarbeitest dann alle übrigen.

    Alternativ kannst du auch die ausgewählten Elemente aus der Liste rausschmeißen, so daß du immer nur über "neue" Elemente suchen mußt.

    PS: sizeof(char) == 1 😉



  • ein array mit den möglichen indizes. damit kannste dann allerhand machen. zum beispiel verwürfeln und die ersten n draus nehmen.



  • volkard schrieb:

    ein array mit den möglichen indizes. damit kannste dann allerhand machen. zum beispiel verwürfeln und die ersten n draus nehmen.

    Das ist ne gute Idee - da denke ich mal weiter drüber nach! Thx! 👍

    EDIT: Hier ein Codeschnipsel, falls jemand das mal braucht. Ein RandomIterator - Konstruktor erfordert die Angabe von m - bringt die maximal m aus m Indizes in Zufallsreihenfolge hervor (Methode next() ). Wird häufiger als m-mal gezogen, wird nur noch zufällig zugegriffen ohne Doublettenschutz:

    #ifndef RANDOMITERATOR_H
    #define RANDOMITERATOR_H
    
    class RandomIterator
    {
    protected:
       unsigned int *indexarr;
       unsigned int size;
       unsigned int limit;
    
       inline void initialize()
       {
          unsigned int i;
    
          for(i=0;i<size;++i) indexarr[i] = i;
          limit = size;
       }
    
    public:
       inline RandomIterator(unsigned int s)
       {
          size = s;
          indexarr = new unsigned int[size];
          initialize();
       }
    
       inline unsigned int next()
       {
          if(!limit)
          {
             return(mt.randIntScale(size));
          }
          unsigned int inx = mt.randIntScale(limit);
          unsigned int val = indexarr[inx];
          --limit;
          indexarr[inx] = indexarr[limit];
          indexarr[limit] = val;
          return(val);
       }
    
       inline ~RandomIterator()
       {
          delete indexarr;
       }
    
       inline operator unsigned int()
       {
          return(limit);
       }
    };
    
    #endif
    


  • CStoll schrieb:

    1. Ab n=m/2 könntest du den Ansatz ja umkehren - du wählst dir m-n Objekte aus deinem Haufen aus und verarbeitest dann alle übrigen.

    2. Alternativ kannst du auch die ausgewählten Elemente aus der Liste rausschmeißen, so daß du immer nur über "neue" Elemente suchen mußt.

    PS: sizeof(char) == 1 😉

    Ich hab' mal numeriert... 😉

    zu 1.: ja, das könnte was bringen, danke.

    zu 2.: das ist aber durch die Listenverwaltung eventuell aufwendiger.

    zu PS: ja, sicher, aber das ist ein Reflex von mir - eh' ich mal int habe und das sizeof vergesse...



  • Siehe 2 Posts über diesem: Codebeispiel zur gefälligen Verwendung eingefügt. Danke nochmal für die Hilfe!



  • Wie wärs damit, das Array von vorne herein mit zufälligen
    Werten zu füllen (dabei Wertebereich beachten und doubletten entfernen)
    und dann der Reihe nach auszulesen? (sprich, wenn du 2 aus 4 brauchst
    einfach 0..1 auslesen, beim nächsten 2 aus 4 2..3 - Prinzip klar?)

    Das Füllen dauert dann viel länger, aber je nach Verhältniss
    Read/Write Ops wirds insgesamt vieleicht schneller?



  • Ja, das könnte generell auch gehen, bei mir ist das Problem aber meist in Richtung "n dicht bei m" verschoben, so dass ich eigentlich "liefere mir n Einträge in zufälliger Reihenfolge" brauchte. Und das macht das Codestück oben ganz gut.
    Danke dennoch für Deine Idee! 🙂



  • Nur noch ein Ansatz (wenn auch verspätet): Du könntest auch random_shuffle() verwenden, um ein mit 1,2,3,4... vorbelegtes Feld zu vermischen und dann elementweise auszulesen.

    (PS: Dein RandomIterator benötigt übrigens noch Copy-Ctor und operator=, sonst stößt du schnell auf Zugriffsfehler)



  • CStoll schrieb:

    (PS: Dein RandomIterator benötigt übrigens noch Copy-Ctor und operator=, sonst stößt du schnell auf Zugriffsfehler)

    Klar. Ist ja nur eine schnell-und-schmutzig-Skizze. 😃


Log in to reply