I'd like to randomly sort an array. A good method?
-
-
Re: randomize array
Jeff Thies wrote:[color=blue]
> I'd like to randomly sort an array. A good method?[/color]
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.htm l">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;
}
-
Re: randomize array
Nik Coughin wrote:[color=blue]
> Jeff Thies wrote:[color=green]
>> I'd like to randomly sort an array. A good method?[/color]
>
> 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.htm l">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 ];[/color]
Above line should read:
sorted[ ii ] = unSorted[ randomNumber ];
[color=blue]
> used[ randomNumber ] = true;
> }[/color]
Comment
-
Re: randomize array
Nik Coughin wrote:[color=blue]
> Jeff Thies wrote:[color=green]
>> I'd like to randomly sort an array. A good method?[/color]
>
> 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.htm l">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;[/color]
Sorry, another typo. Should be:
used[ ii ] = false;
[color=blue]
> }
>
> for( ii=1; ii<=5; ii++ )
> {
> randomNumber = Random( 1, 5 );
> while( used[ randomNumber ] )
> {
> randomNumber = Random( 1, 5 );
> }
> sorted[ ii ] = inSorted[ randomNumber ];
> used[ randomNumber ] = true;
> }[/color]
Comment
-
Re: randomize array
Jeff Thies wrote:[color=blue]
> I'd like to randomly sort an array. A good method?[/color]
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="JavaS cript" 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.htm l">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>
Comment
-
Re: randomize array
> Jeff Thies wrote:[color=blue][color=green]
> > I'd like to randomly sort an array. A good method?[/color]
>
> Ignore my previous posts. Didn't test it and it didn't work. Think it[/color]
had[color=blue]
> too many capitalisation related errors. This works:[/color]
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
[color=blue]
>
> <html>
> <head>
> <title>Test</title>
> </head>
> <body>
> <script language="JavaS cript" 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.htm l">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>
>
>[/color]
Comment
-
Re: randomize array
Jeff Thies wrote:[color=blue][color=green]
>> Jeff Thies wrote:[color=darkred]
>>> I'd like to randomly sort an array. A good method?[/color]
>>
>> Ignore my previous posts. Didn't test it and it didn't work. Think
>> it had too many capitalisation related errors. This works:[/color]
>
> 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?
>[/color]
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.
Comment
-
Re: randomize array
Nik Coughin wrote:[color=blue]
> Jeff Thies wrote:[color=green][color=darkred]
>>> 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:[/color]
>>
>> 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?
>>[/color]
>
> 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.[/color]
That said, looking through the Wrox JavaScript Programmer's Reference, it
seems that they either need to be or should be declared.
Comment
-
Re: randomize array
Nik Coughin wrote:[color=blue]
> Jeff Thies wrote:[color=green]
>> I'd like to randomly sort an array.[/color][/color]
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.htm l">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 "randomNumb er" 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)
Comment
-
Re: randomize array
On Fri, 2 Apr 2004 14:12:22 +1200, Nik Coughin <nrkn!no-spam!@woosh.co. nz>
wrote:
[color=blue]
> Nik Coughin wrote:[/color]
[snip]
[color=blue][color=green]
>> 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.[/color]
>
> That said, looking through the Wrox JavaScript Programmer's Reference, it
> seems that they either need to be or should be declared.[/color]
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.Winter@blueyo nder.co.invalid (replace ".invalid" with ".uk" to reply)
Comment
-
Re: randomize array
Nik Coughin wrote:[color=blue]
> Jeff Thies wrote:
>[color=green]
>>I'd like to randomly sort an array. A good method?[/color]
>
>
> for( ii=1; ii<=5; ii++ )
> {
> randomNumber = Random( 1, 5 );
> while( used[ randomNumber ] )
> {
> randomNumber = Random( 1, 5 );
> }
> Sorted[ ii ] = unSorted[ randomNumber ];
> used[ randomNumber ] = true;
> }[/color]
**** 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
Comment
-
Re: randomize array
JRS: In article <kp3bc.2355$d%6 .55935@news.xtr a.co.nz>, seen in
news:comp.lang. javascript, Nik Coughin <nrkn!no-spam!@woosh.co. nz>
posted at Fri, 2 Apr 2004 13:33:37 :
[color=blue]
> for( ii=1; ii<=5; ii++ )
> {
> randomNumber = Random( 1, 5 );
> while( used[ randomNumber ] )
> {
> randomNumber = Random( 1, 5 );
> }
> Sorted[ ii ] = unSorted[ randomNumber ];
> used[ randomNumber ] = true;
> }
>[/color]
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.demo n.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demo n.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
Comment
-
Re: randomize array
JRS: In article <406d6139$1@10. 10.0.241>, seen in
news:comp.lang. javascript, Brian Genisio <BrianGenisio@y ahoo.com> posted
at Fri, 2 Apr 2004 07:45:59 :[color=blue]
>
>Do a search on "Shuffle Algorithm", and you will see a lot of discussion
>on this topic.[/color]
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.demo n.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demo n.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
Comment
-
Re: randomize array
JRS: In article <Xns94BF69B40A4 A8eejj99@194.10 9.133.29>, seen in
news:comp.lang. javascript, Evertjan. <exjxw.hannivoo rt@interxnl.net >
posted at Fri, 2 Apr 2004 08:23:21 :[color=blue]
>
>// 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
>}[/color]
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.demo n.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.demo n.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.merlyn.demo n.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.
Comment
-
Re: randomize array
Jeff Thies wrote:
[color=blue]
> I'd like to randomly sort an array. A good method?
>
>[/color]
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
Comment
Comment