[Mathe/Coding] Permutation einer Kombination von Zahlen

    • bahmrockk
      bahmrockk
      Bronze
      Dabei seit: 10.09.2005 Beiträge: 6.769
      Hiho,
      ich habe hier nen Problem, und weil ich Kopfschmerzen habe, schreibe ich das einfach mal hier rein, um es mit euch zu teilen :D

      Gegeben:

      Eine Zahl, in diesem Beispiel 21.

      Dazu passend 21 Felder.

      Nun soll diese Zahl a) in alle Moeglichen Summanden zerlegt und b) ueber die 21 Felder permutiert werden, es soll also von

      21 0 0 0 0 usw
      bis usw 0 0 0 0 21
      ueber 1 1 1 1 1 usw
      20 1 0 0 0 0 ...
      alles vertreten sein, und das bei allen Stellen

      Die Permutation ist ja in C++ dank vorgefertigter Funktionen recht einfach zu erledigen.
      Nun wollte ich eine Summandenzerlegung bauen, die mir immer einen Zahlenblock rauswirft und den dann durchpermutiert und weitermacht.

      Das Problem ist, dass ich entweder Reihen wie 5 5 8 3 0 0 ... nicht rauskriege, oder aber die simplen wie 18 3 0 0 - beide zusammen habe ich nicht hingekriegt :(
      Nun koennte das natuerlich mit dem Zustand meines Kopfes zusammenhaengen und ich hoffe, dass ich hier den Ehrgeiz von euch hier foerdern kann, diese scheinbar leichte Aufgabe zu loesen :D
      Danke euch,

      - georg
  • 20 Antworten
    • philwen
      philwen
      Bronze
      Dabei seit: 13.05.2007 Beiträge: 5.601
      ich könnte es dir in VB oder pascal schreiben - aber c++ kp...
    • bahmrockk
      bahmrockk
      Bronze
      Dabei seit: 10.09.2005 Beiträge: 6.769
      pascal reicht völlig!
      danke,
      georg
    • philwen
      philwen
      Bronze
      Dabei seit: 13.05.2007 Beiträge: 5.601
      hmm , hab deine frage falsch verstanden - aber ich schau mal ob ichs doch hinkrieg...
    • dayero
      dayero
      Bronze
      Dabei seit: 26.02.2005 Beiträge: 1.723
      besorg einen sng 55+ coach und ich denk ernsthaft drüber nach.


      da siehst du mal, wie verzweifelt ich bin, daß ich schon zu erpressung greifen muss :D
    • MisterJ
      MisterJ
      Bronze
      Dabei seit: 26.03.2006 Beiträge: 1.760
      Nur so ausm kopf - kA obs das tut, was es soll und ob bugs, etc., aber denke das Prinzip müsste gehen.

      code:
      typedef int[5] felder;
      
      vector<felder> alleFelder;
      felder currentFelder;
      
      currentFelder = {0,0,0,0,0}
      
      zerlege(21, 5);
      
      void zerlege(int zahl, int numFelder)
      {
        if(numFelder == 1) {
          currentFelder[5 - numFelder] = zahl;
          alleFelder.push_back(currentFelder);
          return;
        }
        for(int i = 0; i <= zahl; i++) {
          currentFelder[5 - numFelder] = i;
          zerlege(zahl - i, numFelder - 1);
        }
      }
      
    • MisterJ
      MisterJ
      Bronze
      Dabei seit: 26.03.2006 Beiträge: 1.760
      Nachtrag: Blödes Nerd Dasein, ich konnte's nicht lassen das auszuprobieren. Hier also der kompilierende code für 12650 Kombos.
      php:
      #include <vector>                                                                                                                                                                
      using std::vector;                                                                                                                                                                
      #include <stdio.h>                                                                                                                                                                
                                                                                                                                                                                        
      typedef vector<intfelder;                                                                                                                                                       
                                                                                                                                                                                        
      vector<felderalleFelder;                                                                                                                                                        
      felder currentFelder;                                                                                                                                                             
                                                                                                                                                                                        
      void zerlege(int zahlint numFelder)                                                                                                                                             
      {                                                                                                                                                                                 
         if(numFelder == 1) {                                                                                                                                                           
            currentFelder[numFelder] = zahl;                                                                                                                                        
            alleFelder.push_back(currentFelder);                                                                                                                                        
            return;                                                                                                                                                                     
         }                                                                                                                                                                              
         for(int i 0<= zahli++) {                                                                                                                                               
            currentFelder[numFelder] = i;                                                                                                                                           
            zerlege(zahl inumFelder 1);                                                                                                                                           
         }                                                                                                                                                                              
      }                                                                                                                                                                                 
                                                                                                                                                                                        
      int main()                                                                                                                                                                        
      {                                                                                                                                                                                 
         for(int i 05i++)                                                                                                                                                     
            currentFelder.push_back(0);                                                                                                                                                 
                                                                                                                                                                                        
         zerlege(215);                                                                                                                                                                
                                                                                                                                                                                        
         printf("%d\n"alleFelder.size());                                                                                                                                               
         for(int i 0alleFelder.size(); i++) {                                                                                                                                   
            for(int j 05j++)                                                                                                                                                  
               printf("%d "alleFelder.at(i)[j]);                                                                                                                                      
            printf("\n");                                                                                                                                                               
         }                                                                                                                                                                              
      }
    • bahmrockk
      bahmrockk
      Bronze
      Dabei seit: 10.09.2005 Beiträge: 6.769
      Original von dayero
      besorg einen sng 55+ coach und ich denk ernsthaft drüber nach.


      da siehst du mal, wie verzweifelt ich bin, daß ich schon zu erpressung greifen muss :D
      done, naechsten Freitag gibts Coaching fuer 200er+, erst mal einmal die Woche! :D

      @MisterJ danke, probiere ich sofort aus!

      - georg
    • bahmrockk
      bahmrockk
      Bronze
      Dabei seit: 10.09.2005 Beiträge: 6.769
      @MisterJ leider schmiert Dein Code bei mir ab, wenn ich die Anzahl an Stellen von 5 auf 21 erhoehe - die Rekursion ist dann wohl doch nen bissel zuviel fuer ihn ^^

      - georg
    • MisterJ
      MisterJ
      Bronze
      Dabei seit: 26.03.2006 Beiträge: 1.760
      Naja, rekursiven Code kann man auch nicht-rekursiv umschreiben.
      Viel Spaß dabei :D
    • bahmrockk
      bahmrockk
      Bronze
      Dabei seit: 10.09.2005 Beiträge: 6.769
      Original von MisterJ
      Naja, rekursiven Code kann man auch nicht-rekursiv umschreiben.
      Viel Spaß dabei :D
      na obs das loesen wird .... ? *g* Ich mach mich aber ran ^^ Wenn das nicht hilft, dann weiss ich auch nicht ^^

      - georg
    • dayero
      dayero
      Bronze
      Dabei seit: 26.02.2005 Beiträge: 1.723
      ab welchem status soll das coaching denn zugänglich sein?


      ich denk das problem ist, daß das gegebene problem ein problem ist :D
      ne im ernst, mit 21 feldern sinds vielleicht einfach zuviele kombinationen, so daß für >alleFelder.push_back(currentFelder); kein speicher mehr zur verfügung steht. ich würde das mal so umschreiben, daß du am anfang den speicherbedarf berechnest, dann mit vector::max_size die maximal mögliche größe abfragst und wenn sie nicht ausreicht, mit fehlermeldung abbrichst.
      wenn sie ausreicht, solltest du den speicher auch gleich mit vector::reserve am stück reservieren, byteweise per pushback bestellen ist nämlich sacklangsam, weil dabei hin- und herkopiert wird, wenn der vector zu groß für das speicherfragment wird, in dem er gerade haust.
    • binarytruth
      binarytruth
      Bronze
      Dabei seit: 26.06.2007 Beiträge: 3
      Hi,

      muss mal mitnerden und meine unqualifizierte Meinung mit in den Pott schmeißen ;)

      Grundsätzlich dürfte das Wachstum der Permutationen von der Anzahl der Eingabestellen Exponentiell (-> Fakultät) abhängen. Ich glaube da bekommst du relativ fix probleme. Bin aber zu müde mir Gedanken drüber zu machen wie die Rekurrenzgleichung aussieht. :D

      An der Speicherverwaltung zu drehen wird auch nicht helfen, denk mal der Flaschenhals ist der Stack (wg. Rekursion). Und nur Tail-Call-Recursion lässt sich in andere Schleifen überführen (Quicksort z.B. funktioniert ja nur mit echter Rekursion und Stack).

      Ich würde die Zeit lieber darauf verwenden mir Gedanken zu machen welche der Permutationen du tatsächlich brauchst und dann entsprechend nur die berechnen... aber kA was du vorhast :)

      Edit: Das soll nich Zufällig ne Blackjack-KI werden? :D
    • hitecc
      hitecc
      Bronze
      Dabei seit: 26.04.2007 Beiträge: 160
      code:
      int sum = 21;
      int no_fields = 5;
      
      int * fields = new fields[no_fields];
      
      for (int i = 0; i < (int)pow(sum, no_fields); ++i)
      {
        int csum = 0;
        for (int f = 0; f < no_fields; ++f)
        {
          csum += fields[f] = i % (int)(pow(sum, f+1)) / (int)(pow(sum, f));
        }
        if (csum == sum)
          for (int f = 0; f < no_fields; ++f)
            printf("%d%s ", fields[f], f < no_fields - 1 ? "," : "");
      }
      


      Habe keinen compiler zur Hand mit dem ich das Testen kann, also ohne Gewähr.
    • SQuick
      SQuick
      Bronze
      Dabei seit: 10.03.2006 Beiträge: 485
      Wenn ich es richtig verstehe ist die Zerlegung in die Partitionszahlen das Problem.

      Vielleicht habe ich gerade ein Brett vor dem Kopf aber eine einfache Möglichkeit wäre hier einfach durch Brutforce das Array zu durchlaufen und jede Stelle des Arrays hochzuzählen und die Summe des Arrays zu checken.

      int a[] = new int[3];
      for (int i = 0; i <= 3; i++) {
      for (int k = 0; k <= 3; k++) {
      for (int j = 0; j <= 3; j++) {
      a[0] = j;
      a[1] = k;
      a[2] = i;
      if (a[0] + a[1] + a[2] == 3) {
      System.out.println(a[0] + " " + a[1] + " " + a[2]);
      }
      }
      }
      }

      }

      hier als Bsp. für die Zahl 3. Du läufst jedes Feld des Arrays von 0-3 und gibt dir auch gleich alle Permutationen aus.
      Ausgabe:
      3 0 0
      2 1 0
      1 2 0
      0 3 0
      2 0 1
      1 1 1
      0 2 1
      1 0 2
      0 1 2
      0 0 3
    • binarytruth
      binarytruth
      Bronze
      Dabei seit: 26.06.2007 Beiträge: 3
      Okay, lass mal überlegen.

      Bei 21 Stellen und der Zahl 21 gibt es per Bruteforce 21^21 Mögliche Kombinationen. Nehmen wir an wir haben einen Vektorrechner der uns in jedem Taktschritt eine dieser Kombinationen berechnet und überprüft. Nehmen wir zusätzlich an, dass der Rechner bei 1GHz getaktet ist. Dann brauchen wir nur 21^21 / 10^9 Sekunden auf unser Ergebnis warten.
      Das wäre dann ca. 5,84 * 10^18 Sekunden, also ca. 6,76 * 10^13 Jahre. Zum Vergleich: Das Universum ist etwa 13,7 * 10 ^ 9 Jahre alt. Die Zeit sollte wie im Flug vergehen! ;)
    • emophiliac
      emophiliac
      SuperModerator
      SuperModerator
      Dabei seit: 08.03.2005 Beiträge: 4.554
      ist doch easy. erstelle ein tupel oszillierender interferierender funktionen und lies die werte ab. sowas direkt berechnen ist doch asi. simulier es einfach.
    • SQuick
      SQuick
      Bronze
      Dabei seit: 10.03.2006 Beiträge: 485
      Stimmt für 21 ist der Aufwand so sehr hoch, aber auf die schnelle fällt mir kein einfacher algorithmus ein wie man alle Partialzerlegungen bekommt.
    • dayero
      dayero
      Bronze
      Dabei seit: 26.02.2005 Beiträge: 1.723
      ich denke, ich weiss, wie man das hinkriegt, aber ich hab den verdacht, das geht hier nur um irgendeine spielerei und da habe ich im moment nicht so den nerv, mir das hirn drüber kaputtzumachen.
    • binarytruth
      binarytruth
      Bronze
      Dabei seit: 26.06.2007 Beiträge: 3
      Naja, im Grunde genommen ist das Problem klar - nur ist die Ergebnismenge so groß dass man sie auf keinem existierenden Speicher unterbringen könnte. Daher wäre es sinnvoll den Anwendungszweck zu erfahren, so dass man sinnvollere Techniken (Pruning, Äquivalenzklassenbildung, ...) ansetzen könnte...
    • 1
    • 2