Laden...

[erledigt] Wie programmiere ich einen performanten Bruteforce-Algorithmus?

Erstellt von Jonas007 vor 3 Jahren Letzter Beitrag vor 3 Jahren 1.220 Views
J
Jonas007 Themenstarter:in
37 Beiträge seit 2020
vor 3 Jahren
[erledigt] Wie programmiere ich einen performanten Bruteforce-Algorithmus?

Hallo liebe Community,

Ich habe bereits einen eher schlechten Brute Force Algorithmus programmiert, der ein Array so lange "mischt", bis es sortiert ist. Jedoch möchte ich jetzt einen guten Brute Force Sortieralgorithmus schreiben, welcher nicht zufällig mischt, sondern nacheinander alle Möglichkeiten, die es gibt probiert.
Ich habe es bereits mit vielen Ansätzen probiert, jedoch nicht geschafft. Auch im Internet bin ich leider nicht fündig geworden.

Ich hoffe, dass mir jemand weiterhelfen kann!
LG Jonas 😉

T
2.219 Beiträge seit 2008
vor 3 Jahren

Was ist den dein Ziel?
Sortierung generell gibt es zu Hauf Lösungen im Netz.
Was soll der Zweck eines Brute Force Sortierung sein?
Der Sinn einer Sortierung ist ja, dass man eine bestimmte Reihenfolge haben will.
Wenn du mit Permutation arbeiten willst, dann ergibt das Ziel der Sortierung keinen großen Sinn.
Aber ggf. fehlt uns der Kontext, den du hie nicht erwähnst.

Ansonsten gibt es für nomale Sortierungen genug Lösungen + fertige Lösungen in Array.Sort

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

J
Jonas007 Themenstarter:in
37 Beiträge seit 2020
vor 3 Jahren

Mein Ziel ist es Algorithmen besser zu verstehen und einfach etwas zu üben. Ich dachte mir ein Brute Force Algorithmus, sprich einfach alle Lösungen auszuprobieren, sollte einfach sein jedoch schaffe ich es nicht. Ich habe bereits viel effizienter Sortier Algorithmen gesehen, verstanden und selbst programmiert jedoch ist es bedauernd, dass ich so einen scheinbar einfachen Algorithmus nicht schaffe.

4.931 Beiträge seit 2008
vor 3 Jahren

Dein Algorithmus nennt sich Bogosort (und ist eher als Spaß zu verstehen).
Hast du denn schon den Bubblesort mal programmiert (denn diesen kann man, gerade in der einfachen Form, als Sortieren über alle Möglichkeiten bezeichnen)?

309 Beiträge seit 2020
vor 3 Jahren

Jedoch möchte ich jetzt einen guten Brute Force Sortieralgorithmus schreiben, welcher nicht zufällig mischt, sondern nacheinander alle Möglichkeiten, die es gibt probiert.

Das kannst du mit ein paar Schleifen selber zusammen bauen oder vielleicht hilft das: Enumerable.Zip Methode

J
Jonas007 Themenstarter:in
37 Beiträge seit 2020
vor 3 Jahren

Im Prinzip kann man mein Problem ziemlich vereinfachen: Ich suche eine Methode, welche alle Möglichkeiten einer Liste angibt:


public static int[,] Combinations(int[] arr)
{
    // Algorithmus
}

Die Augabe sollte dann ein 2D Array (Tabelle) sein, wo nacheinander alle Möglichkeiten der List aufgelistet werden.
Im Grunde genau das, was diese Website, die ich gerade gefunden habe erledigt: https://www.zum.de/Faecher/Materialien/gebhardt/stochastik/Kombin.html

Bsp:


int[] arr = new int[3] {1, 2, 3}
int[,] arr2D = Combinations;

// Ausgabe beim Durchlaufen des arr2D:
// 123
//132
//213
//231
//312
//321


Ich hoffe ihr versteht was ich versuche. Und bereits vielen Dank für die zahlreichen Antworten

J
Jonas007 Themenstarter:in
37 Beiträge seit 2020
vor 3 Jahren

Danke dir. Ich bin in diesem Beitrag auf den Johnson Trotter Algorithmus gestoßen, der mein Problem löst. Mit Hilfe dieses Grundalgorithmuses kann ich meine Idee umsetzen.

5.657 Beiträge seit 2006
vor 3 Jahren

Ich verstehe nicht, was das mit Sortierung zu tun haben soll. Sortieren bedeutet ja, die Werte in der Liste in eine bestimmte Reihenfolge zu bringen. Eine Permutation ist doch das genaue Gegenteil.

PS: "ein performanter Bruteforce-Algorithmus" ist eine Tautologie ein Widerspruch*, ich hoffe, das ist dir klar 😃

*Danke @witte

Weeks of programming can save you hours of planning

W
955 Beiträge seit 2010
vor 3 Jahren

Du meinst Paradoxon und nicht Tautologie oder?