468,136 Members | 1,444 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,136 developers. It's quick & easy.

randomize array

I'd like to randomly sort an array. A good method?
Jul 23 '05 #1
21 3918
Jeff Thies wrote:
I'd like to randomly sort an array. A good method?


Untested (but modified from a working script):

function Random( low, high )
{
with( Math )
{
return floor(random() * ( 1 + high - low ) + low );
}
}

var unSorted = new Array( 5 );
var Sorted = new Array( 5 );
var used = new Array( 5 );

unSorted[ 1 ] = '<a href="one.html">One</a>';
unSorted[ 2 ] = '<a href="two.html">Two</a>';
unSorted[ 3 ] = '<a href="three.html">Three</a>';
unSorted[ 4 ] = '<a href="four.html">Four</a>';
unSorted[ 5 ] = '<a href="five.html">Five</a>';

for( ii=1; ii<=5; ii++ )
{
Used[ ii ] = false;
}

for( ii=1; ii<=5; ii++ )
{
randomNumber = Random( 1, 5 );
while( used[ randomNumber ] )
{
randomNumber = Random( 1, 5 );
}
sorted[ ii ] = inSorted[ randomNumber ];
used[ randomNumber ] = true;
}

Jul 23 '05 #2
Nik Coughin wrote:
Jeff Thies wrote:
I'd like to randomly sort an array. A good method?
Untested (but modified from a working script):

function Random( low, high )
{
with( Math )
{
return floor(random() * ( 1 + high - low ) + low );
}
}

var unSorted = new Array( 5 );
var Sorted = new Array( 5 );
var used = new Array( 5 );

unSorted[ 1 ] = '<a href="one.html">One</a>';
unSorted[ 2 ] = '<a href="two.html">Two</a>';
unSorted[ 3 ] = '<a href="three.html">Three</a>';
unSorted[ 4 ] = '<a href="four.html">Four</a>';
unSorted[ 5 ] = '<a href="five.html">Five</a>';

for( ii=1; ii<=5; ii++ )
{
Used[ ii ] = false;
}

for( ii=1; ii<=5; ii++ )
{
randomNumber = Random( 1, 5 );
while( used[ randomNumber ] )
{
randomNumber = Random( 1, 5 );
}
sorted[ ii ] = inSorted[ randomNumber ];


Above line should read:

sorted[ ii ] = unSorted[ randomNumber ];
used[ randomNumber ] = true;
}


Jul 23 '05 #3
Nik Coughin wrote:
Jeff Thies wrote:
I'd like to randomly sort an array. A good method?
Untested (but modified from a working script):

function Random( low, high )
{
with( Math )
{
return floor(random() * ( 1 + high - low ) + low );
}
}

var unSorted = new Array( 5 );
var Sorted = new Array( 5 );
var used = new Array( 5 );

unSorted[ 1 ] = '<a href="one.html">One</a>';
unSorted[ 2 ] = '<a href="two.html">Two</a>';
unSorted[ 3 ] = '<a href="three.html">Three</a>';
unSorted[ 4 ] = '<a href="four.html">Four</a>';
unSorted[ 5 ] = '<a href="five.html">Five</a>';

for( ii=1; ii<=5; ii++ )
{
Used[ ii ] = false;


Sorry, another typo. Should be:

used[ ii ] = false;
}

for( ii=1; ii<=5; ii++ )
{
randomNumber = Random( 1, 5 );
while( used[ randomNumber ] )
{
randomNumber = Random( 1, 5 );
}
sorted[ ii ] = inSorted[ randomNumber ];
used[ randomNumber ] = true;
}


Jul 23 '05 #4
Jeff Thies wrote:
I'd like to randomly sort an array. A good method?


Ignore my previous posts. Didn't test it and it didn't work. Think it had
too many capitalisation related errors. This works:

<html>
<head>
<title>Test</title>
</head>
<body>
<script language="JavaScript" type="text/javascript">
function Random( low, high )
{
with( Math )
{
return floor(random() * ( 1 + high - low ) + low );
}
}

var unSorted = new Array( 5 );
var Sorted = new Array( 5 );
var used = new Array( 5 );

unSorted[ 1 ] = '<a href="one.html">One</a>';
unSorted[ 2 ] = '<a href="two.html">Two</a>';
unSorted[ 3 ] = '<a href="three.html">Three</a>';
unSorted[ 4 ] = '<a href="four.html">Four</a>';
unSorted[ 5 ] = '<a href="five.html">Five</a>';

for( ii=1; ii<=5; ii++ )
{
used[ ii ] = false;
}

for( ii=1; ii<=5; ii++ )
{
randomNumber = Random( 1, 5 );
while( used[ randomNumber ] )
{
randomNumber = Random( 1, 5 );
}
Sorted[ ii ] = unSorted[ randomNumber ];
used[ randomNumber ] = true;
}
</script>
</body>
</html>
Jul 23 '05 #5
> Jeff Thies wrote:
I'd like to randomly sort an array. A good method?
Ignore my previous posts. Didn't test it and it didn't work. Think it

had too many capitalisation related errors. This works:
Thanks Nik. It's better than what I might have thought up!

Curious about the length initializations: var used = new Array( 5 ); Does
that save resources, or is there another reason?

Cheers,
Jeff

<html>
<head>
<title>Test</title>
</head>
<body>
<script language="JavaScript" type="text/javascript">
function Random( low, high )
{
with( Math )
{
return floor(random() * ( 1 + high - low ) + low );
}
}

var unSorted = new Array( 5 );
var Sorted = new Array( 5 );
var used = new Array( 5 );

unSorted[ 1 ] = '<a href="one.html">One</a>';
unSorted[ 2 ] = '<a href="two.html">Two</a>';
unSorted[ 3 ] = '<a href="three.html">Three</a>';
unSorted[ 4 ] = '<a href="four.html">Four</a>';
unSorted[ 5 ] = '<a href="five.html">Five</a>';

for( ii=1; ii<=5; ii++ )
{
used[ ii ] = false;
}

for( ii=1; ii<=5; ii++ )
{
randomNumber = Random( 1, 5 );
while( used[ randomNumber ] )
{
randomNumber = Random( 1, 5 );
}
Sorted[ ii ] = unSorted[ randomNumber ];
used[ randomNumber ] = true;
}
</script>
</body>
</html>

Jul 23 '05 #6
Jeff Thies wrote:
Jeff Thies wrote:
I'd like to randomly sort an array. A good method?


Ignore my previous posts. Didn't test it and it didn't work. Think
it had too many capitalisation related errors. This works:


Thanks Nik. It's better than what I might have thought up!

Curious about the length initializations: var used = new Array( 5 );
Does that save resources, or is there another reason?


To be honest, I don't know if it saves resources or even if it's necessary.
I don't know all that much about JavaScript, just the basic syntax. I'm
just lucky that it's similar enough to other languages that I've used that
pretty much everything I write works first time (except when I type
something out quickly and sloppily and fuck up the capitalisation). I've
written in a lot of different languages (BASIC, Pascal, COBOL [yuck], c/c++,
vb, DarkBASIC, delphi, JavaScript, *nix shell, etc. etc. etc.), and I've
gotten into the habit of declaring arrays before I use them.
Jul 23 '05 #7
Nik Coughin wrote:
Jeff Thies wrote:
Jeff Thies wrote:
I'd like to randomly sort an array. A good method?

Ignore my previous posts. Didn't test it and it didn't work. Think
it had too many capitalisation related errors. This works:


Thanks Nik. It's better than what I might have thought up!

Curious about the length initializations: var used = new Array( 5 );
Does that save resources, or is there another reason?


To be honest, I don't know if it saves resources or even if it's
necessary. I don't know all that much about JavaScript, just the
basic syntax. I'm just lucky that it's similar enough to other
languages that I've used that pretty much everything I write works
first time (except when I type something out quickly and sloppily and
fuck up the capitalisation). I've written in a lot of different
languages (BASIC, Pascal, COBOL [yuck], c/c++, vb, DarkBASIC, delphi,
JavaScript, *nix shell, etc. etc. etc.), and I've gotten into the
habit of declaring arrays before I use them.


That said, looking through the Wrox JavaScript Programmer's Reference, it
seems that they either need to be or should be declared.
Jul 23 '05 #8
Nik Coughin wrote:
Jeff Thies wrote:
I'd like to randomly sort an array.


I would prefer randomizing by record swapping:
<script type="text/javascript">

var unSorted = new Array( 5 );
var randomlist = new Array( 5 );

unSorted[ 1 ] = '<a href="one.html">One</a>';
unSorted[ 2 ] = '<a href="two.html">Two</a>';
unSorted[ 3 ] = '<a href="three.html">Three</a>';
unSorted[ 4 ] = '<a href="four.html">Four</a>';
unSorted[ 5 ] = '<a href="five.html">Five</a>';

// random number generation
function Random( low, high ) {
return Math.floor(Math.random() * ( 1 + high - low ) +
low );
}

// fill a new array "randomNumber" sequentially
for( ii=1; ii<=5; ii++ ) {
randomlist[ ii ] = ii;
}

// randomize the randomNumber array by record swapping
for( ii=1; ii<=5; ii++ ) {
var randomNumber = Random( 1, 5 );
var temp = randomlist[ ii ]
randomlist[ ii ] = randomlist[ randomNumber ]
randomlist[ randomNumber ] = temp
}

// indirect output the so randomized list
for( ii=1; ii<=5; ii++ ) {
document.write(unSorted[randomlist[ ii ]]+"<br>")

// or fill a new array "myNewArray":
// myNewArray[ ii ] = unSorted[randomlist[ ii ]]
}

</script>

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)
Jul 23 '05 #9
On Fri, 2 Apr 2004 14:12:22 +1200, Nik Coughin <nr***********@woosh.co.nz>
wrote:
Nik Coughin wrote:


[snip]
To be honest, I don't know if it saves resources or even if it's
necessary. I don't know all that much about JavaScript, just the
basic syntax. I'm just lucky that it's similar enough to other
languages that I've used that pretty much everything I write works
first time (except when I type something out quickly and sloppily and
fuck up the capitalisation). I've written in a lot of different
languages (BASIC, Pascal, COBOL [yuck], c/c++, vb, DarkBASIC, delphi,
JavaScript, *nix shell, etc. etc. etc.), and I've gotten into the
habit of declaring arrays before I use them.


That said, looking through the Wrox JavaScript Programmer's Reference, it
seems that they either need to be or should be declared.


You need to initialise the variable or property to be of an array type
using either of

a = [];
a = new Array();

but you needn't specify a size. Writing

a[ 7 ] = 'The only entry';

will resize the zero-length array to include eight elements, the last of
which contains a string. The first seven will remain undefined: a sparse
array.

There might be some speed improvements by specifying an adequate initial
size, but only if arrays in JavaScript are implemented as contiguous
memory blocks, which might not be the case (probably implementation
dependent).

The same is true for an object. You need to initialise the variable or
property to an object using either of[1]

o = {};
o = new Object();

before you assign any properties or methods.

Mike
[1] You could also use a function as a constructor.

--
Michael Winter
M.******@blueyonder.co.invalid (replace ".invalid" with ".uk" to reply)
Jul 23 '05 #10
Nik Coughin wrote:
Jeff Thies wrote:
I'd like to randomly sort an array. A good method?

for( ii=1; ii<=5; ii++ )
{
randomNumber = Random( 1, 5 );
while( used[ randomNumber ] )
{
randomNumber = Random( 1, 5 );
}
Sorted[ ii ] = unSorted[ randomNumber ];
used[ randomNumber ] = true;
}


**** WARNING ****

This method is incredibly inneficient with arrays of any real size.
Immagine if you have 1000 numbers, and you are trying to fill the 1000th
space. On average (with true randomness) , you will go through 1000
tries, just to find a number that is not used!!!

If you are familiar with BigO notation, this algorithm takes O(n^2).
Instead, you can do a 1 time pass over the data set, and swap it
randomly with another. You can do this more than once if you choose,
and it will still be O(n).

Do a search on "Shuffle Algorithm", and you will see a lot of discussion
on this topic.

Brian
Jul 23 '05 #11
JRS: In article <kp******************@news.xtra.co.nz>, seen in
news:comp.lang.javascript, Nik Coughin <nr***********@woosh.co.nz>
posted at Fri, 2 Apr 2004 13:33:37 :
for( ii=1; ii<=5; ii++ )
{
randomNumber = Random( 1, 5 );
while( used[ randomNumber ] )
{
randomNumber = Random( 1, 5 );
}
Sorted[ ii ] = unSorted[ randomNumber ];
used[ randomNumber ] = true;
}


Inefficient.

There is in principle no guarantee, with a perfect random generator,
that it will ever finish.

On the fifth time round the FOR loop, it hunts at random for a single
entry among the five, having on the fourth sought one of two among the
five ... . Of course, that's presumably not too slow with only five;
but if shuffling a deck of cards it will end up blindly looking for one
in 52.

The smart move, before answering a question, is to consult the newsgroup
FAQ (it is also smart to do so before asking) as a precaution against
making an obvious fool of oneself. (Another good one is to only post
answers that have been tested then copy'n'pasted.)

Section 4.22 of he newsgroup FAQ links to <URL:http://www.merlyn.demon.
co.uk/js-randm.htm> which contains

function Shuffle(Q) { var R, T, J
for (J=Q.length-1 ; J>0 ; J--)
{ R=Random(J+1) ; T=Q[J] ; Q[J]=Q[R] ; Q[R]=T }
return Q }

and that is the algorithm that should be used. I claim credit only for
copying the method, indirectly, from Knuth. It generates, with minimum
effort, an equi-probable distribution, if Random is itself perfect.

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
<URL:http://jibbering.com/faq/> Jim Ley's FAQ for news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
Jul 23 '05 #12
JRS: In article <40********@10.10.0.241>, seen in
news:comp.lang.javascript, Brian Genisio <Br**********@yahoo.com> posted
at Fri, 2 Apr 2004 07:45:59 :

Do a search on "Shuffle Algorithm", and you will see a lot of discussion
on this topic.


Why recommend a search, when the newsgroup FAQ has all that the OP
needs?

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
<URL:http://jibbering.com/faq/> Jim Ley's FAQ for news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
Jul 23 '05 #13
JRS: In article <Xn********************@194.109.133.29>, seen in
news:comp.lang.javascript, Evertjan. <ex**************@interxnl.net>
posted at Fri, 2 Apr 2004 08:23:21 :

// randomize the randomNumber array by record swapping
for( ii=1; ii<=5; ii++ ) {
var randomNumber = Random( 1, 5 );
var temp = randomlist[ ii ]
randomlist[ ii ] = randomlist[ randomNumber ]
randomlist[ randomNumber ] = temp
}


That loop is done five times, and each time it generates one of five
numbers. The total number of possible routes, all equally probable, is
thus 5^5.

There are 5! possible orders for the five items.

5^5 is not an integer multiple of 5! ; therefore, the method cannot
generate all 5! orders with exactly equal probability.

See <URL:http://www.merlyn.demon.co.uk/pas-rand.htm#Shuf>, and (AIUI)
Knuth.
BTW, the OP asked to shuffle an existing array; you, and others, create
an array and fill it with numbers. For that case, the numbers can be
generated on-the-fly. See <URL:http://www.merlyn.demon.co.uk/pas-
rand.htm#Deal>, and the URL in the FAQ.

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 MIME. ©
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.merlyn.demon.co.uk/clpb-faq.txt> RAH Prins : c.l.p.b mFAQ;
<URL:ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ.
Jul 23 '05 #14
Jeff Thies wrote:
I'd like to randomly sort an array. A good method?


Array.prototype.swap = function(index1,index2)
{ var temp = this[index1];
this[index1] = this[index2];
this[index2] = temp;
return;
}

Array.prototype.shuffle = function()
{ for(var i=0; i<this.length; i++)
{ ind1 = Math.floor(Math.random()*this.length);
ind2 = Math.floor(Math.random()*this.length);
this.swap(ind1,ind2);
}
return;
}

--
Vladdy
http://www.klproductions.com
Jul 23 '05 #15
Dr John Stockton wrote on 02 apr 2004 in comp.lang.javascript:
That loop is done five times, and each time it generates one of five
numbers. The total number of possible routes, all equally probable, is
thus 5^5.

There are 5! possible orders for the five items.

5^5 is not an integer multiple of 5! ; therefore, the method cannot
generate all 5! orders with exactly equal probability.


This can be, but the increase in speed is significant, because you do not
have to search and repeat for uniqueness.

Shuffling is a good option, if you tolerate a not exact randomness.

The quality increases with repeating the shuffle, not necessary in this
case, I think, unless one of the paying(!) target URL's complains.

================

btw, can you give an exact value to the deviation of the chance of having
one URL being on place 1 from 20% in the case of n=5. Is this dependent
on the initial position ?

5 x 5 = 25

1 x 2 x 3 x 4 x 5 = 120

.... [sorry I give up]
--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)
Jul 23 '05 #16
"Evertjan." <ex**************@interxnl.net> writes:
Dr John Stockton wrote on 02 apr 2004 in comp.lang.javascript:
That loop is done five times, and each time it generates one of five
numbers. The total number of possible routes, all equally probable, is
thus 5^5.

There are 5! possible orders for the five items.

5^5 is not an integer multiple of 5! ; therefore, the method cannot
generate all 5! orders with exactly equal probability.

This can be, but the increase in speed is significant, because you do not
have to search and repeat for uniqueness.


Not over the recommended method:
---
function shuffle(arr) {
for(var i=arr.length;i>0;i--) {
var n = Math.floor(Math.random()*i); //element to end in position i
var tmp = arr[i-1];
arr[i-1]=arr[n];
arr[n]=tmp;
}
}
---
(it's equivalent to the version linked from the FAQ:
<URL:http://www.merlyn.demon.co.uk/js-randm.htm#SDFS>
)

It gives a perfect shuffle, with each of the (arr.length)!
permutations having equal chance (or, it would if Math.random was
perfect). And it is just as efficient as the other one!
Shuffling is a good option, if you tolerate a not exact randomness.
Computers only generate pseudo-random numbers. That should not be an
excuse for not using a good algorithm.
The quality increases with repeating the shuffle, not necessary in this
case, I think, unless one of the paying(!) target URL's complains.
If repepating a shuffle increases the qualit, then the original shuffle
was not good enough. there is no excuse for that, since it could be.
btw, can you give an exact value to the deviation of the chance of having
one URL being on place 1 from 20% in the case of n=5. Is this dependent
on the initial position ?


Does it matter, when there is a shuffle that is known to work, is just
as efficient, and when the shuffle you presented can be shown not to
work?

Hmm. Probability. Hard to calculate. Let's try. :)
Every step has 25 different possible "swaps" (5*5), which are equally
likely. Some of them give equal results (swap(1,2) or swap(2,1)) or
no change (move(1,1)).

Let's define a pair of mutually recursive functions (we can ignore the
actual positions because of symmetry, and let N be the number of
positions):

P(n) := chance of element not at at specific position
ending up at that position after n steps,
Q(n) := chance of element at a specific position
ending up at that position after n steps

(trivially, although we won't need them:)
P(0) = 0
Q(0) = 1

(Without loss of generality, assume p = positon of element, q = target
position)
P(1) = Chance of move swap(q,p) or swap(p,q) (using P we know p!=q)
= 2/(N^2)
Q(1) = Chance of swap(n,m), n,m!=p, or swap(p,p) (using Q we know p=q)
= ((N-1)^2+1)/(N^2)

P(n) = Chance to move p to q * Q(n-1)
+
Chance not to move p to q * P(n-1)
= Chance of swap(p,q) or swap(q,p) * Q(n-1)
+
Chance not of swap(p,q) or swap(q,p) * P(n-1)
= 2/(N^2) * Q(n-1)
+ (N^2-2)/(N^2) * P(n-1)
Q(n) = Chance to move away from p * P(n-1)
+
Chance not to move away from p * Q(n-1)
= Chance of swap(p,m) or swap(m,p),m!=p * P(n-1)
+
Chance of swap(n,m),n,m!=p or swap(p,p) * Q(n-1)
= 2(N-1)/(N^2) * P(n-1)
+
((N-1)^2+1)/(N^2) * Q(n-1)
Since this is a Javascript group, here goes:
---
var N=5;
function P(n) {
if (n<1) {return 0;}
if (n==1) {
return 2/(N*N);
} else {
return (2/(N*N)) * Q(n-1) +
(N*N-2)/(N*N) * P(n-1);
}
}
function Q(n) {
if (n<1) {return 0;}
if (n==1) {
return ((N-1)*(N-1)+1)/(N*N);
} else {
return (2*(N-1)/(N*N))*P(n-1) +
((N-1)*(N-1)+1)/(N*N) * Q(n-1);
}
}
var pn = P(n);
var qn = Q(n);
alert([qn,pn,qn/pn])
---
(This implementation takes time exponential in n, but can easily
be made linear with dynamic programming).

If the shuffle was perfect, then P(n) == Q(n) for all n (where you end
up should not depend on where you started).

They are actually:
P(5) = 0.184448
Q(5) = 0.262208
A ~42% higher chance of ending up where you started than at any other
single position. That's your deviation from 20%.

The problem grows for larger N. For N=10, Q(10)/P(10)~=2.20, i.e., a
102% larger chance of staying at the start-position than of moving to
another specific position.

For shuffling a deck of cards (N=52), Q(52)/P(52)~=8.78. The position
you start out in is more than seven times as likely as your final
position than any other position. (Don't try to calcualte this with
the exponential time functions :)

It's that bad.
/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Jul 23 '05 #17
Lasse Reichstein Nielsen <lr*@hotpop.com> writes:
"Evertjan." <ex**************@interxnl.net> writes:
This can be, but the increase in speed is significant, because you do not
have to search and repeat for uniqueness.


Not over the recommended method:


Notice: I misremebered Evertjan's algorithm, confuzing it with another
one also suggested as a solution (it was even worse than Evertjan's :)

Evertjan's algorithm was (using 1-based arrays):
---
for( ii=1; ii<=5; ii++ ) {
var randomNumber = Random( 1, 5 );
var temp = randomlist[ ii ]
randomlist[ ii ] = randomlist[ randomNumber ]
randomlist[ randomNumber ] = temp
}
---

This is not summetrical for the different positions, so I just ran through
the 5^5 = 3125 different possible runs to see which of the 5!=120 different
shuffles came out most often.
---
var seeds = [];
function generateSeeds() {
var ctr = 0;
for (var i1=0;i1<5;i1++) {
for (var i2=0;i2<5;i2++) {
for (var i3=0;i3<5;i3++) {
for (var i4=0;i4<5;i4++) {
for (var i5=0;i5<5;i5++) {
seeds[ctr++] = [i1,i2,i3,i4,i5];
}}}}}};
var randomSeed;
var randomSeedIdx;
function setSeed(seed) {
randomSeed = seed;
randomSeedIdx = 0;
}
function Random() {
return randomSeed[randomSeedIdx++];
}

function shuffle(randomlist) {
for( ii=1; ii<=5; ii++ ) {
var randomNumber = Random( 1, 5 );
var temp = randomlist[ ii-1 ] // zero based array
randomlist[ ii-1] = randomlist[ randomNumber ]
randomlist[ randomNumber ] = temp
}
return randomlist;
}

generateSeeds();
var lists = [];
for(var i=0;i<seeds.length;i++) {
setSeed(seeds[i]);
lists.push(shuffle([0,1,2,3,4]));
}
---
Now, "lists" contain all the shuffled lists. Let's run some statistics, like
seeing how often each value ends up at each position:
---
// stat[elem][pos] = number of time elem ends up at position pos
var stat=[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]];
for(var i=0;i<lists.length;i++) {
for (var j=0;j<5;j++) {
stat[lists[i][j]][j]++; // element lists[i][j] ended up at position j
}
}

var res=[]; // doing some lousy formatting :)
for (var i=0;i<5;i++) {
res.push("Element "+i+": ");
for (var j=0;j<5;j++) {
res.push(" pos "+j+": "+stat[i][j]+" times ("+Math.round((stat[i][j]/lists.length)*100)+"%) ");
}
res.push("\n");
}
alert(res.join(""));
---

The result, manually formatted: How often does the element n (starting
at position n) end up at another position, rounded to integer
percentage.

End position 0 1 2 3 4
start position
0: 20% 20% 20% 20% 20%
1: 24% 18% 19% 19% 20%
2: 21% 23% 17% 19% 20%
3: 18% 20% 23% 18% 20%
4: 16% 18% 21% 24% 20%

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Jul 23 '05 #18
Lasse Reichstein Nielsen wrote on 03 apr 2004 in comp.lang.javascript:
End position 0 1 2 3 4
start position
0: 20% 20% 20% 20% 20%
1: 24% 18% 19% 19% 20%
2: 21% 23% 17% 19% 20%
3: 18% 20% 23% 18% 20%
4: 16% 18% 21% 24% 20%


Right.

Using the "Monte Carlo" method, 10000 tries,
I see nearly the same results:

20% 19% 20% 20% 21%
24% 19% 18% 19% 20%
21% 23% 18% 19% 19%
19% 21% 22% 18% 20%
17% 18% 21% 25% 20%

<script>
var randomlist = []
var sumlist = []
sumlist[0] = [0,0,0,0,0]
sumlist[1] = [0,0,0,0,0]
sumlist[2] = [0,0,0,0,0]
sumlist[3] = [0,0,0,0,0]
sumlist[4] = [0,0,0,0,0]

function Random( high ) {
return Math.floor(Math.random() * ( 1 + high ));
}

for( j=0; j<10000; j++ ) {
for( ii=0; ii<=4; ii++ ) {
randomlist[ ii ] = ii
}
for( ii=0; ii<=4; ii++ ) {
var randomNumber = Random( 4 );
var temp = randomlist[ ii ]
randomlist[ ii ] = randomlist[ randomNumber ]
randomlist[ randomNumber ] = temp
}
for( ii=0; ii<=4; ii++ ) {
sumlist[randomlist[ ii ]][ ii ] += 1
}
}

for( j=0; j<=4; j++ ) {
for( ii=0; ii<=4; ii++ ) {
document.write(Math.round(sumlist[ j ][ ii ]/100)+"% ");
}
document.write("<br>");
}
</script>

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)
Jul 23 '05 #19
"Evertjan." <ex**************@interxnl.net> writes:
Lasse Reichstein Nielsen wrote on 03 apr 2004 in comp.lang.javascript:
End position 0 1 2 3 4
start position
0: 20% 20% 20% 20% 20%
1: 24% 18% 19% 19% 20%
2: 21% 23% 17% 19% 20%
3: 18% 20% 23% 18% 20%
4: 16% 18% 21% 24% 20%


Right.

Using the "Monte Carlo" method, 10000 tries,
I see nearly the same results:

20% 19% 20% 20% 21%
24% 19% 18% 19% 20%
21% 23% 18% 19% 19%
19% 21% 22% 18% 20%
17% 18% 21% 25% 20%


Good to know (means I probably didn't make an error :)

If we divide these results by 1/5 (i.e., multipies by 5), we get the
percentage change compared to the expected 1/5. Also using a Monte
Carlo approach with 10000 rounds, I get (rounding only at the end):
98% 104% 98% 100% 100%
123% 88% 95% 94% 101%
106% 118% 83% 93% 100%
95% 100% 116% 89% 100%
78% 90% 109% 124% 99%

Now, when we pick an N larger than 5 and try again, we can still read
the results (instead of them all being 2% or 3% :)

For N=20, the largest and smallest results were 140% and 78%.
For N=52: 144% and 70%.
It seems the problem does get bigger for bigger N.

(Code:
---
var N = 52
;
var Rounds = 10000;

function LS(n) {
return ((n<10)?" ":"")+(n<100?" ":"")+n;
}

function Random(min,max) { // in range min-max inclusive.
return Math.floor(Math.random()*(max-min+1))+min
}

function makelist(n) {
var list = [];
for(var i=0;i<n;i++) {list[i]=i;}
return list;
}

function shuffle(randomlist) {
var n = randomlist.length;
for(var i=0; i<n; i++ ) {
var randomNumber = Random(0, n-1);
var temp = randomlist[ i ]
randomlist[ i ] = randomlist[ randomNumber ]
randomlist[ randomNumber ] = temp
}
return randomlist;
}
var stat = [];
for (var i=0;i<N;i++) {
var li = [];
stat[i]= li;
for (var j=0;j<N;j++) {
li[j]=0;
}
}

for(var r=0;r<Rounds;r++) {
var slist = shuffle(makelist(N));
for(var i=0;i<N;i++) {
stat[slist[i]][i]++;
}
}

var res = [];
for (var i=0;i<N;i++) {
for (var j=0;j<N;j++) {
res.push(LS(Math.round(stat[i][j]/(Rounds)*N*100))+"% ");
}
res.push("\n");
}
res.join(""); // write or alert this. I run it in an eval that is displayed
---
)

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Jul 23 '05 #20
JRS: In article <c6***************@nwrdny01.gnilink.net>, seen in
news:comp.lang.javascript, Vladdy <vl**@klproductions.com> posted at
Sat, 3 Apr 2004 02:14:32 :
Jeff Thies wrote:
I'd like to randomly sort an array. A good method?


Array.prototype.swap = function(index1,index2)
{ var temp = this[index1];
this[index1] = this[index2];
this[index2] = temp;
return;
}

Array.prototype.shuffle = function()
{ for(var i=0; i<this.length; i++)
{ ind1 = Math.floor(Math.random()*this.length);
ind2 = Math.floor(Math.random()*this.length);
this.swap(ind1,ind2);
}
return;
}

It would be interesting to find out whether a swap method is better than
in-line code in such cases. In Pascal one could pass a pointer, to
avoid repeated indexing - there ought to be a way in JS for setting a
variable to point to A[b] rather than setting to a copy of A[b] if A[b]
is a number and not an object ...

Your code calls Math.random ten times to shuffle 5 elements; it should
therefore be slower than the efficient method which calls it only five
times.

For 5 elements, your code gets a random in 1..5 ten times; there are
therefore 5^10 equi-probable possible routes and still 5! outcomes; the
former is not a multiple of the latter; therefore, Lasse's tests for
evenness will show the method to be faulty. It's hard to beat Knuth;
and, in this case, not worth trying; OTTINMODNPPSODNPDW.


Note that in some browsers Math.random() can occasionally give (at
least) 1.0; in that case, ISTM that an instance of "undefined" will
appear, if not shuffled out again. FAQ 4.22 is therefore incompletely
reliable; follow its third link.

function Randum(N) { return (N*(Math.random()%1))|0 } // %1 : Opera

also seems slightly faster (for me) than using Math.floor, though the
upper bound is lower.

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 MIME. ©
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Proper <= 4-line sig. separator as above, a line exactly "-- " (SonOfRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036)
Jul 23 '05 #21
Lasse Reichstein Nielsen wrote:
"Evertjan." <ex**************@interxnl.net> writes:

Lasse Reichstein Nielsen wrote on 03 apr 2004 in comp.lang.javascript:

End position 0 1 2 3 4
start position
0: 20% 20% 20% 20% 20%
1: 24% 18% 19% 19% 20%
2: 21% 23% 17% 19% 20%
3: 18% 20% 23% 18% 20%
4: 16% 18% 21% 24% 20%


Right.

Using the "Monte Carlo" method, 10000 tries,
I see nearly the same results:

20% 19% 20% 20% 21%
24% 19% 18% 19% 20%
21% 23% 18% 19% 19%
19% 21% 22% 18% 20%
17% 18% 21% 25% 20%

Good to know (means I probably didn't make an error :)

If we divide these results by 1/5 (i.e., multipies by 5), we get the
percentage change compared to the expected 1/5. Also using a Monte
Carlo approach with 10000 rounds, I get (rounding only at the end):
98% 104% 98% 100% 100%
123% 88% 95% 94% 101%
106% 118% 83% 93% 100%
95% 100% 116% 89% 100%
78% 90% 109% 124% 99%

.....


Ha! I love it. What do you get when you put a bunch of computer
scientists and mathmaticians in a room? A bunch of nerd talk!!!!! May
the whole world be this nerdy!!! Keep it up. I dont get enough of it
on a regular basis. :)

Brian
Jul 23 '05 #22

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by knoak | last post: by
2 posts views Thread by Fieldmedic | last post: by
3 posts views Thread by Gaffer | last post: by
1 post views Thread by Ellen Manning | last post: by
1 post views Thread by Badass Scotsman | last post: by
1 post views Thread by Samuel Shulman | last post: by
6 posts views Thread by mrtaka79 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.