Verfasst am: 20.06.2018, 21:09
Titel: Algorithmus für Permutation
Hallo,
Ich suche einen Algorithmus der genau das gleiche macht wie "perms" jedoch für mehr als nur ca. 10 Zahlen (ab 11 Zahlen bekomme ich eine Fehlermeldung das die maximale Anzahl überschritten wurde).
Es geht also um n aus n mit Beachtung der Reihenfolge ohne Wiederholung.
Vielleicht hat sich jemand von euch auch schon damit auseinander gesetzt und entsprechenden Algorithmus geschrieben und ist bereit ihn zu teilen. Ansonsten würde ich mich auch über Ansätze oder Hinweise freuen.
Dieser Algorithmus ist genau das was ich suche jedoch für einen nx1 oder 1xn Vektor (entweder oder). Versteht jemand diesen Code und weiß wie er zu modifizieren ist?
die Fehlermeldung bekommst du ja nicht, weil MATLAB keine Lust hat das zu machen, sondern weil der Speicher nicht ausreicht. Bei mir geht z.B.
perms(1:11)
gerade noch, benötigt aber 3,5 GB an Speicher.
perms(1:12)
würde dann rund 40 GB Speicher brauchen, und so viel hat man halt typischerweise nicht.
Warum willst du diese Matrix aufstellen bzw. was willst du damit machen?
die Fehlermeldung bekommst du ja nicht, weil MATLAB keine Lust hat das zu machen, sondern weil der Speicher nicht ausreicht. Bei mir geht z.B.
perms(1:11)
gerade noch, benötigt aber 3,5 GB an Speicher.
perms(1:12)
würde dann rund 40 GB Speicher brauchen, und so viel hat man halt typischerweise nicht.
Warum willst du diese Matrix aufstellen bzw. was willst du damit machen?
Grüße,
Harald
Ich muss im Zuge meiner Bachelorarbeit ein Programm schreiben welches es mir erlaubt eine Vorauslegung der Avionik eines Flugzeuges im Vorentwurf zu berechnen.
Dabei müssen sogenannte "Tasks" den "Modulen" zugeordnet werden und dies in jeder möglichen Kombination (um anschließend die beste auswählen zu können).
Die Zuordnung erfolgt anhand von zwei Vektoren, dem Modulvektor und dem Taskvektor. Dabei wird der Taskvektor vom ersten bis zum letzten Element durchgearbeitet und überprüft welchem Element er aus dem Modulvektor zugeordnet werden kann. Da die Module gewisse Ressourcen haben die von den Tasks verbraucht werden spielt es eine Rolle in welcher Reihenfolge die Tasks zugeordnet werden. Aus diesem Grund brauche ich alle möglichen Zuordnungen von "Tasks" zu "Modulen". Dementsprechend benötige ich alle möglichen Reihenfolgen der Elemente des Taskvektors (daraus ergeben sich dann alle möglichen Zuordnungen).
Diese Funktion müsste zunächst kompiliert werden. Die Erstellung solch riesiger Matrizen benötigt auch einige Zeit.
Gruß, Jan
Hallo Jan,
das hört sich super an. Wie man vielleicht heraus lesen kann bin ich ein ziemlicher Anfänger was den Umgang mit Matlab und Programmieren generell betrifft. Ich weiß leider nicht was "Diese Funktion müsste zunächst kompiliert werden" bedeutet. Die entsprechende Datei aus dem Link habe ich mir bereits heruntergeladen und versucht auszuführen. Ich erhalte dann folgende Fehlermeldung "Attempt to execute SCRIPT VChooseKO as a function". Ich habe ebenfalls in anderen Foren schon etwas über diese Fehlermeldung gelesen kann damit jedoch aufgrund meiner fehlenden Programmierkenntnissen nichts anfangen.
die Anzahl der Kombinationen kann extrem hoch sein. Ein Durchtesten aller Kombinationen ist daher oft nicht möglich. Dann sollte man erwägen, das als Optimierungsproblem aufzusetzen.
Verfasst am: 22.06.2018, 10:53
Titel: Re: Algorithmus für Permutation
Hallo FrAnKy_0,
Zum "Kompilieren" muss man zunächst einen C-Compiler installieren, z.B. MinGW. Informationen dazu findest Du im Netz und in der Dokumentation von Matlab.
Dann:
Danach kann die Funktion genauso aufgerufen werden, wie andere Matlab Funktionen.
Die Verwendung von Integertypen wie UINT8 kann die Verarbeituing deutlich bescghleunigen und den Speicherbedarf auf ein Achtel reduzieren. Trotzdem werden die Outputs schnell gigantisch groß. Ob solche Brute-Force-Ansätze sinnvoll sind, muss man im Einzelfall abwägen.
Danke Jan, es hat alles funktioniert.
Wie du schon sagtest werden die Outputs extrem groß sodas mein Rechner auch hier versagt.
Ich würde gerne deine Datei (VChooseKO) so umschreiben das sie mir nicht alle Kombinationen aufeinmal berechnet und ausgibt, sondern mir jede Kombination einzeln ausgibt.
D.h. die Funktion soll anfangen zu rechenen und sobald sie die erste Lösung hat mir diese Ausgeben und sich gleichzeitig merken an welcher "Stelle" sie war damit sie dann im nächsten schritt dort weiter macht. Die alte Kombination soll dann durch die neu berechneten überspeichert werden. Dann soll mir die neu berechnete ausgegeben werden. Ich denke so kann ich den großen Speicherbedarf umgehen.
Ich hoffe es ist verständlich was ich machen möchste (alle Lösungen einzeln ausgeben und die neu berechnete soll immer die davor berechnete überspeichern).
Könntest du mir bitte entsprechende Stelle in deinem Code nennen die ich dafür verändern muss.
VChooseKO ist eine optimierte C-Funktion. Mit dem Ändern einer einzelnen Zeile ist es da nicht getan. Die Funktion wurde mit dem Ziel geschrieben, möglichst große Permutations-Matrizen effizient zu berechnen. Du hast aber nun ein anderes Ziel, bei dem es zwar auch um Permutationen geht, aber eben nicht alle am Block benötigt werden. Dann würde VChooseKO am Ziel vorbei schießen.
Das ist genau das was ich benötigt habe um mein Problem zu lösen.
Danke, danke, danke!
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS