[PHP] PHP sortieren - alle Möglichkeiten

Michamab

Also ich habe eine Array mit x natürlichen Integerzahlen. In einer Schleife will ich die Array nun immer wieder neu sortieren, soweit kein Problem, doch will ich alle Kombination zum sortieren einmal durchhaben, momentan mach ich das mit Zufallssortierung, allerdings da es sich um ein mathematisches Problem handelt, will ich nichts mit Zufall zu tuen haben. Kennt jemand einen Algorithmus der mein Problem löst ?

Bsp. :
Array {1, 2, 3}
=>
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

Willst du dein Zahlenarray permutieren? Dann schau mal hier (viel. ist was brauchbares dabei!?): http://www.google.com/search?hl=de&ie=ISO-8859-1&q=Permutation+PHP&btnG=Google+Suche&lr=lang_de

Michamab

Ja, sowas in der Art habe ich gesucht, das Problem ist bloß, dass ich da recht schnell nen TimeOut bekomme.

flenders

Wenn dein Array nicht meht allzu klein ist lässt sich das wohl aufgrund der vielen Lösungen - sizeof($array)! - wohl nicht vermeiden
Oder ab welcher Größe bekommst du den Timeout? Und was hast du mit dem Ganzen überhaupt vor

Bloops

Timeout in dem Skript auf z. B. 5 min hochsetzen:

ini_set('max_execution_time', '300');

Ist aber nicht gerade der sauberste Weg.

mfg,
Bloops

Michamab

Meine Array besteht "bloß" aus 21 Zahlen. Problem ist folgendes, ich brauche eigentlich nur immer die ersten 3 Zahlen für die Berechnung, es geht darum durchzutesten wie viele verschiedene Möglichkeiten es gibt, es diesen 21 Zahlen nach einer Bestimmten Formel eine Summe zu bilden.

flenders

Michamab schrieb:

Meine Array besteht "bloß" aus 21 Zahlen.

Du bist gut, da gibt es dann 21 Fakultät Permutationen => ca. 5,11*10^19

Michamab schrieb:

Problem ist folgendes, ich brauche eigentlich nur immer die ersten 3 Zahlen für die Berechnung, es geht darum durchzutesten wie viele verschiedene Möglichkeiten es gibt, es diesen 21 Zahlen nach einer Bestimmten Formel eine Summe zu bilden.

Da verstehe ich jetzt nicht so ganz, was du meinst

Hattest du schon Wahrscheinlichkeitsrechnung? Schau dir mal Variationen an (falls die Reihenfolge 'ne Rolle spielt, sonst Kombinationen). Also damit kannst du die Möglichkeiten rausbekommen. Beispiel:
Läufer: 1 - 21
Wieviele Möglichkeiten gibt es die ersten 3 Plätze zu belegen?

21!/(21 - 3)!

Mit freundlichen Grüßen

Tobsen

Ps: Weiß net, obs schon 'ne Funktion für die Fakultät gibt, sollte aber net sonderlihc schwer zu schreiben sein (kommt drauf an, bis wieviel das script mitmacht). Codemäßig müsste das dann ungefähr so aussehen Fak(21)/Fak(21-3)!...

Michamab

Hm, also ich glaub ihr habt mich nicht richtig verstanden, es ging um folgendes Problem:

2*a + 2*b + c = x

Nun will ich alle Kombinationen erfahren, mit denen man x errechnen kann, die Zahl 21 bezog sich auf die Anzahl der natürlichen Zahlen, die man für a, b und c verwenden kann.

Also 'ne richtig gute Lösung fällt mer grad net ein. Ich würde das mit 'ner rekursiven Funktion machen. Lösungsansätze findest du hier:

http://www.darmstadt.gmd.de/schulen/LICHTENBERGSCHULE/projekte/lkinfrr/lkinf08.htm

flenders

Also du hast ein Array mit 21 Zahlen, die verwendet werden dürfen und eine beliebige Zahl x (natürliche Zahl?) die das Ergebnis sein soll?

<?php
 $zahlen = range(0, 20); // Array, dass die zu verwendenden Zahlen enthält
 $x = 17;                // Ergebnis, das herauskommen soll
 foreach($zahlen as $a)
 {
  foreach($zahlen as $b)
  {
   // Gleichung nach c umstellen und schauen, ob das Ergebnis in $zahlen enthalten ist
   $c = $x - 2*$a - 2*$b;
   if(in_array($c,$zahlen)) echo "2*$a + 2*$b + $c = $x<br>";
  }
 }
?>

Michamab

Wunderbar, danke, funktioniert wunderbar
... hätte ich auch selber draufkommen können