Array-Permutationen?

30 views
Skip to first unread message

Stefan Weiss

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
Hi,

kennt jemand vielleicht eine halbwegs elegante Methode, den Inhalt
eines (eindimensionalen) Arrays zu durchmischen? Also zB von
[1,2,3,4,5,6,7,8,9,10] in [4,3,9,5,10,6,8,2,7,1].

Folgende Methode, die einen int-Array von 1 bis (cities) liefert,
funktioniert zwar, ist aber wenig elegant:

function generateRandomRoute(cities) {
var randomRoute = new Array();
var straightArray = new Array();
for (var i = 1; i <= cities; i++) {
straightArray[i-1] = i;
}
for (var i = 0; i < cities; i++) {
randomIndex = Math.floor(Math.random()*(straightArray.length-i)) + i;
randomRoute[i] = straightArray[randomIndex];
straightArray[randomIndex] = 0;
straightArray.sort();
}
return randomRoute;
}

cheers & tnx,
stefan

Ralf Beutler

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
hi stefan,

"Stefan Weiss" <der....@gmx.net> schrieb

> kennt jemand vielleicht eine halbwegs elegante Methode, den Inhalt
> eines (eindimensionalen) Arrays zu durchmischen? Also zB von
> [1,2,3,4,5,6,7,8,9,10] in [4,3,9,5,10,6,8,2,7,1].


mal eins zum ausprobieren:

<SCRIPT LANGUAGE="JavaScript" TYPE="text/javascript">
<!--
var zahlen = new Array();
var string="";
// array mit zahlen füllen
for(i=1; i <=20; i++)
zahlen[i-1] = i;
// vertauschen
for(z=0; z < zahlen.length*10; z++){
zf1 = Math.floor(Math.random()*zahlen.length);
zf2 = Math.floor(Math.random()*zahlen.length);
merke = zahlen[zf1];
zahlen[zf1] = zahlen[zf2];
zahlen[zf2] = merke;
}
// Ausgabe
for(z=0; z < zahlen.length; z++)
string += (z+": "+zahlen[z]+"\n");
alert(string);
// -->
</SCRIPT>

br | rb
--
media connexion GmbH . agentur für digitale medien: www.mediaconnexion.de
JavaScript-FAQ: www.mintert.com/javascript/de.comp.lang.javascript.html
nur für fans: http://go.to/trekki
special event: http://www.luftikunst.de

Stefan Weiss

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
Hi,

Ralf Beutler <rbeu...@mconnexion.com> schrieb:
> mal eins zum ausprobieren:
>
> <SCRIPT ...

Danke für deine Antwort. Ist keine schlechte Idee, das. Die Frage
ist, ob das Ergebnis "zufällig genug" ist. Ich weiß, das kommt auch
auf die Anwendung an, aber der Grad der Zufälligkeit wird, wenn ich
das Script richtig verstehe, von der Zahl 10 in

> for(z=0; z < zahlen.length*10; z++){

bestimmt. Also so, daß bei n Elementen im Array 10n mal zwei
Zahlen vertauscht werden. Ist das ein Erfahrungswert oder irgendwo
abgeleitet?

Dann ist da noch die Frage der Performance. Ich fürchte, daß meine
Variante durch das n-fache Sortieren des Arrays nicht besonders
effizient ist. Ich bin da kein Fachmann, aber deine Variante könnte
für größere n problematisch werden (die Berechnung dieses Zufalls-
Arrays wird einige tausend mal durchgeführt).

Wie siehst du das?


cheers,
stefan


PS: Das Ganze werde ich später noch in eine andere Sprache mit besserer
Performance umschreiben (C++?), aber fürs erste Entwickeln ist JS ganz
angenehm, weil ich nicht ständig compilieren muß.

Thomas Fischer

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
Hallo,

Stefan Weiss <der....@gmx.net> schrieb:
>
> kennt jemand vielleicht eine halbwegs elegante Methode, den Inhalt
> eines (eindimensionalen) Arrays zu durchmischen?

Das ist das schnellste (eleganteste) was mir einfällt ;-)

function arrayShuffle(){
/* copyright 2000, tool42.com - don't remove this comment */
var randArr =new Array(), i;
for(i=0; i <this.length; i++){
randArr[i] =new Number(Math.random());
randArr[i].content =this[i];
}
randArr.sort();
for(i=0; i <randArr.length; i++){
this[i] =randArr[i].content;
}
}
Array.prototype.shuffle =arrayShuffle;
delete arrayShuffle;


// TEST:
array =new Array();
for(var i=0; i<25; i++) array[i] =i;
array.shuffle();
document.write(array.join("<br>"));


salute
Thomas Fischer (derdreiviertelvorzwölfte)


Ralf Beutler

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to

"Stefan Weiss" <der....@gmx.net> schrieb im Newsbeitrag
news:8ji329$38du$1...@www.univie.ac.at...

> Hi,
>
> Ralf Beutler <rbeu...@mconnexion.com> schrieb:
> > mal eins zum ausprobieren:
> >
> > <SCRIPT ...
>
> Danke für deine Antwort. Ist keine schlechte Idee, das. Die Frage
> ist, ob das Ergebnis "zufällig genug" ist.
wie zufällig ist der Zufall?

> Ich weiß, das kommt auch
> auf die Anwendung an, aber der Grad der Zufälligkeit wird, wenn ich
> das Script richtig verstehe, von der Zahl 10 in

du kannst ja auch das array von unten nach oben durchlaufen und den Wert an
der i-ten Stelle mit einem beliebigen anderen Wert tauschen. Das halte ich
dann auch für die bessere Variante.

> Ich bin da kein Fachmann, aber deine Variante könnte
> für größere n problematisch werden (die Berechnung dieses Zufalls-
> Arrays wird einige tausend mal durchgeführt).

problematischer dürfte eher werden, ein array mit sagen wir 6000 Elementen im
Speicher zu halten.
Bei 20 000 stürzt der ie ab ;-)
du kannst ja mal die Zahl bei i schritt für Schritt erhöhen.

bei 6000 Elementen dauerte das vertauschen ca. 170 ms (bei mir)
PII - 350 / 128 MB RAM

ich poste mal eine Weiterentwicklung:


<SCRIPT LANGUAGE="JavaScript" TYPE="text/javascript">
<!--
var zahlen = new Array();
var string="";

// array füllen
for(i=1; i <=2000; i++)
zahlen[i-1] = i;

var jetzt = new Date();
var begin = jetzt.getTime();
// vertauschen
for(z=0; z < zahlen.length; z++){
zf = Math.floor(Math.random()*zahlen.length);
merke = zahlen[z];
zahlen[z] = zahlen[zf];
zahlen[zf] = merke;
}
var jetzt = new Date();
var end = jetzt.getTime();


// Ausgabe
for(z=0; z < zahlen.length; z++)
string += (z+": "+zahlen[z]+"\n");

alert("Das vertauschen dauerte höchstens "+(end-begin)+" Millisekunden");
alert(string);
// -->
</SCRIPT>

Hatto von Hatzfeld

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
Stefan Weiss <der....@gmx.net> schrieb:

> kennt jemand vielleicht eine halbwegs elegante Methode, den Inhalt
> eines (eindimensionalen) Arrays zu durchmischen? Also zB von
> [1,2,3,4,5,6,7,8,9,10] in [4,3,9,5,10,6,8,2,7,1].

function RndSort(a,b) { return Math.random()-.5; }
s=new Array(1,2,3,4,5,6,7,8,9,10);
s.sort(RndSort);

Elegant genug? :-)

Geht allerdings m.W. nur ab JavaScript 1.1. Und die Performance könnte
bei sehr großen Arrays deutlich suboptimal sein. Getestet habe ich es
mit meinem NN 4.61.

Grüße,
Hatto

--
*********************************** _- / =/
* Unterwegs auf 8 oder 10 Rollen * _- / . o\;,._
* de.rec.sport.inlineskating * _- (__________)
*********************************** - (_)(_)(_)(_)

Ralf Beutler

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
Hi Thomas,

"Thomas Fischer" <Thomas....@tool42.com> schrieb
> Hallo,


>
> Stefan Weiss <der....@gmx.net> schrieb:
> >
> > kennt jemand vielleicht eine halbwegs elegante Methode, den Inhalt
> > eines (eindimensionalen) Arrays zu durchmischen?

> // TEST:
> array =new Array();
> for(var i=0; i<25; i++) array[i] =i;
> array.shuffle();
> document.write(array.join("<br>"));

interessiert mich jetzt brennend,
kann man folgendes einfügen und liefert es brauchbare Ergebnisse?
<snip>
var jetzt = new Date(); // eingefügt
var begin = jetzt.getTime(); // eingefügt

array.shuffle();

var jetzt = new Date(); // eingefügt
var end = jetzt.getTime(); // eingefügt

document.write("Das vertauschen dauerte höchstens "+(end-begin)+"
Millisekunden<br>");
document.write(array.join("<br>"));
</snip>

wenn ja, dann dauert das von dir gepostete im ie etwa 4mal so lange wie mein
zuletzt gepostet und im NN ist es Faktor 10.
Frage:
Ist das von dir gepostete Verfahren stabiler als meins (bezüglich
Zufälligkeit)?
Wenn ich richtig sehe, gibt es dann 2 Arrays der Länge n. Wie sieht es dann
mit dem Speicherverbrauch bei n*10^3 aus?

Thomas Fischer

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
Ralf Beutler <rbeu...@mconnexion.com> schrieb:

>
> wenn ja, dann dauert das von dir gepostete im ie etwa 4mal so
> lange wie mein zuletzt gepostet und im NN ist es Faktor 10.

Nagut, man muß auch mal verlieren können ;-)

> Ist das von dir gepostete Verfahren stabiler als meins (bezüglich
> Zufälligkeit)?

Wahrscheinlich nochnichteinmal daß :..(
da bei dir mitunter zwei- und dreifach Vertauschungen stattfinden

salute
Thomas Fischer (derdreiviertelvorzwölfte)

Thomas Fischer

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
Ralf Beutler <rbeu...@mconnexion.com> schrieb:

>
> ich poste mal eine Weiterentwicklung:
>
> [... perfektes Script ...]

Nach dem ich schon den Performance-Wettkampf verloren
habe, wenigstens noch ein Versuch den OOP-Schönheitswettbewerb
zu gewinnen ;-)


function arrayShuffle(){
var i, tmp, rand;
for(i =0; i < this.length; i++){
rand = Math.floor(Math.random() *this.length);
tmp = this[i]; this[i] = this[rand]; this[rand] =tmp;
}
}
Array.prototype.shuffle =arrayShuffle;
delete arrayShuffle;


// T E S T :

var i, array =new Array();
for(i=0; i <5000; i++) array[i] =i;
var time =new Date();
array.shuffle();
time =new Date() -time;
document.write("time: " + time +"<br><br>" +array.join(", "));


salute
Thomas Fischer (derdreiviertelvorzwölfte)


Hatto von Hatzfeld

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
Ralf Beutler <rbeu...@mconnexion.com> schrieb:
> Hi Thomas,

>
> dann dauert das von dir gepostete im ie etwa 4mal so lange wie mein
> zuletzt gepostet und im NN ist es Faktor 10.

Nur als ergänzende Info:

Bei meinem NN 4.61 für Linux habe ich gemessen, dass Deines ca. 10- bis
20-mal so schnell ist wie Thomas' Script (bei großen Arrays ca. 20-mal).
Mein Zweizeiler liegt dazwischen und ist ca. 5-mal schneller als Thomas'
Script.

Ciao,
Hatto

--
Achtung!!! Achtung!!! Ganz gefährlicher E-Mail- und Usenet-Virus im
Umlauf!!! Er ist an einer Häufung von Ausrufezeichen zu erkennen!!!
Diese dürfen keinesfalls gelesen werden!!! Sonst wird Ihre Festplatte
gelöscht!!! Infos: http://www.salesianer.de/util/viruswarnung.html

Thomas Fischer

unread,
Jun 30, 2000, 3:00:00 AM6/30/00
to
Hatto von Hatzfeld <ha...@salesianer.de> schrieb:

>
> Bei meinem NN 4.61 für Linux habe ich gemessen, dass Deines ca. 10- bis
> 20-mal so schnell ist wie Thomas' Script (bei großen Arrays ca. 20-mal).
> Mein Zweizeiler liegt dazwischen und ist ca. 5-mal schneller als Thomas'
> Script.

Jaja, hack nur weiter auf mir rum, ich ahnte, daß da
noch mal was kommt wegens des "ersetze()"-Tunings %-)

salute
Thomas Fischer (derdreiviertelvorzwölfte)


Stefan Weiss

unread,
Jul 1, 2000, 3:00:00 AM7/1/00
to
Danke an alle!

Da waren ja massig neue Anregungen dabei, und elegant waren sie auch
noch. Wenn ich dazukomme, mache ich noch Tests zur Standardabweichung,
damit könnte man dann die Zufälligkeit genauer überprüfen.

cheers,
stefan

Marek Mänd

unread,
Jul 1, 2000, 3:00:00 AM7/1/00
to
Stefan Weiss <der....@gmx.net> wrote

> PS: Das Ganze werde ich später noch in eine andere Sprache mit besserer
> Performance umschreiben (C++?), aber fürs erste Entwickeln ist JS ganz
> angenehm, weil ich nicht ständig compilieren muß.

Na dann schreibe es in VBScript ... Hast später viel mehr weniger Arbeit
als bei JavaScript -> C Konversion ....
Und BASIC lässt sich auch interpretieren ....

btw von Zufälligkeit.
Mein Pokerspiel war ursprünglich für ms-dos
mit Turbo Pascal7 geschrieben. Bei jede start des Spieles
bakam ich immer dieselben Karten .... Ich weiss aber nicht wie
random bei js funzt ... Vielleicht kannst du auch aktuelle Zeit
in millisekunden für "Zufälligkeit" benuzten ...
--
Marek Mänd aus Estland.
http://my.tele2.ee/cadorsoft/products/cdr_js_eventcalc.html
http://my.tele2.ee/cadorsoft/cdr_js_pkb


Ralf Beutler

unread,
Jul 3, 2000, 3:00:00 AM7/3/00
to
Hi Thomas,

konnte Freitag leider nicht länger mitlesen.
"Thomas Fischer" <Thomas....@tool42.com> schrieb


> Nach dem ich schon den Performance-Wettkampf verloren
> habe, wenigstens noch ein Versuch den OOP-Schönheitswettbewerb
> zu gewinnen ;-)

herzlichen Glückwunsch dazu ;-)

eine Nachfrage habe ich noch. Habt ihr mal Tests gemacht, wieviel
Speicherplatz ein array der länge n belegt?
Schließlich sollte ein array irgendwie im RAM bleiben, oder?

Thomas Fischer

unread,
Jul 3, 2000, 3:00:00 AM7/3/00
to
Hallo,

Ralf Beutler <rbeu...@mconnexion.com> schrieb:


>
> eine Nachfrage habe ich noch. Habt ihr mal Tests gemacht, wieviel
> Speicherplatz ein array der länge n belegt?
> Schließlich sollte ein array irgendwie im RAM bleiben, oder?

Bei mir (128MB) hat IE locker bis 1.000.000 Elemente des
Types "number" mitgemacht (hab dann aufgehört, man muß ja auch
arbeiten), NN hat zwischen 100.000 und 500.000 irgendwann
angefangen auszulagern.

Solange du nicht vorhast, die Main-Data-Base des Bundesamtes
für Statistik in JS zu programmieren, solltest Du eigentlich
damit auskommen ;-)

salute
Thomas Fischer (derdreiviertelvorzwölfte)


Reply all
Reply to author
Forward
0 new messages