PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

Anzahl Schleifendurchläufe -> Kombinatorik

https://www.purebasic.fr/german/viewtopic.php?t=16228

Seite 1 von 2

Anzahl Schleifendurchläufe -> Kombinatorik

Verfasst: 02.04.2008 20:03
von NicknameFJ
Hallo zusammen,

wer von Euch war gut in Mathe und hat Ahnung von Kombinatorik ???

Ich habe folgendes Schleifenkonstrukt und müsste vor Eintritt in die Routine die Anzahl der Schleifendurchläufe in Abhängigkeit der beiden Variablen ANZAHL und TIEFE kennen die die innerste Schleife macht

Zur Beachtung:

Die Schleifen LP1 bis LP7 laufen von 0 bis zum Schleifenende, die innerste Schleife LP8 von 1 bis zum Schleifenende.

Die Schleifenenden sind in Abhängigkeit der Tiefe entweder 0 oder gleich der Variablen Anzahl - sh. Code

Die Schleifen 1-8 werden mit Continue übersprungen wenn der Schleifenzähler einen Wert hat, den schon eine vorherige Schleife hat und bei den Schleifen 1-7 (nicht in der innersten) muss die Laufvar. noch dazu ungleich NULL sein.

Die beiden Variablen am Anfang Anzahl und Tiefe habe ich nur mal so vorbelegt, diese sind im richtigen Programm variabel.

[EDIT]

Tiefe kann niemals den Wert 1 haben, nur von 2 bis 8

[END EDIT]


Danke schonmal im voraus

LG

Joachim


Hier der Code

Code: Alles auswählen

  
   Count  = 0
    
    Anzahl = 10
    Tiefe = 8        ; maximal 8 da nur 8 verschachtelte Schleifen

   
    LP1Ende = Anzahl 
    LP2Ende = Anzahl 
    LP3Ende = Anzahl 
    LP4Ende = Anzahl 
    LP5Ende = Anzahl 
    LP6Ende = Anzahl 
    LP7Ende = Anzahl 
    LP8Ende = Anzahl 
    
    
    If Tiefe = 2
      LP1Ende =  0
      LP2Ende =  0
      LP3Ende =  0
      LP4Ende =  0
      LP5Ende =  0
      LP6Ende =  0
      
    ElseIf Tiefe = 3
      LP1Ende =  0
      LP2Ende =  0
      LP3Ende =  0
      LP4Ende =  0
      LP5Ende =  0
      
    ElseIf Tiefe = 4
      LP1Ende =  0
      LP2Ende =  0
      LP3Ende =  0
      LP4Ende =  0
      
    ElseIf Tiefe = 5
      LP1Ende =  0
      LP2Ende =  0
      LP3Ende =  0
      
    ElseIf Tiefe = 6
      LP1Ende =  0
      LP2Ende =  0
      
    ElseIf Tiefe = 7
      LP1Ende =  0
      
    ElseIf Tiefe = 8
      
      
    EndIf
    
    
    For LP1 = 0 To LP1Ende
      
      For Lp2 = 0 To LP2Ende
        
        If Lp2 = LP1 And Lp2 <> 0
          Continue  
        EndIf
        
        
        For LP3 = 0 To LP3Ende
          If (LP3 = Lp2 Or LP3 = LP1) And LP3 <> 0
            Continue
          EndIf
          
          
          For LP4 = 0 To LP4Ende
            If (LP4 = LP3 Or LP4 = Lp2 Or LP4 = LP1) And LP4 <> 0
              Continue
            EndIf
            
            For LP5 = 0 To LP5Ende
              
              
              If (LP5 = LP4 Or LP5 = LP3 Or LP5 = Lp2 Or LP5 = LP1) And LP5 <> 0
                Continue
              EndIf
              
              
              For LP6 = 0 To LP6Ende
                
                
                If (LP6 = LP5 Or LP6 = LP4 Or LP6 = LP3 Or LP6 = Lp2 Or LP6 = LP1) And LP6 <> 0
                  Continue
                EndIf
                
                
                For LP7 = 0 To LP7Ende
                  
                  
                  If (LP7 = LP6 Or LP7 = LP5 Or LP7 = LP4 Or LP7 = LP3 Or LP7 = Lp2 Or LP7 = LP1) And LP7 <> 0
                    Continue
                  EndIf
                  
                  
                  For LP8 = 1 To LP8Ende
                    
                    If (LP8 = LP7 Or LP8 = LP6 Or LP8 = LP5 Or LP8 = LP4 Or LP8 = LP3 Or LP8 = Lp2 Or LP8 = LP1) ;And LP8 <> 0
                      Continue
                    EndIf
                    
                    
                    
                    Count = Count +1
                    
                    
                    
                  Next LP8  
                Next LP7
              Next LP6
            Next LP5
          Next LP4
        Next LP3
      Next Lp2
    Next LP1
    
    
    MessageRequester("","Insgesamt waren dies "+Str(Count) + " Schleifendurchläufe")

Verfasst: 02.04.2008 20:07
von Andreas_S
Einfach multiplizieren...

Code: Alles auswählen

Anzahl = LP1Ende * LP2Ende * LP3Ende * ... * LP8Ende + AnzahlDerSchleifen - 1
'+ AnzahlDerSchleifen - 1' weil du bei 0 beginnst und bei einer nicht...

Verfasst: 02.04.2008 20:10
von NicknameFJ
DANKE, aber ne iss nich, weil die Schleifen zwischendurch mit CONTINUE abgebrochen werden

Verfasst: 02.04.2008 20:14
von Andreas_S
Ahh... habs erst jetzt gesehn...

Außerdem wäre meins eh falsch...
so wärs richtig:

Code: Alles auswählen

Anzahl = (LP1Ende+1) * (LP2Ende+1) * (LP3Ende+1) * ... LP8Ende

Verfasst: 02.04.2008 20:20
von gnasen
der Übersicht zu liebe (und vllt auch zur weiteren Nutzung) würde ich das ganze in eine Prozedur packen, die du mit den Argumenten Tiefe und Anzahl aufrufst, also den Inhalt dynamisch gestalten, nicht diese Schleifen in Schleifen Konstruktion per Hand

Verfasst: 02.04.2008 20:23
von NicknameFJ
@ gnasen

Danke für den Hinweis, aber wenn ich das hier so gemacht hätte (mit Rekursion ?) dann hätte bei dem Konstrukt - so befürchte ich - hier keiner mehr durchgeblickt was ich eigentlich wollte

Verfasst: 03.04.2008 02:53
von NicTheQuick
Hab da jetzt mal zur Erholung von meinem Projekt was für dich getüftelt.
Ist zwar kein Einzeiler, funktioniert aber und hat konstante Laufzeit zum
Berechnen.
Aber wenn du jetzt etwas an den Schleifendurchläufen änderst, kann ich
dir nicht sagen, was du wo ändern musst.

Code: Alles auswählen


Count1 = 0 : Count2 = 0 : Count3 = 0 : Count4 = 0 : Count5 = 0 : Count6 = 0 : Count7 = 0 : Count8 = 0

Anzahl = 10
Tiefe = 8        ; maximal 8 da nur 8 verschachtelte Schleifen

LP1Ende = Anzahl : LP2Ende = Anzahl : LP3Ende = Anzahl : LP4Ende = Anzahl : LP5Ende = Anzahl : LP6Ende = Anzahl : LP7Ende = Anzahl : LP8Ende = Anzahl

If Tiefe = 2
  LP1Ende =  0 : LP2Ende =  0 : LP3Ende =  0 : LP4Ende =  0 : LP5Ende =  0 : LP6Ende =  0
ElseIf Tiefe = 3
  LP1Ende =  0 : LP2Ende =  0 : LP3Ende =  0 : LP4Ende =  0 : LP5Ende =  0 : 
ElseIf Tiefe = 4
  LP1Ende =  0 : LP2Ende =  0 : LP3Ende =  0 : LP4Ende =  0
ElseIf Tiefe = 5
  LP1Ende =  0 : LP2Ende =  0 : LP3Ende =  0
ElseIf Tiefe = 6
  LP1Ende =  0 : LP2Ende =  0
ElseIf Tiefe = 7
  LP1Ende =  0
ElseIf Tiefe = 8
  ;do nothing
EndIf

k1 = LP1Ende + 1
k2 = k1 * LP2Ende + 1
k3 = k2 * LP3Ende + 1
If Tiefe > 7 : k3 - 90 : EndIf
k4 = k3 * LP4Ende + 1
If Tiefe > 6 : k4 - 90 : EndIf
If Tiefe > 7 : k4 - 1620 : EndIf
k5 = k4 * LP5Ende + 1
If Tiefe > 5 : k5 - 90 : EndIf
If Tiefe > 6 : k5 - 1620 : EndIf
If Tiefe > 7 : k5 - 19710 : EndIf
k6 = k5 * LP6Ende + 1
If Tiefe > 4 : k6 - 90 : EndIf
If Tiefe > 5 : k6 - 1620 : EndIf
If Tiefe > 6 : k6 - 19710 : EndIf
If Tiefe > 7 : k6 - 190440 : EndIf
k7 = k6 * LP7Ende + 1
If Tiefe > 3 : k7 - 90 : EndIf
If Tiefe > 4 : k7 - 1620 : EndIf
If Tiefe > 5 : k7 - 19710 : EndIf
If Tiefe > 6 : k7 - 190440 : EndIf
If Tiefe > 7 : k7 - 1526850 : EndIf
k8 = k7 * (LP8Ende - 1) + 1
If Tiefe > 2 : k8 - 90 : EndIf
If Tiefe > 3 : k8 - 1620 : EndIf
If Tiefe > 4 : k8 - 19710 : EndIf
If Tiefe > 5 : k8 - 190440 : EndIf
If Tiefe > 6 : k8 - 1526850 : EndIf
If Tiefe > 7 : k8 - 10303740 : EndIf

MessageRequester("", "Die innere Schleife wird " + Str(k8) + " durchlaufen werden!")

Gosub loop

s.s = "Ergebnisse: (Kombinatorik)" + Chr(10)
s   + "Schleife 1: " + Str(Count1) + " Durchläufe (" + Str(k1) + ")" + Chr(10)
s   + "Schleife 2: " + Str(Count2) + " Durchläufe (" + Str(k2) + ")" + Chr(10)
s   + "Schleife 3: " + Str(Count3) + " Durchläufe (" + Str(k3) + ")" + Chr(10)
s   + "Schleife 4: " + Str(Count4) + " Durchläufe (" + Str(k4) + ")" + Chr(10)
s   + "Schleife 5: " + Str(Count5) + " Durchläufe (" + Str(k5) + ")" + Chr(10)
s   + "Schleife 6: " + Str(Count6) + " Durchläufe (" + Str(k6) + ")" + Chr(10)
s   + "Schleife 7: " + Str(Count7) + " Durchläufe (" + Str(k7) + ")" + Chr(10)
s   + "Schleife 8: " + Str(Count8) + " Durchläufe (" + Str(k8) + ")" + Chr(10)

MessageRequester("", s)

End

loop:
For LP1 = 0 To LP1Ende
  Count1 + 1
  
  For Lp2 = 0 To LP2Ende
    If Lp2 = LP1 And Lp2 : Continue : EndIf
    Count2 + 1
    
    For LP3 = 0 To LP3Ende
      If (LP3 = Lp2 Or LP3 = LP1) And LP3 : Continue : EndIf
      Count3 + 1
      
      For LP4 = 0 To LP4Ende
        If (LP4 = LP3 Or LP4 = Lp2 Or LP4 = LP1) And LP4 : Continue : EndIf
        Count4 + 1
        
        For LP5 = 0 To LP5Ende
          If (LP5 = LP4 Or LP5 = LP3 Or LP5 = Lp2 Or LP5 = LP1) And LP5 : Continue : EndIf
          Count5 + 1
         
          For LP6 = 0 To LP6Ende
            If (LP6 = LP5 Or LP6 = LP4 Or LP6 = LP3 Or LP6 = Lp2 Or LP6 = LP1) And LP6 : Continue : EndIf
            Count6 + 1
           
            For LP7 = 0 To LP7Ende
              If (LP7 = LP6 Or LP7 = LP5 Or LP7 = LP4 Or LP7 = LP3 Or LP7 = Lp2 Or LP7 = LP1) And LP7 : Continue : EndIf
              Count7 + 1
              
              For LP8 = 1 To LP8Ende
                If (LP8 = LP7 Or LP8 = LP6 Or LP8 = LP5 Or LP8 = LP4 Or LP8 = LP3 Or LP8 = Lp2 Or LP8 = LP1) : Continue : EndIf
               
                Count8 + 1
                
              Next
            Next
          Next
        Next
      Next
    Next
  Next
Next
Return
///Edit:
Mist!
Hab natürlich nicht bedacht, dass ich auch noch auf die Anzahl als nur die
Tiefe achten muss.
Geht also doch nicht. Sorry.

Verfasst: 03.04.2008 08:52
von Froggerprogger
Moinsen!
Die Formel lautet:
Bild
LaTeX-Code: \[Anzahl + \sum_{t=1}^{Tiefe-1} \binom{Tiefe-1}{t} \* \binom{Anzahl}{t} \* t! \* (Anzahl-t)\]

Darauf kommt man, indem man sich in der innersten Schleife die Kombinationen ausgibt und daran ein bißchen rumknobelt. Bei Interesse kann ich dazu noch was schreiben.

In PB könnte man das so berechnen:

Code: Alles auswählen

Procedure.l Faculty(n)
  If n > 12
    MessageRequester("Overflow", "Parameter " + Str(n) + " too big For Faculty")
    End
  EndIf
  If n = 0 Or n = 1
    ProcedureReturn 1
  Else
    ProcedureReturn n * Faculty(n-1)
  EndIf
EndProcedure

Procedure Binomial(n, k)
  If n < 0 Or k < 0 Or n < k
    ProcedureReturn 0
  Else
    ProcedureReturn (Faculty(n) / Faculty(k)) / Faculty(n-k)
  EndIf
EndProcedure

Procedure GetNumCombinations(depth.l, numElems.l)
  Protected numCombs.l, d.l
  numCombs = numElems ; 0....0x
  For d = 1 To depth-1
    numCombs = numCombs + Binomial(depth-1, d) * Binomial(numElems, d) * Faculty(d) * (numElems-d)
  Next
  ProcedureReturn numCombs
EndProcedure

Procedure.l CountCombinations(Tiefe.l, Anzahl.l)
   Count  = 0
   
    LP1Ende = Anzahl
    LP2Ende = Anzahl
    LP3Ende = Anzahl
    LP4Ende = Anzahl
    LP5Ende = Anzahl
    LP6Ende = Anzahl
    LP7Ende = Anzahl
    LP8Ende = Anzahl
   
   
    If Tiefe = 2
      LP1Ende =  0
      LP2Ende =  0
      LP3Ende =  0
      LP4Ende =  0
      LP5Ende =  0
      LP6Ende =  0
     
    ElseIf Tiefe = 3
      LP1Ende =  0
      LP2Ende =  0
      LP3Ende =  0
      LP4Ende =  0
      LP5Ende =  0
     
    ElseIf Tiefe = 4
      LP1Ende =  0
      LP2Ende =  0
      LP3Ende =  0
      LP4Ende =  0
     
    ElseIf Tiefe = 5
      LP1Ende =  0
      LP2Ende =  0
      LP3Ende =  0
     
    ElseIf Tiefe = 6
      LP1Ende =  0
      LP2Ende =  0
     
    ElseIf Tiefe = 7
      LP1Ende =  0
     
    ElseIf Tiefe = 8
     
     
    EndIf
   
   
    For LP1 = 0 To LP1Ende
     
      For Lp2 = 0 To LP2Ende
       
        If Lp2 = LP1 And Lp2 <> 0
          Continue 
        EndIf
       
       
        For LP3 = 0 To LP3Ende
          If (LP3 = Lp2 Or LP3 = LP1) And LP3 <> 0
            Continue
          EndIf
         
         
          For LP4 = 0 To LP4Ende
            If (LP4 = LP3 Or LP4 = Lp2 Or LP4 = LP1) And LP4 <> 0
              Continue
            EndIf
           
            For LP5 = 0 To LP5Ende
             
             
              If (LP5 = LP4 Or LP5 = LP3 Or LP5 = Lp2 Or LP5 = LP1) And LP5 <> 0
                Continue
              EndIf
             
             
              For LP6 = 0 To LP6Ende
               
               
                If (LP6 = LP5 Or LP6 = LP4 Or LP6 = LP3 Or LP6 = Lp2 Or LP6 = LP1) And LP6 <> 0
                  Continue
                EndIf
               
               
                For LP7 = 0 To LP7Ende
                 
                 
                  If (LP7 = LP6 Or LP7 = LP5 Or LP7 = LP4 Or LP7 = LP3 Or LP7 = Lp2 Or LP7 = LP1) And LP7 <> 0
                    Continue
                  EndIf
                 
                 
                  For LP8 = 1 To LP8Ende
                   
                    If (LP8 = LP7 Or LP8 = LP6 Or LP8 = LP5 Or LP8 = LP4 Or LP8 = LP3 Or LP8 = Lp2 Or LP8 = LP1) ;And LP8 <> 0
                      Continue
                    EndIf
                   
                   
                   
                    Count = Count +1
                   
                  Next LP8 
                Next LP7
              Next LP6
            Next LP5
          Next LP4
        Next LP3
      Next Lp2
    Next LP1
   
  ProcedureReturn Count
EndProcedure

For Tiefe = 2 To 8
  For Anzahl = 0 To 12
    calc.l = GetNumCombinations(Tiefe, Anzahl)
    count.l = CountCombinations(Tiefe, Anzahl)
    If calc <> count
      Debug "Fehler für Tiefe=" + Str(Tiefe) + " Anzahl=" + Str(Anzahl)
      End
    Else
      Debug Str(calc) + " = " + Str(count)
    EndIf
  Next
Next
Debug "OK"
So geht das aber nur bis Anzahl=12, da sonst die Implementation von Faculty streikt, man könnte aber ja auch mit Quads rechnen, musst du mal schauen. Mit Quads sollte man bis zu Anzahl 237 (bei Tiefe 8 ) rechnen können, denn dafür liefert Maple das Ergebnis 9105757030337110821 < 9223372036854775808 = 2^63

Maple (und jedes andere CAS, oder eine BigNumLib) liefert aber ohne Probleme auch für Anzahl 10000 die Lösung: 99790195898530934547505281460000

Verfasst: 03.04.2008 12:38
von NicTheQuick
Den Binomialkoeeffizienten kann man ja einfach er ausrechnen, da sich da
immer einiges wegkürzen lässt.

Verfasst: 03.04.2008 13:55
von Froggerprogger
Jau, da gibt es bessere Verfahren. Bis gerade eben dachte ich aber noch, dass das nix bringt, da man ja in t! trotzdem die Fakultät braucht, die läuft aber gar nicht bis Anzahl-1 (wie ich dachte), sondern nur bis Tiefe-1, also kann man mit einer geeigneten Binomial-Implementation auch ohne Quads bis zu Anzahl 17 (bei Tiefe 8 ) rechnen, dann erhält man 1881506161 < 2^31 Kombinationen ohne Überlauf in den Zwischenergebnissen. Mit Quads wird man auch nur dann bis zur Grenze 237 gelangen, wenn man eine andere Implementation für den Binomialkoeffizienten nutzt, denn sonst wäre schon bei 21 Schluss, da im Zwischenergebnis 21! > 2^63 wäre.

Ansonsten auf eine BigNum-Lib ausweichen, oder die Werte in einem CAS vorberechnen und als Tabelle halten. Eine solche Tabelle für z.B. Tiefe 2..8 und Anzahl 0..1000 könnte ich posten falls gewünscht. Hier das Maple-Programm zur Ausgabe einer solchen Tabelle:

Code: Alles auswählen

numCombs := (T, A) -> A + sum(binomial(T-1,t) * binomial(A, t) * t! * (A-t), t=1..T-1);

for T from 2 to 8 do
  for A from 0 to 100 do
    printf("(T:%d A:%d)->%d\n", T, A, numCombs(T,A));
  end;
end;
Alle Zeiten sind UTC+02:00
Seite 1 von 2

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de