Abbilden einer Reihenfolge

  • Excel

Es gibt 12 Antworten in diesem Thema. Der letzte Beitrag () ist von petaod.

    Abbilden einer Reihenfolge

    Hallo zusammen,

    ich habe folgendes Problem: Ich habe mit Hilfe von VBA ein Makro für Excel erstellt, welches zunächst in den Spalten 1 bis 4 mit den Zahlen 1 bis 4 alle Permutationen abbildet. D.h. das Makro generiert alle möglichen Kombinationen, welche sich aus diesen 4 Ziffern bilden lassen, ohne Wiederholungen zu zu lassen.
    Exemplarisch sieht das dann so aus:

    1 2 3 4
    1 2 4 3
    1 4 2 3
    1 4 3 2
    ...

    So gehts weiter bis die 24 Möglichkeiten abgebildet sind. Dies funktioniert auch so weit ganz gut.

    Mein Ziel ist es nun die Reihenfolge der Zahlen in den Spalten 6 bis 9 abzubilden. Dies habe ich versucht über die Position der Zahlen auszudrücken. Wenn man davon ausgeht, dass die Gundreihenfolge 1 2 3 4 ist, so ist bei der ersten Möglichkeit die Reihenfolge ebenfalls 1 2 3 4. D.h. die 1 ist an der 1. Position, die 2 and der 2. Position usw...
    Für die Permutation 4 3 1 2 wäre die Reihenfolge / Position dann zum Beispiel 3 4 2 1. Nochmal kurz zum Verständnis: die 1 an 3. Position, die 2 an 4. Position, die 3 an 2. Position und die 4 an 1. Position.

    Ich habe bereits eine Möglichkeit gefunden diese Positionsbestimmung durchzuführen - das Problem ist jedoch, dass die Methode relativ langsam ist, da sie so lange Schleifen durchläuft bis für jede einzelne Spalte pro Zeile die Reihenfolge abgebildet ist.

    Visual Basic-Quellcode

    1. 'Reihenfolge bilden
    3. Dim Rang As Long
    4. Dim Position As Long
    6. Position = 6 '1. Spalte der Reihenfolgetabelle
    8. Do While Position < 10 'Nummer ist eins höher als letzte Spalte der Reihenfolgetabelle
    10. Rang = Application.Match((Cells(1, Position)), Range((Cells(Zeile, 1)), (Cells(Zeile, 4))), 0) 'Range für Permutationstabelle
    11. Cells(Zeile, Position) = Rang
    13. Position = Position + 1
    15. Loop


    Anmerkung: Die Grundreihenfolge steht in der 1. Zeile der Reihenfolgetabelle (Spalte 6 bis 9). Application.Match nutzt diese Grundreihenfolge, um einen Abgleich mit den ersten 4 Spalten zu machen.

    Jetzt könnte man natürlichen sagen, dass das nicht allzu lange dauert für 24 Möglichkeiten. Mein Ziel ist jedoch diese Permutationstabelle zu vergrößern. Bei 10 Ziffern handelt es sich schon um 3,6 Mio Möglichkeiten und da bremst diese Reihenfolge-Schleife ziemlich. Und sie soll eigentlich noch größer werden.


    Hat irgendjemand eine Idee wie sich die Reihenfolge-/Positionsbestimmung schneller durchführen lässt? Vielleicht in einem einzigen Schritt pro Zeile?


    Falls etwas nicht verstanden wurde weil ich es zu kompliziert oder nicht ausreichend erklärt habe bin ich auch gerne bereit mein Thema noch weiter zu erläutern.

    Vielen Dank im Voraus!
    Bo2k

    Hey...
    mal so als Anregung...

    Visual Basic-Quellcode

    1. Option Explicit
    2. Dim j As Integer
    3. Private Sub cmdTest_Click()
    4. j = 1
    5. Call permut(1, 2345)
    6. End Sub
    7. Sub permut(ByVal einzel As String, ByVal rest As String)
    8. Dim neuEinzel, neuRest As String
    9. Dim i As Integer
    10. If Not rest = "" Then
    11. For i = 1 To Len(rest)
    12. neuEinzel = einzel & Mid(rest, i, 1)
    13. neuRest = Replace(rest, Mid(rest, i, 1), "")
    14. Call permut(neuEinzel, neuRest)
    15. Next i
    16. Else
    17. Range("A1").Offset(j, 0).Value = einzel
    18. j = j + 1
    19. End If
    20. End Sub


    permutiert nur nach der 1. festen Zahl aber ich denke, da wirst du den rest drum herum bekommen
    Bis 8 gehts in Clickschnelle... bei 9 brauch er ne Weile bzw musst dann die ausgabeVariable "j" auch aus nem anderen Datentyp wählen

    Hey, vielen Dank erst mal für deine schnelle Antwort. Unglücklicherweise hilft mir deine Anregung nicht wirklich weiter. Die Permutationen funktionieren ja schon! Hilfreich wäre die Abbildung der Reihenfolge der Zahlen in den einzelnen Permutationen. Deswegen habe ich die einzelnen Ziffern der Permutationen auch in separate Zellen schreiben lassen.

    Warum das ganze:
    Es geht um die Möglichkeiten wie man etwas zusammenbauen kann. Die Zahlen sollen später durch die einzelnen Komponenten ersetzt werden. Danach werden dann mit Hilfe von Verbaubedingungen die Permutationen rausgeworfen die nicht möglich sind.

    Für irgendeine Idee wie man das mit der Reihenfolge anderst machen kann wie oben beschrieben wäre ich Dir sehr dankbar!

    Gruß Bo2k

    Ah OK.

    Also ich nehme mal an es soll dann vom Programm geprüft werden, ob oder ob nicht der zusammenbau so funkioniert?
    Dann sollte sowohl die Komponenten als auch diese Bedingungen nun schon in den Algorithmus/ Permutation integriert werden, ala exit for Anweisungen zum Beispiel.
    Weil:
    Ich weiß nicht wie schnell dein Code ist. Bei mir lief die Permutation von 9 Zahlen in ca 2,5min. Da ich annehme, daß keine riesigen Algorithmusoptimierungen mehr möglich sind (lasse mich aber gerne eines besseren Belehren) kannst du dir in etwa ausrechnen wie lange das ganze dann für 10 Zahlen (25min), 11 Zahlen(275min), usw dauert. und dann danach erst prüfen welche 80% der zig Millionen Möglichkeiten nicht Möglich sind ist wohl der falsche Weg.
    Also sollte man in meinen Augen diese Bedingungen direkt integrieren, um so Zweige, die nicht möglich sind direkt zu überspringen.

    Hallo!

    Ja das Programm prüft ob der Zusammenbau funktioniert. Die Bedingungen habe ich bereits in den Algorithmus integriert, da von Anfang an das Problem mit der Begrenzung der Zeilenanzahl bestand. Bei 9 Ziffern liegt man schon bei ca. 360.000 Permutationen, bei 10 ist mit 3,6 Mio Möglichkeiten die Grenze von 1 Mio Zeilen überschritten. Daher bildet das Makro nur "richtige" Reihenfolgen ab. Leider nur sehr langsam. Für 10 Ziffern benötige ich ca. 1,5 Stunden und die Zeit geht mit jeder weiteren Ziffer steil nach oben. Daher wollte ich versuchen zumindest so simple Dinge wie die Abbildung der Reihenfolge der Ziffern in der Permutation zu beschleunigen. Für die Prüfung der BEdingungen geht natürlich auch sehr viel Zeit verloren, da für jede einzelne Bedingung eine Schleife durchlaufen werden muss. Das Programm geht zwar direkt zur nächsten Permutation wenn eine Bedingung nicht erfüllt wird aber es kostet immer noch massig Zeit.
    Ziel waren wie gesagt bis zu 20 Ziffern aber langsam bezweifle ich, dass ein normaler Computer das bewerkstelligen kann.

    Leider habe ich nicht ganz so viel Ahnung vom Programmieren. Kann man eigentlich den Quellcode aus VBA im Excel auch in dem Programm Visual Basic verwenden und bringt das irgendwelche Vorteile in Bezug auf die Geschwindigkeit?

    Zur 2. Frage: Es sollte jede zulässige Kombination gefunden werden. Funktioniert ja auch aber halt nur mit max. 10 Ziffern

    Vielen Dank für Eure Hilfe...
    Gruß Bo2k

    nunja dann solltest Du die Bedingungen mal genau durch gehen und schauen wie Du sie sinnvoll mit der Permutation verknüpfst. Das ganze is dann weniger eine Frage der Programmiersprache, sondern eher die Sache, dass Du Dir richtig gedanken machen musst wie du durch einen guten Algorithmus nur solche Permutationen durchnimmst, die auch den Regeln entsprechen... ergo musst du zuerst mal Regeln erstellen. Dann brauchst du wohl auch keine Permutation von 20 Elementen, sondern vielleicht immer nur von 4 oder 5...
    Weil wenn ja zum Beispiel niemals die 7 neben der 8 sein darf reduziert das ja die möglichkeiten um einiges. Ergo.. erst die Regeln definieren und von da aus entsprechend in die Permutation starten.

    das ist ein graphentheoretisches problem: wegfindung im graphen.
    man kann die komponenten als knoten auffassen, und jede zusammensteck-möglichkeit mit einer anneren ist eine kante. und dann mit einer Tiefensuche alle Wege finden.
    im grunde stellt der vertig verknüpperte Graph alle Wege dar, und jeder mögliche vollständige Durchlauf ist eine Lösung.
    während es rel. einfach ist, eine, oder auch mehrere Lösungen zu finden, wüsste ich aber nicht, wie man mathematisch korrekt alle diese lösungen findet. Aber ich bin was sehr anneres als ein mathematiker, ist durchaus möglich bis wahrscheinlich, dass die auch die Findung aller lösungen ausbaldowert haben ;)

    Das problem hat aber mit Excel nix zu tun, und Tabellen und zellen helfen dabei herzlich wenig - bestenfalls zur Eingabe der (ziemlich vielen) parameter.

    ich glaub sogar fast, das Problem ist das Problem "topologische sortierung", und auch das ist performant lösbar, aber auch da weiißichnich, wie man alle möglichen korrekten reihenfolgen ermittelt.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

    Ne :)
    Tagesturnier mit -sagen wir mal 10 Spieler -, also jeder 2 Spiele.
    Aber ich möchte alle möglichen Paarungen "durchlaufen" lassen und mit einer Bewertung die beste Möglichkeit rausfinden.
    Dafür eben alle Möglichkeiten durchlaufen und stoppen bzw. speichern, wenn die beste sich ergibt.

    Ich bräuchte also die Zahlenreihe 1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10 in jeder möglichen Reihenfolge.
    Die jeweiligen Spieler hole ich mir während des Laufs als Verweise heraus und bewerte diese.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „HollyMcLane“ ()

Facebook
Telefonspende