Algorithmus: Liste umsortieren

Royal_Flush · 22. Januar 2011

Hi,

Ich bin auf der Suche nach einem Algorithmus, der folgendes bewerkstelligt: Eine Liste (eig. Array) soll umsortiert in eine andere Liste übernommen werden. Dabei ist folgendes zu beachten:
1. Der Vorgang muss umkehrbar sein, er darf somit nicht zufallsbasiert sein.
2. Alle Bestandteile der alten Liste müssen genau einmal in der neuen Liste vorhanden sein.
3. Die Umsortierung sollte nicht zu regelmäßig sein (also nicht: "Ab der x-ten Position anfangen und dann normal weiter" oder "Rückwärts")
4. Das Verfahren muss für jede beliebige Listenlänge funktionieren

Wünschenswert wäre eine Abhängigkeit von einer Zahl. Das ist aber nur das Zuckerl. :-D

Ich hoffe, jemand findet eine Lösung

Gruß
Royal

PS: Auch die Leute, die keine Ahnung von Informatik haben, sind herzlich eingeladen mitzuraten. Ich habs extra verständlich formuliert

Tommy · 22. Januar 2011

Hmm, also geht es gar nicht ums sortieren sondern einfach nur ums "durcheinander bringen"?

1) umkehrbar ist kein problem - man muss nur seine umsortierschritte nochmal rückwärts durchlaufen.
2) sollte auch kein Problem darstellen
4) sollte auch unproblematisch sein

würd da jetzt so ran gehen, dass deine eingegebene Zahl die Anzahl der Sortierschritte angibt, bei denen immer 2 Mitglieder vertauscht werden (im einfachsten Fall ... kann man natürlich auch komplexer machen)

eh es jetzt an den Algorithmus geht, müsste noch geklärt werden was "regelmässig" ist ... irgend eine Regelmässigkeit muss da rein, da ja kein Zufall gewünscht ist und es zudem umkehrbar sein soll

tja als trivales Beispiel nehmen wir einmal den Listeneinträg der dem Schleifenzähler für die Sortierschritte entspricht und als zweiten vielleicht irgend eine Kombination aus Schleifenzähler, Anzahl der Listeneinträge, modulo usw. ... sei einfach kreativ - Hauptsache du bleibst in den Grenzen deines Arrays. Die Listeneinträge dann entsprechend tauschen und zum nächsten Schritt weiter. Für die Umkehrung dann einfach rückwärts alle Schritte wiederholen und du hast dein Ausgangsarray.

Royal_Flush · 22. Januar 2011

Aber ist es bei deinem Vorschlag nicht so, dass ein Eintrag mehrmals kopiert werden kann? Könntest du mal ein Codebeispiel (C++, C#, Java oder Pseudocode) posten?

Tommy · 23. Januar 2011

Royal_Flush schrieb:
Aber ist es bei deinem Vorschlag nicht so, dass ein Eintrag mehrmals kopiert werden kann?

kann durchaus passieren, je nachdem wie du deine Listeneinträge auswählst ... ist aber nach deiner Beschreibung auch nicht verboten. Hier mal ein kurzes Beispiel in Pseudo-Java-Code:

Code:

public class test {
	
	public static List<String> array; 

	public static void encode(int count) {
		for(int i=0;i<count;i++) shuffle(i); //x mal umsortieren
	}
	
	public static void decode(int count) {
		for(int i=count-1;i>=0;i--) shuffle(i); // zurücksortiern
	}
	
	public static void shuffle(int i){
		int index = Math.round(((i%3)+1)*(array.size()-i)/3); //Algorithmus für zweiten Listeneintrag (verbesserungswürdig ;))
		String first = array.get(i), second = array.get(index); //Inhalte merken
		array.set(i, second);array.set(index, first); //Listeneinträge vertauschen 
	}
	
	public static void show() {
		for(String s : array) System.out.print(s + " ");System.out.println(); //Array anzeigen 
	}
	
	public static void main(String args[]){
		array = Arrays.asList("Hallo Welt! Das ist ein schneller Test. A B C D E F G H I J K".split(" "));show();
		encode(5);show();decode(5);show();
		encode(7);show();decode(7);show();
		encode(10);show();decode(10);show();
		encode(13);show();decode(13);show();
	}
}

Hab den Code nicht ausprobiert (deswegen "Pseudo") ... außerdem muss er an diversen Ecken noch ausgebessert werden. Welche Listeneinträge nun getauscht werden, müsstest du nochmal überarbeiten (hab da einfach aus dem Bauch heraus irgend eine Formel gebastelt) ... du bist da übrigens nicht auf 2 Einträge beschränkt - kannst wenn du willst munter durchtauschen.

Royal_Flush · 23. Januar 2011

Ah, jetzt verstehe ich, was du meinst. Das ist natürlich auch eine Möglichkeit. Ich war bisher darauf fixiert, die Einträge in einer bestimmten Reihenfolge in die Liste zu kopieren. Aber Einträge einfach untereinander vertauschen, darauf wär ich nicht gekommen. Dabei ist es eigentlich ganz logisch. Danke.

Anti_Held · 25. Januar 2011

Ich schreib auch mal hier rein , da ich keine Lust habe einen völlig neuen Thread zu machen.

Ich bin gerade dabei im Dienste der Schule ein kleines Zahlenratenspiel mit Java Skript zu machen. Das Programm sucht eine Zahl ziwschen 1 und 100 aus und hilft dem Spieler nur mit Tipps wie "Zahl zu klein" etc...

Dabei werden die Versuche mitgezählt und am Ende wird dem Spieler auch mitgeteilt wie viele Versuche er hatte. Soweit so gut, aber ich will noch das Extra ,dass wenn der Spieler z.b. 1 Versuch gebraucht hat dann eine Nachricht kommt wie "Sie sind ein Genie".
Allerdings bekomm ich das nicht hin und außerdem lässt das Programm die " Abbrechen " Funktion nicht zu.

Wäre nett wenn mir jemand helfen kann. Ich benutze den Html Editor zum scripten.

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title></title>
<meta name="author" content="Marc">
<meta name="editor" content="html-editor phase 5">
</head>
<body text="#000000" bgcolor="#C0C0C0" link="#FF0000" alink="#FF0000" vlink="#FF0000">

 <p></p>
  <p></p>
<div align="center"><h1>Zahlenratespiel</h1> </div>
 <p></p>
<div align="center">Die Regeln : <p></p>
Es wird eine Zahl zwischen 1 und 100 generiert. Sie raten.<p></p>
Am Ende werden ihnen ihre Versuche angezeigt</div>

<script language="JavaScript">


</script>
<noscript></noscript>

<form>
<div align="center"> <input type ="button" value= " Game" onClick = " zahlen () " > </div>

</form>
</body>
</html>
</body>
</html>

Ich hatte mir gedacht noch eine Variable zu erstellen die sobald der Spieler die Zahl hat auf 1 gesetzt wird. Sobald diese Variable dann 1 ist wird eine do/while Schleife benutzt, in welcher erst geguckt wird wie hoch die Zahl der Versuche ist. Dann wird je nach welcher If Funktion ein " Alert " ausgeführt und der Spieler bekommt sowas gesagt wie " Bla Bla Sie sind ein Genie " . Nach dieser Message wird die Variable die vorher 1 war wieder auf 0 gesetzt und die Schleife beendet.

Allerdings bekomm ich dass so nicht hin . ( Ich hatte zwar ein Versuch aber der ist futsch ...)

Mfg

benedikt · 6. Februar 2011

Ich hab selbst auch nicht soviel Ahnung von JS, ich hab aber auf jeden fall mal den HTML - Code aufgeräumt (konnte der wirklich von irgendeinem Browser angezeigt werden?:ugly

Code:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
  <head>
    <title>Zahlenratespiel</title>
    <meta name="author" content="Marc">
    <meta name="editor" content="html-editor phase 5">
    <script type="text/javascript">
          <!--
            function zahlen () {
                var eingabe,zufall,anzahl;
                zufall = Math.ceil(Math.random() * 100);
                
                anzahl = 0;
                do {
                    eingabe = window.prompt("Bitte raten:", "");
                    
                    if (eingabe < 1 || eingabe > 100)
                        { alert ("Die gesuchte Zahl liegt zwischen 1 und 100 ! "); }
                    else if (eingabe < zufall)
                        { alert ("zu klein"); }
                    else if (eingabe > zufall)
                        { alert ("zu groß"); }
                        
                    anzahl++;
                } while (zufall != eingabe);
                
                alert ("Richtig\nSie haben " + anzahl + " Versuche gebraucht!");
                
                if (anzahl == 1)
                    { alert("Sie sind ein Genie!"); }
            }
        //-->
    </script>
  </head>
  <body text="#000000" bgcolor="#C0C0C0" link="#FF0000" alink="#FF0000" vlink="#FF0000">
        <br><br>
        <h1 align="center">Zahlenratespiel</h1>
        <br><br>
        <p align="center"> Die Regeln :<br><br>Es wird eine Zahl zwischen 1 und 100 generiert. Sie raten.<br>Am Ende werden ihnen ihre Versuche angezeigt.</p>

        <br><br>
        <p align="center"<button onClick="zahlen ();">Game</button></p>
        
        <br><br>
        <noscript><p align="center"><b>Mit JavaScript könnte diese Seite sogar funktionieren!^^</b></p></noscript>
    </body>
</html>

Ich weiß selber auch nicht ob und wie du das Abbrechen beim alert() erkennen kannst, du könntest natürlich bei einer leeren Zeichenkette (-> while (zufall != eingabe && eingabe != ""); abbrechen.

Ich hatte mir gedacht noch eine Variable zu erstellen die sobald der Spieler die Zahl hat auf 1 gesetzt wird. Sobald diese Variable dann 1 ist wird eine do/while Schleife benutzt, in welcher erst geguckt wird wie hoch die Zahl der Versuche ist. Dann wird je nach welcher If Funktion ein " Alert " ausgeführt und der Spieler bekommt sowas gesagt wie " Bla Bla Sie sind ein Genie " . Nach dieser Message wird die Variable die vorher 1 war wieder auf 0 gesetzt und die Schleife beendet.

Wie bitte? Der Text ist für mich dann doch unverständlich, sorry.

Suche

Suche

Algorithmus: Liste umsortieren

Royal_Flush

Vertrauter

Tommy

Hausvetter

Royal_Flush

Vertrauter

Tommy

Hausvetter

Royal_Flush

Vertrauter

Anti_Held

Freund des Hauses

benedikt

Neuankömmling

Ähnliche Themen