Permutationen (k aus n)

Übersicht BlitzBasic Codearchiv

Neue Antwort erstellen

diceman

Betreff: Permutationen (k aus n)

BeitragDi, Dez 17, 2013 23:02
Antworten mit Zitat
Benutzer-Profile anzeigen
Hatte gerade etwas Langeweile und habe eine Funktion zusammengekloppt, die Permutationen von k aus n erstellt (ohne Reihenfolge und Wiederholungen - z.B.: 5 Karten, die aus einem 32er Deck gezogen werden).
Die finale Anzeige-Funktion der Permutationen ist natürlich nur rudimentär und kann leicht optimiert werden, aber darum geht's hier auch nicht Wink . Wollte den Code nicht mehr als nötig aufpumpen.



Code: [AUSKLAPPEN]
Const n = 7
Const k = 5

Dim seq(k)
Global index

Type PERMUTATION
   Field SEQUENCE[5] ; Array kann nicht indiziert werden, Type-Arrays müssen immer konstant sein!
End Type

;Startsequenz erstellen
For var = 1 To k
   seq(var) = var
Next
createSequence()

index = k ; den Zeiger auf den letzte Stelle der Sequenz setzen --> diese wird bis auf n hochgezählt, dann kommt der Überlauf

Repeat
   If seq(index) < n And (Not((seq(index) +1) = seq(limit(index+1,0,k)) And index < k))
      seq(index) = seq(index) +1
      If index < k ; Beim Überlauf die nachfolgenden Sequenz-Einträge resetten
         For var = index+1 To k
            seq(var) = seq(index) + (var-index)
         Next
         index = k ; den Zeiger zurück auf die letzte Stelle der Sequenz setzen
      EndIf
      
      ; aktuell erstellte Permutation speichern
      createSequence()

   Else
      index = index -1
   EndIf
Until seq(1) = (n-k+1)

index = 0
For perm.PERMUTATION = Each PERMUTATION
   Print perm\SEQUENCE[1]+","+perm\SEQUENCE[2]+","+perm\SEQUENCE[3]+","+perm\SEQUENCE[4]+","+perm\SEQUENCE[5]
   index = index +1
Next
Print
Print index+" Permutations"
WaitKey()
End






Function createSequence()
   perm.PERMUTATION = New PERMUTATION
   For var = 1 To k
      perm\SEQUENCE[var] = seq(var)
   Next
End Function



Function limit(value,min,max)
   ; Nützliche Allround-Funktion, die eine ihr übergebene Zahl auf einen bestimmten Bereich limitiert, bsp. um einen "Array Index out of Bounds"-Error zu vermeiden.

   If value < min Then Return min
   If value > max Then Return max
   Return value
End Function

Neue Antwort erstellen


Übersicht BlitzBasic Codearchiv

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group