Array mischen - aber gründlich!

[soundZ]

Hallo,

zum Theman "array mischen" gibt es ja einiges* hier zu finden.
Nun möchte ich aber ein Array so "gründlich" mischen, dass KEIN einziges Element nach dem Mischen an der Stelle ist (bzw. sein könnte), an der es vorher war. Jedes Element muss also ZWINGEND einen neuen Platz bekommen.

Wenn jemand eine Idee hat wär das super! Meine jetzige Lösung sieht so aus, dass die Mischfunktion so lange neu ausgeführt wird, bis o.g. Bedingung erfüllt ist - das scheint mir aber weder elegant, noch schnell.


*) Ich hätte mal wieder gleich hier suchen sollen und mir nich ne Mischfunktion selberschreiben sollen, die ich jetzt wieder übern haufen werfe.. naja.

[bokel]

Das Problem ist interessant.
Ein erster Ansatz könnte sein, erstmal beliebig zu mischen und dann zu prüfen, welche Positionen noch unverändert sind. Jetzt kannst du diese Elemente gegeneinander vertauschen, bis alle auf neuen Positionen sind. Auf die Art bleiben die korrekt gemischten Einträge auf jeden Fall korrekt gemischt. Könnte klappen, probiers mal.

Edit:
Ja, genau
Wenn du mehr als einen falsch positionierten Eintrag findest, dann könntest du einfach alle falschen Elemente jeweils zur Positionen des nächsten falschen Eintrags verschieben, quasi ein Ringtausch. Dann sind alle auf jeden Fall an neuen korrekten Positionen.
Es gibt nur einen Spezialfall, nämlich wenn nur ein Element falsch ist. Den musst du besonders behandeln. Du musst dann ein, eigentlich schon okayes Element finden, das du mit dem falschen Element vertauschen kannst, ohne die Unordnung zu zerstören.


mfg. r.

[e2e4]

Keine falschen Lorbeeren für mich

/**
 * Shuffles an array using the Fisher-Yates shuffle.
 */
Array.prototype.shuffle = function() {
    for (var i = this.length; --i; i>0) {
        var j = random( i  + 1 );
        var temp = this[ i ];
        this[ i ] = this[ j ];
        this[ j ] = temp;
    }
}
var toMix = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
toMix.shuffle();
trace(toMix) 

[bokel]

Eine andere Möglichkeit wäre es, immer nur erlaubte Vertauschungen durchzuführen. Eine Vertauschung ist erlaubt, wenn anschliessend beide Tauschpartner auf erlaubten Plätzen stehen. Dann muss man nur sicherstellen, dass alle mindestens einmal vertauscht worden sind.

@e2e4: Oder so

Edit:
Allerdings scheint es noch nicht ganz zu stimmen. Jedenfalls kann es anscheinend passieren, dass die letzte Zahl stehen bleibt. Ich schätze, es muss j = random(i) heissen, anstatt i+1


mfg. r.

[Alphanimal]

Idee:

Immer ein zufälliges Element in ein freies Feld in einem neues Array kopieren, ausser bei gleichem Index.

Hab jetzt eine knappe Stunde dafür gebraucht was ich in 20 Sekunden schreiben wollte:

PHP-Code:

a = ["a","b","c","d"]; //Ein-Array
ta = []; //Aus-Array
for(i=0;i<a.length;i++){
if(a[i]==undefined){ //Keine "undefined" erlaubt!
i = a.length; //Schleife abbrechen
}else if(i==a.length-1 && ta[i]==undefined){ //Letztes Element passt nicht! *
ta = []; //Neu anfangen: Aus-Array leeren, Zähler zurücksetzten
i = -1; // (-1 damit er am Schleifenanfang wieder auf 0 steht)
}else{ // Nix passiert, hier kommt das eigentliche Skript
do{
ti = random(a.length); //Zufälligen Ziel-Index erstellen
}while(ti==i || ta[ti]!=undefined); //wenn es die gleiche Position ist, oder das Feld nicht frei ist... neu erstellen
ta[ti] = a[i]; //Kopieren!
}
}
trace("result: "+ta); 


* Die ausnahme tritt dann auf, wenn alle Elemente gesetzt wurden, ausser das letzte, dieses sich aber an der gleichen Stelle wie das Ausgangs-Element befindet.
Wenn die Arrays länger sind kommt das selten vor. bei 2 Elementen gar nie!
Bei 3 Elementen kommt es schon öfter vor!
Er setzt dann zB. [0] auf [1], [1] auf [0], und dann is nix mehr frei für [2], weil das ja nur mehr [2] frei ist!

Wegen dieser Ausnahme hab ich auch so lang gebrauch!

So bitte! Gute nacht!

hier nochmal der Code in einer netten Funktion, ohne lästige Kommentare:

PHP-Code:

function shuffle_all(a){
var ta = [], i;
for(var i=0;i<a.length;i++){
if(a[i]==undefined){
return undefined;
}else if(i==a.length-1 && ta[i]==undefined){ //Letztes Element passt nicht!
ta = [];
i = -1;
}else{
do{
    ti = random(a.length);
}while(ti==i || ta[ti]!=undefined);
ta[ti] = a[i];
}
}
return ta;
} 


Edit:
Hier noch eine nette Prototype Methode:

Array.prototype.shuffleAll = function(){
	var ta=[], i;
	for(var i=0;i<this.length;i++){
		if(this[i]==undefined){
			return undefined;
		}else if(i==this.length-1 && ta[i]==undefined){
			ta = [];
			i = -1;
		}else{
			do{
				ti = random(this.length);
			}while(ti==i || ta[ti]!=undefined);
			ta[ti] = this[i];
		}
	}
	for(i in ta)this[i] = ta[i];
}

[e2e4]

@bokel:

*hmpfr* muß ich ja nochmal ran

Array.prototype.shuffle = function() {
    for (var i = this.length; --i; i>0) {
        var j = random(i+1);
        if (i == j) {
            ++i;
            continue;
        }
        var temp = this[i];
        this[i] = this[j];
        this[j] = temp;
    }
};
var toMix = [0, 1, 2, 3];
for (var i = 0; i<10; i++) {
    toMix.shuffle();
    trace(toMix); 
} 

[Alphanimal]

da kommt z.B. 0,2,3,1 raus!

0 darf nicht an erster stelle stehen weil jedes Element einen neuen Platz bekommen soll!

das is ja das Problem

Edit:
Ups mein Fehler...
Wenn das geshuffelte Array nochmals geshuffelt wird darf es das...

Könntest du mir verraten wie das Funktioniert?

[bokel]

Ah ok, jetzt passt es. Die for-Schleife würde ich aber etwas konventioneller formulieren,
for (var i = this.length-1; i>0; i--), das sollte genauso funktionieren.
mfg r.

[Alphanimal]

Was für eine Überlegung steckt da dahinter? Ich versteh den Code nicht...

[e2e4]

@bokel: Der Fisher-Yates-Shuffle lässt zu das Elemente nicht getauscht werden, da hatte ich nicht dran gedacht. Kommt aus dem Knuth das Teil...

@alpha: Einfach das zufällig ausgewählte Element immer an die in der Schleife aktuellen Position schieben und dabei sicherstellen dass das zufällig ausgewählte Element nicht mit dem gerade aktuellen übereinstimmt. Da die Position ja mit jedem Schleifendurchlauf kleiner wird, werden die verschobenen Elemente nicht mehr betrachtet.

[thebiz]

Hi.

Ich habe auch mal eine Mix-Methode verfasst.
Sieht den anderen etwas ähnlich.

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
b = ["anna", "ben", "chris", "dirk", "fred", "glen", "hans"];
//-----------------------------------------------------------------
Array.prototype.mix = function() {
    for (var i = 0; i < this.length; i++) {
        var alt = Math.round(Math.random() * (this.length - 1));
        var neu = Math.round(Math.random() * (this.length - 1));
        var wert = this[alt];
        this.splice(alt, 1);
        this.splice(neu, 0, wert);
    }
    trace(this);
};
//-----------------------------------------------------------------
a.mix();
b.mix(); 

[shorty]

also das is mal n wirklich "schöner" thread. kommt man sich ja vor, wie bei der Matheolympiade . gut, ich muss an der stelle aber erst noch einmal zur ursprünglichen aufgabe zurück kommen. wie soll es jetzt laufen, soll einfach nur sicher gestellt werden, das kein element nach dem mix-In an alter stelle steht, oder ist hier noch etwas anderes von belang? um zu meiner ersten idee zurück zu kommen, sprich: einfach nur 100%ig sicher stellen das die elemente des arrays in der positionierung, nach dem mix-In, deffinitiv != dem der vorherigen sind, würd ich es so machen.

PHP-Code:

var arrOrig:Array = new Array('0', '1', '2', '3', '4', '5');
// ----------------------------------------------------------
function fncReplace(arrToMix:Array) {
    arrToMix.push(arrToMix[0]);
    arrToMix.shift(arrToMix[0]);
    trace(arrOrig);
}
// ----------------------------------------------------------
fncReplace(arrOrig); 


* ich geh mal schweer davon aus, daß diese möglichkeit mit sicherheit die ist, an die jeder zuerst gedacht hat, aber hier werden doch deffinitiv alle elemente an eine andere position gesetzt, oder seh ich da was falsh? ausnahmen gibts natürlich auch hier, ist wie beim karten spielen, wenn ich nur eine karte habe, kann ich die ja logischerweise mit keiner anderen mischen, und darum müßen halt mind.2 elemente im array vorhanden sein.

... und jetzt ihr wieder

[bokel]

@thebiz: Ja, aber du stellst nicht sicher, dass kein Element am gleichen Platz bleibt. Dabei fällt mir ein: Sind die Elemente eigentlich alle verschieden?

@shortbymc: Stimmt, kein Element bleibt an seinem alen Platz, aber besonders gemischt sind sie auch nicht gerade, oder Wobei das als ein Fall durchaus passieren kann.

mfg. r.

[thebiz]

Wenn man Karten mischt, dann ist auch
die Wahrscheinlichkeit gegeben, dass alle
wieder an der gleichen Stelle sind.

[soundZ]

wow, hier hab ich ja 'was losgetreten! Vielen Dank auf jeden Fall für die vielen hilfreichen Antworten und Ideen.

@e2e4: Auch wenn ich Deinen Code erstmal überhauptnet verstanden hab, nachdem ich Deine Erklärung gefunden hab, war einiges klarer:-) Vielen Dank! Wenn nicht noch ne andere ganz tolle Idee auftaucht, dann hast Du wohl die "Matheolympiade" (zumindest aus meine Sicht) gewonnen:-)

@thebiz: Sehe ich das falsch und irre mich: Deine Mixfunktion mixt aber nur - sie schließt nicht aus, dass ein Element zufällig wieder auf der alten Position im Array landet - oder?
Ja, bei Mischen eines Kartenspieles kann das vorkommen - diesen Spezialfall und den Fall, dass eine oder mehrere "Karten" an gleicher Stelle liegen wie vorher wollte ich ja aber gerade ausschließen:-)

@Bokel ("Sind die Elemente eigentlich alle verschieden?"):
Ja, zum Glück! Sonst kann man ja wahnsinnig werden - insbesondere dann, wenn mehr als die Hälfte aller Elemente gleich ist *ggg*:-)

@shortybmc (ich geh mal schweer davon aus, daß diese Möglichkeit mit Sicherheit die ist, an die jeder zuerst gedacht hat):
Naja, ich hatte GANZ KURZ an sowas änliches gedacht: Erst mixen (änlich wie thebiz, und dann alles um eine Position verschieben - macht aber natürlich auch nicht wirklich Sinn - ich darf garnich daran denken, dass ich sowas Blödsinniges gedacht habe; Son Stuss:-)

Nochmal an Alle: Vielen, vielen Dank!

P.S.: Sorry, dass ich mich erst so spät wieder melde - heute nacht war das Forum aber plötzlich nichmehr zu erreichen:-(