Offtopic: ---> Sortieren durch Permutationen...

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Offtopic: ---> Sortieren durch Permutationen...

Beitrag von oren78 »

hallo ihr lieben,

sorry ist zwar etwas offtopic, aber vom thema ("sortieren") her doch irgendwie hierher einzuordnen:

angenommen wir haben eine liste von buchstaben: "bac",
wir erstellen nun in O(n!) Schritten alle Permutationen dieser liste, also:

1.) "abc"
2.) "acb"
3.) "bac"
4.) "bca"
5.) "cab"
6.) "cba"

wie lässt sich nun die wahrsscheinlichkeit, bzw. die daraus resultierende komplexität errechnen, wann wir
genau eine sortierte liste erhalten..?? im oberen fall, wäre das ja z.B schon in einem einzigen schritt, wenn
wir eine sortierte permutation starten...

kann mir da jemand ein hilfreichen tipp dazu geben ?? ein artikel in der aktuellen inforz hat mich auf dieses thema aufmerksam gemacht :-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: Offtopic: ---> Sortieren durch Permutationen...

Beitrag von Demmi »

Ich hab zwar den Inforz-Artikel noch nicht gelesen, aber ich würde mal sagen, dass man im Mittel nach n!/2 Schritten die sortierte Liste hat. Ich bin mir nicht sicher, ob es das ist was du hören wolltest...

Die nächste Frage ist dann auch noch, wie man erkennt ob die liste jetzt wirklich sortiert ist. Im Zweifelsfall geht man also zusätzlich nach jedem schritt nochmal durch die Liste durch und schaut ob element<element[i+1]. Das hätte dann nochmal die Komplexität n pro Durchlauf
Also hätte man im Mittel (n!/2)*n, vermute ich mal.

Ob das jetzt 100%ig richtig ist, kann ich nicht garantieren. Aber vielleicht gibt es dir ja nen neuen Denkansatz.
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

Benutzeravatar
sevenclev
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 19. Mai 2005 09:50
Wohnort: Wiesbaden

Re: Offtopic: ---> Sortieren durch Permutationen...

Beitrag von sevenclev »

Die Wahrscheinlichkeit hängt vom Algorithmus der die Permutationen erzeugt ab.
Wenn du zB Quicksort zum erzeugen von Permutationen benutzt, ist die Wahrscheinlichkeit für die sortierte Liste in erster Stelle 100%.
Wenn du einfach irgendwie Permutationen erzeugst, hat jede Stelle die gleiche Wahrscheinlichkeit.
Build a man a fire, and he'll be warm for a day.
Set a man on fire, and he'll be warm for the rest of his life.

SE: Design & Construction 2009/10 Tutor

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Offtopic: ---> Sortieren durch Permutationen...

Beitrag von oren78 »

Demmi hat geschrieben:Die nächste Frage ist dann auch noch, wie man erkennt ob die liste jetzt wirklich sortiert ist...
am genialsten wäre es natürlich, wenn man die permutation sortiert erzeugen könnte, aber das ist glaub ich nicht ohne weiteres möglich, oder irre ich mich hier ??

folgender code erzeugt zwar korrekte permutationen, allerdings mit einer rekursion in einer for() was sich natürlich enorm auf die komplexität auswirkt..
man kann die rekursion zwar eiliminieren, aber es bleibt bei der hässlichen O(n!)

Code: Alles auswählen

public class Permutation
{   	
   public static void main(String args[])
   {
	 Permutation obj = new Permutation();
		
	 obj.permuteString("", "87nero");
   }

   public void permuteString(String beginningString, String endingString )
   {	   
      if ( endingString.length() <= 1 )  System.out.println( beginningString + endingString );
      else
      {
         for ( int i = 0; i < endingString.length(); i++ )
         {
            try
            {
               String newString = endingString.substring( 0, i ) + endingString.substring( i + 1 );               
               permuteString( beginningString + endingString.charAt( i ), newString );               
            }
            catch ( StringIndexOutOfBoundsException exception )
            {
               exception.printStackTrace();
            } 
         } 
      } 
   } 
}
hat jemand vielleicht eine schönere alternative als die hier ?? :-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Yankee
Kernelcompilierer
Kernelcompilierer
Beiträge: 441
Registriert: 2. Jul 2004 00:05
Wohnort: Melbourne

Re: Offtopic: ---> Sortieren durch Permutationen...

Beitrag von Yankee »

oren78 hat geschrieben:
Demmi hat geschrieben:Die nächste Frage ist dann auch noch, wie man erkennt ob die liste jetzt wirklich sortiert ist...
am genialsten wäre es natürlich, wenn man die permutation sortiert erzeugen könnte, aber das ist glaub ich nicht ohne weiteres möglich, oder irre ich mich hier ??
Um die List zu sortieren, bräuchtest Du ja wieder einen Sortierungsalgorithmus.

Worauf willst Du eigentlich hinaus? Die Frage, wann voraussichtlich die sortierte Liste erzeugt wird, wurde Dir ja schon beantwortet.

Implementierungstechnisch würde ich nicht mit Strings, sondern char[] arbeiten, zumal Du die Länge jeder Permutation ja vorab kennst. Das sollte schon einmal einen deutlichen Geschwindigkeits- wenn auch nicht Komplexitätsgewinn erzielen.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Offtopic: ---> Sortieren durch Permutationen...

Beitrag von oren78 »

@ Yankee: danke für die hilfreiche info :-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Antworten

Zurück zu „Archiv“