Array.shuffle

[SteveStall]

Hi there,

 

I'm looking for a way to shuffle an array. It seems not to be working write. The only way I had to return all the length of the array was by increasing the initial value of var i in the for cycle. It just doesn’t seem correct for me. Another thing is that this way it often repeats an ascendant  sequence:

 

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Array.prototype.shuffle = function () {
    var newArray:Array = this;
    for (i = 3; i < this.length; i++) {
        this[i] = newArray.splice (Math.floor (Math.random () * (newArray.length)), 1);

    }

    delete newArray
};

var firstArray:Array = new Array (1, 2, 3, 4, 5, 6);
firstArray.shuffle ();
trace (firstArray);

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Thanks in advance

Steve Stall

[perry]

I´m using this code (not quite elegant, but it works)

 

Array.prototype.shuffle = function() {

 

 for (i=0; i<this.length; i++) {
  myFlag = String.fromCharCode(Math.floor(Math.random()*(255-33)+32));
  this[i] = myFlag+this[i];
 }
 
 this.sort();
 
 for (i=0; i<this.length; i++) {
  this[i] = String(this[i]).substring(1, (this[i]).length);
 }
 
 return this;
 
}

"SteveStall" <peter...@oniduo.pt> schrieb im Newsbeitrag news:ddi01m$b9o$1...@forums.macromedia.com...

[Rothrock]

You should try searching the forums. This is a frequent topic which has a nice
solution.

Array.prototype.shuffle = function() {
for (var ivar = this.length-1; ivar>=0; ivar--) {
var p = random(ivar);
var t = this[ivar];
this[ivar] = this[p];
this[p] = t;
}
};

myArray=[0,1,2,3,4,5];
myArray.shuffle();

[NSurveyor]

Wouldn't this work for shuffling as well?

myArray.sort(function(){return (random(3)-1)});

[David Stiller]

NSurveyor,

> Wouldn't this work for shuffling as well?
> myArray.sort(function(){return (random(3)-1)});

Wow, that's nice! Yes, that seems to do the trick nicely, and doesn't
get much more compact than that. I wonder if someone will run one of those
"perform it 10,000 times" statistics analyses and compare it against the one
Rothrock suggested (often attributed to kglad). Off hand, your sort()
function strikes me as wonderfully suited to the task.

David
stiller (at) quip (dot) net
"Luck is the residue of good design."

[SteveStall]

thanks a lot. What a nice moment this was. :D

"NSurveyor" <saif...@yahoo.com> wrote in message news:ddi8j3$o3n$1...@forums.macromedia.com...

[perry]

real cool!

"NSurveyor" <saif...@yahoo.com> schrieb im Newsbeitrag
news:ddi8j3$o3n$1...@forums.macromedia.com...

[NSurveyor]

I did some tests like David suggested, and my sort loops many more times than
the shuffle does. Here, test it yourself:

arrayLen = -1;

Array.prototype.shuffle = function() {
for (var ivar = this.length-1; ivar>=0; ivar--) {

++count1;

var p = random(ivar);
var t = this[ivar];
this[ivar] = this[p];
this[p] = t;
}
};

onMouseDown = function () {
trace('Array length is now: '+(++arrayLen));
count0 = 0;
count1 = 0;
myArray0 = new Array(arrayLen);
myArray1 = new Array(arrayLen);
myArray1.shuffle();
myArray0.sort(function () { ++count0;return (random(3)-1);});
trace('Sort loops: '+count0);
trace('Shuffle loops:'+count1);
trace('\n');
};

Just keep clicking the mouse to see more results.

[NSurveyor]

Quicker testing:

Array.prototype.shuffle = function() {
for (var ivar = this.length-1; ivar>=0; ivar--) {
++count1;
var p = random(ivar);
var t = this[ivar];
this[ivar] = this[p];
this[p] = t;
}
};

arrayLen = -1;
trace('X\t\tSort\tShuffle');
onEnterFrame = function(){
++arrayLen;

count0 = 0;
count1 = 0;
myArray0 = new Array(arrayLen);
myArray1 = new Array(arrayLen);
myArray1.shuffle();
myArray0.sort(function () { ++count0;return (random(3)-1);});

trace(''+arrayLen+'\t\t'+count0+'\t\t'+count1);
onMouseDown = function(){
delete onEnterFrame;
}
};

[NSurveyor]

I'm guess its a bit messed up, because of the randomness, ex:

Suppose you have the array:

['A','B','C'];

Let's sort!
(Random greater than, less than, and equal)

B < A
A < C
C < B

A should go after C but before B, yet C should go before B, no how does that
work? :confused;

[NSurveyor]

Here are my results from my last test: (I noticed that every time I ran it, the
numbers for sort were different, but always pretty close)

X Sort Shuffle
0 0 0
1 0 1
2 1 2
3 4 3
4 5 4
5 13 5
6 19 6
7 23 7
8 19 8
9 42 9
10 42 10
11 66 11
12 87 12
13 98 13
14 96 14
15 71 15
16 71 16
17 125 17
18 150 18
19 159 19
20 94 20
21 128 21
22 177 22
23 215 23
24 212 24
25 167 25
26 170 26
27 207 27
28 194 28
29 215 29
30 276 30
31 312 31
32 276 32
33 273 33
34 241 34
35 445 35
36 308 36
37 416 37
38 373 38
39 355 39
40 342 40
41 436 41
42 371 42
43 426 43
44 449 44
45 422 45
46 469 46
47 413 47
48 471 48
49 462 49
50 484 50
51 544 51
52 512 52
53 595 53
54 611 54
55 589 55
56 663 56
57 763 57
58 599 58
59 648 59
60 679 60
61 661 61
62 754 62
63 782 63
64 686 64
65 723 65
66 753 66
67 781 67
68 857 68
69 779 69
70 779 70

[Rothrock]

I'll probably stick with my version. I know how it works and it seems pretty
efficient. I seem to recall there was a big discussion about this in one of the
last threads. Jeckyl weighed in with some info about the sort method ? I can't
remember if he was for or against it, but in any event it didn't convince me
that I should change my ways.

As for the authorship. I had found the algorithm (which has been around for
quite some time before there was an internet, I'm sure) on some random website
many years ago for something else. A couple of years later, I coded it up in
Actionscript as a function and put it on another forum (which is no more) as
something to share. Somebody on that site showed me that it had been posted
(with just slightly different variables) as a prototype about a year before
that on yet another site. At some point I posted it here and both kglad and
Jeckyl (both of whom probably already had the code) helped me refine my use of
it.

I'm guessing it is kind of like that thing where two different, unrelated
families of tree frogs evolved the same mechanism for producing poison. (See
here: http://www.nytimes.com/2005/08/09/science/09frog.html) It is just a
simple, well-known algorithm for shuffling, so it is hardly surprising that it
pops up again and again.

Also while the number of loops is important, I checked it with getTimer. For
an array with 52 (number of cards in a standard deck) the shuffle method takes
about 1?5 milliseconds while the sort method takes 44?60 milliseconds. And with
an array of 200 ? shuffle: 4?7 and sort: 277?364.

I know which one I'll use. :)

[David Stiller]

Rothrock,

Nicely written, the whole thing.

> For an array with 52 (number of cards in a standard deck) the
> shuffle method takes about 1?5 milliseconds while the sort
> method takes 44?60 milliseconds. And with an array of 200
> ? shuffle: 4?7 and sort: 277?364.

This, in particular, is handy knowledge. Thanks for weighing in. :)

[NSurveyor]

Yup, I knew the sort would be slower, after all, it loops way more times than
the number of elements in the array! If I do ever shuffle, I'm most definitely
going to use the shuffle method, not the sort. When I posted that code, I was
merely suggesting that you could also do it this way, as opposed to that way,
even though it isn't as fast. In short, I would use the shuffle, and so should
everyone else (who wants to shuffle).

PS: My thumb really hurts after playing Midnight Club on PS2 for like 4 hours
straight, just came here to rest my thumb till it's ready to kill the London
Champion...

[NSurveyor]

Here's a shuffle method I wrote, that should work just as fast as the other one:

Array.prototype.shuffle = function() {
for (var i = this.length; i>0; i--) {
var r=random(i);
this.push(this[ r ]);
this.splice(r, 1);
}
};
arr = [0,1,2,3,4,5,6,7,8,9,10];
arr.shuffle();
trace(arr);

[NSurveyor]

OT: In case you were wondering... I swept the floor with the London Champ (with the help of one of my cousins, and then I anhialated the World Champion a bit later... I finished my career mode, yay!

[Rothrock]

Congratulations are in order. (I guess I don't know what that is, but it seems
like a good thing.)

As for that prototype. Nope. 200 elements with the new prototype approximately
470 and old prototype 3. Evidently assignment is much easier that pushing!

[kglad]

the sort() method is bizarre. for starters, why does it check the first array element against itself? what possible purpose does that serve?

[NSurveyor]

Ok, how about this:

Array.prototype.shuffle = function() {
for (var i = this.length; i>0; i--) {
var r=random(i);

this[this.length-1] = this[ r ];

this.splice(r, 1);
}
};
arr = [0,1,2,3,4,5,6,7,8,9,10];
arr.shuffle();
trace(arr);

Yeah, the sort is really messed up...

[Rothrock]

Faster than the last try at about 215 for 200 elements, but still a long way to go to get to 3. I think anything that has to manipulate the places in an array will just be slower than assignment.

[SteveStall]

Ok, imagine you have a line of stones on a table, each with its own color. You've been asked to shuffle the order of the stones.

What came to me in first place was to use both ands and start by picking 2 stones and swap their position, and so on, and so on...

 

But what if the table is pretty long? You can just use one hand and put each stone you take to the beginning or the hand of the line.

I though this would be a simpler way to spare effort with lines of code, and by not creating more variables and doing lots of calculations:

 

Array.prototype.shuffle = function () {

 for (var i = this.length; i > 0; i--) {

  this.unshift (this.splice (Math.random () * this.length, 1));
 }
};
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
arr.shuffle ();
trace(arr)

 

SteveStall

 

PS: Thought the theory leeds to a point were you could be using the same element you've just shuffled the trace result doesn't give me much sequenced numbers...try it

 

 

 

"NSurveyor" <saif...@yahoo.com> wrote in message news:ddl60o$1eg$1...@forums.macromedia.com...

[SteveStall]

Rothrock, how do you come up with does numbers?... I would like to have the test also ; )

"Rothrock" <webfor...@macromedia.com> wrote in message news:ddlam7$73o$1...@forums.macromedia.com...

[kglad]

use getTimer() for timing.

[Gerrard]

I'm having some problems with the array.shuffle() posted here. When I use this
code the original first name in the array never show when I use "ctrl + enter"
several time after another. Why is that? Is there a solution?

Array.prototype.shuffle = function() {

for (var ivar = this.length-1; ivar>=0; ivar--) {

var p = random(ivar);
var t = this[ivar];
this[ivar] = this[p];
this[p] = t;
}
};

var myArray:Array = new Array("Steven","Linda","Harry");
myArray.shuffle();
trace(myArray[0]);

[Jeckyl]

That is correct for the algorithm you are using .. it is ALWAYS going to
object at [0] away .. so it will indeed never appear there. your code is
not a true shuffle.

Lets look at what can happen.

first time thru loop
if [2] swaps with [0], then the original first element is at [2] now and
will never move from there. If [2] swaps with [1], then [0] is still where
it was
second time thru
[1] always swaps with [0], so original first element is at [1] now and will
never move from there.

You need a different method that actually shuffles correctly .. that code
doesn't work.
--
Jeckyl

[Jeckyl]

change it to

Array.prototype.shuffle = function() {
for (var ivar = this.length-1; ivar>=0; ivar--) {

var p = random(ivar+1);

var t = this[ivar];
this[ivar] = this[p];
this[p] = t;
}
};

then it should work correctly.
--
Jeckyl

[Gerrard]

Yup :)
Works fine now!
Thanks for the help, Jeckyl!

Regards

Gerrard

[juankpro]

Look at this statistics on my computer with an array of 400:

Rothrock: 2 miliseconds
NSurveyor 1: 99 miliseconds
NSurveyor 2: 263 miliseconds
NSurveyor 3: 267 miliseconds
SteveStall: 301 miliseconds

//Rothrock
Array.prototype.shuffle1 = function() {
for (var ivar = this.length - 1; ivar >= 0; ivar--) {
var p = random(ivar);

var t = this[ivar];
this[ivar] = this[p];
this[p] = t;
}
};

//Nsurveyor 1
/*myArray.sort(function () {
return (random(3) - 1);
});*/
//Nsurveyor 2
Array.prototype.shuffle2 = function() {
for (var i = this.length - 1; i >= 0; i--) {
var r = random(i);

this.push(this[r]);
this.splice(r, 1);
}
};

//Nsurveyor 3
Array.prototype.shuffle3 = function() {
for (var i = this.length - 1; i >= 0; i--) {
var r = random(i);
this[this.length] = this[r];
this.splice(r, 1);
}
};
//SteveStall
Array.prototype.shuffle4 = function() {

for (var i = this.length; i > 0; i--) {

this.unshift(this.splice(Math.random() * this.length, 1));
}
};
myArray = new Array();
for(var i = 0; i <= 400; i++){
myArray[i] = i;
}

beginTime = getTimer();
myArray.shuffle1();
trace("Rothrock: " + (getTimer() - beginTime) + " miliseconds");

beginTime = getTimer();
myArray.sort(function () {return (random(3) - 1);});
trace("NSurveyor 1: " + (getTimer() - beginTime) + " miliseconds");

beginTime = getTimer();
myArray.shuffle2();
trace("NSurveyor 2: " + (getTimer() - beginTime) + " miliseconds");

beginTime = getTimer();
myArray.shuffle3();
trace("NSurveyor 3: " + (getTimer() - beginTime) + " miliseconds");

beginTime = getTimer();
myArray.shuffle4();
trace("SteveStall: " + (getTimer() - beginTime) + " miliseconds");

[Gerrard]

Great!
So I'm on the right path by choosing the modyfied code Rothrock by Jeckyl:

//Rothrock
Array.prototype.shuffle1 = function() {
for (var ivar = this.length - 1; ivar >= 0; ivar--) {

//using this.length instead of ivar
var p = random(this.length);

[Jeckyl]

Most of those need fixing as per my earlier post here...

> //Rothrock
> var p = random(ivar);
that one above fails .. should be corrected to
>> var p = random(ivar+1);

> //Nsurveyor 2
> var r = random(i);
that one above also fails .. should be corrected to
>> var r = random(i+1);

> //Nsurveyor 3
> var r = random(i);

that one above also fails .. and should be corrected to
>> var r = random(i+1);

Certainly the simplest way (no expensive push and splices etc) is best.
--
Jeckyl

[jamestomasino]

I saw that there are a lot of people posting their own shuffle code up here, so
I thought I'd throw in my hat. This is the version I've used for a while on my
own.

Array.prototype.shuffle = function() {
for (var c=this.length; c >= 0; c--) this.push(this.splice(random(c), 1));
}

I can't get it much shorter than that. If anyone finds it useful, drop me a
line. It's good for my self-esteem.

~tomasino

[kglad]

the splice method is problematic because it returns an array. you are
therefore changing the nature of the original array (unless the original array
has elements that are arrays) when you use it in a prototype statement.

[Rothrock]

And it is very slow. The splice method took about 8.5 seconds to shuffle a 1000 entry array. My favorite, about 8 milliseconds.

To paraphrase Jeckyl ? push and splice are very expensive.

[blemmo]

The attached variation cuts the 8 ms to 4 ms :)

Array.prototype.shuffle = function() {
var i = this.length;
while (i--) {
var p = random(i+1);
var t = this[i];
this[i] = this[p];
this[p] = t;
}
};