Say I have items numbered c=1, c=2, to c=5.
Can Javascript present them in a non-numeric order, say 1, 3, 5, 4, 2?
All the numbers bewteen 1 and 5 are there but they appear in a
different order.
Cheers
Geoff
What order would you like. A random order?
--
Jonathan
Yes.
PointedEars
--
var bugRiddenCrashPronePieceOfJunk = (
navigator.userAgent.indexOf('MSIE 5') != -1
&& navigator.userAgent.indexOf('Mac') != -1
) // Plone, register_function.js:16
How did you get that idea?
> optimistx wrote:
>> "Thomas 'PointedEars' Lahn" <Point...@web.de> [wrote:]
>>> Geoff Cox wrote:
>>>> Say I have items numbered c=1, c=2, to c=5.
>>>>
>>>> Can Javascript present them in a non-numeric order, say 1, 3, 5, 4, 2?
>>> Yes.
>> No.
>
> How did you get that idea?
Because you cannot number items c=1, c=2, to c=5.
That is one item that is overwritten time and again.
And there is no order in writing one item.
And is 1, 3, 5, 4, 2 a nonnummeric order? No.
Perhaps randomness is intended,
but random cannot be an order, it is lack of order.
Perhaps an array of numbers should be placed in a random sequence?
Impossible, as a state machine can only achieve pseudo randomness.
Perhaps an array of numbers should be placed in a pseudo random sequence?
Yes, that is what Javascript can do!
--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)
Jonathan,
random is OK so long as all 5 numbers are present each time...
Cheers,
Geoff
Evertjan
I am trying to get all 5 numbers, 1-5, each time but in a different
order each time ...
Cheers
Geoff
That wont work forever..
> Cheers
>
> Geoff
the order may be repeated at random intervals - is this what you mean?
Geoff
>> Cheers
>>
>> Geoff
Pardon me asking, but why do you say that?
--
Jonathan
Because it's a truth.
function Item(c) {
this.c = c;
}
Item.prototype.toString = function () {
return "c=" + this.c;
};
var a = [];
for (var i = 1; i < 6; i++) {
a.push(new Item(i));
}
function sorter(x, y) {
// appropriately randomize
}
print(a.sort(sorter));
print(a.sort(sorter));
print(a.sort(sorter));
=>
c=2,c=3,c=5,c=4,c=1
c=4,c=3,c=2,c=1,c=5
c=3,c=4,c=1,c=5,c=2
--
Jake Jarvis
You really should try to get your brain in gear before you start your
fingers up. The above 2 statements are mutually exclusive and as TNP
points out, the first is impossible.
;-)
> Geoff
>
>>> Cheers
>>>
>>> Geoff
Off topic:
I admire your ability to show friendly attitude always here. Sometimes that
kind of behaviour is very difficult for me.
I have had an opportunity to observe an Asperger syndrome patient long time
in her home, a 12 year girl.
She had to make and follow rules all the time, she could not imagine how
other people felt, and her language was very 'literary'. Eg. if I was
carrying a box with both hands, came to a closed door and asked 'Could you
open this door?'. She answered 'Yes' and continued doing what she was doing
(e.g. reading a book), and no intention to open the door for me!
When I asked 'Why do you not open the door?', she explained that I did not
ask her to open the door. In her opinion she answered my question, and in
fact she did. She had no ability to imagine that maybe I with the question
meaned also some other things. When I thereafter asked ' Please open this
door' she opened the door without problems.
It depends, of course, on the chosen interpretation of the question.
There is at least one interpretation where the correct answer is "Yes".
PointedEars
--
Anyone who slaps a 'this page is best viewed with Browser X' label on
a Web page appears to be yearning for the bad old days, before the Web,
when you had very little chance of reading a document written on another
computer, another word processor, or another network. -- Tim Berners-Lee
Thanks for the clarification.
How I got my idea "No", depends on the chosen interpretation of the
question, of course.
There are at least two interpretations where the correct answer is "No".
Abort, retry, fail?
There is a degree of ambiguity. "In a different order *each* time" is
not the same as "In a different order *every* time". The difference is
subtle, but it is there. "Different order *each* time" allows the
possibility that it need only be different from the immediately previous
result.
If my wife asks me the same question continually, I give a different
answer each time. Even when the possible choices are just "Yes" and "No".
--
Steve Swift
http://www.swiftys.org.uk/swifty.html
http://www.ringers.org.uk
You overlook the distinct possibility that there may be distinct items
(objects) that have a attribute (property) named `c' with different values each.
>> And there is no order in writing one item.
>>
>> And is 1, 3, 5, 4, 2 a nonnummeric order? No.
AISB, it depends on the interpretation of the question. I had interpreted
the question in the OP's favor.
>> Perhaps randomness is intended,
>> but random cannot be an order, it is lack of order.
That, again, depends on the interpretation. With computers at least,
randomness is not defined as a lack of order but as a certain, seemingly
arbitrary, class of order:
>> Perhaps an array of numbers should be placed in a random sequence?
>> Impossible, as a state machine can only achieve pseudo randomness.
>>
>> Perhaps an array of numbers should be placed in a pseudo random sequence?
Mark the "pseudo" part.
>> Yes, that is what Javascript can do!
>
> Evertjan
>
> I am trying to get all 5 numbers, 1-5, each time but in a different
> order each time ...
It is possible to generate a limited set of different elements in an order
that is different from the order used before, the order before that aso.
until including the second used order. However, logic (and math) dictates
that with a limited set of elements, as here, it is not possible to generate
those elements in an order (more precisely: a permutation of the elements)
that is different from all preceding permutations as the number of possible
permutations of those elements is also limited (and well-defined).
That applies both to monotonous ascending (e.g.: 1, 2, 3, 4, 5) and
non-monotonous² permutations of elements (e.g.: 1, 5, 4, 2, 3), whereas you
probably meant the latter by "non-numeric". In a stricter sense, even a
non-monotonous permutation is numeric because there exists an ordering
function to generate that permutation. As a result, a reference to a
corresponding Function object can be passed to the Array.prototype.sort()
method.
PointedEars
___________
¹ <http://en.wikipedia.org/wiki/Permutation>
² <http://en.wikipedia.org/wiki/Monotonic_function>
--
Use any version of Microsoft Frontpage to create your site.
(This won't prevent people from viewing your source, but no one
will want to steal it.)
-- from <http://www.vortex-webdesign.com/help/hidesource.htm> (404-comp.)
And how was the original poster to know what /you/ meant when you said
"Yes"?
--
Jonathan
Geoff, I've not seen anyone give you an answer, so I'll have a go. I
can't do it in JavaScript, as I'm 99.9% useless at that. However, I've
solved this in other languages, and will describe the principle.
First create a string '12345'
Then loop five times:
Select a random number from 1 to {length of string}
(probably 0 to length-1 for JavaScript)
Pick the letter at that offset as your next number
Delete that letter from the string
This has the advantage that you loop only 5 times. If you pick random
numbers from 1 to 5 and ignore ones you've already used, you risk
wasting time, possibly for minutes. or even until the universe ends if
your luck is as bad as mine sometimes is.
It gets inefficient when you are picking from much larger ranges, as you
are continually shrinking the initial string. Depending on how this is
handled, it might range from quick to very slow.
They could only guess, as I could only guess (or, to employ a more
scientific term, one would need to determine one or more interpretations in
which either statement is true). That is one major problem with questions
not asked in a smart way. Incidentally, the FAQ recommends for the OP to do
something different.
<http://jibbering.com/faq/#posting>
<http://www.catb.org/~esr/faqs/smart-questions.html>
You're welcome.
> How I got my idea "No", depends on the chosen interpretation of the
> question, of course.
Naturally. That is why I did not say that you were wrong but, in essence,
I asked you about the interpretation that you employed. Unfortunately, you
preferred not to answer that question which somewhat leaves us at a dead end.
> There are at least two interpretations where the correct answer is "No".
Quite possible.
> Abort, retry, fail?
No. (Selection of an appropriate interpretation of this response is left as
an exercise to the reader.)
PointedEars
--
realism: HTML 4.01 Strict
evangelism: XHTML 1.0 Strict
madness: XHTML 1.1 as application/xhtml+xml
-- Bjoern Hoehrmann
And that's why, in my original response I wrote:
What order would you like. A random order?
This was, by the way, over three hours before you responded 'Yes'.
Yes, you're right. Sometimes not smart questions get not smart
responses. I try to give a wise response, whatever the question.
--
Jonathan
Well, It is clear that the problem is not her interpretation, but yours.
You expect the "world" to understand that what you say is not what you
mean, but quite another thing that is only known to "intimi".
Such "intimi" could be any local group, a family, a shop slang group, a
hobby or specialists group, a country, several countries.
The name given to such clearly abberant interpretations is "idiom".
Her only problem is not that she does not know your idiomatic
interpretation, but that she is unable to lower herself to your level of
acceptance of the illogical.
> When I asked 'Why do you not open the door?', she explained that I did
> not ask her to open the door. In her opinion she answered my question,
> and in fact she did. She had no ability to imagine that maybe I with
> the question meaned also some other things. When I thereafter asked '
> Please open this door' she opened the door without problems.
You see, her interpretation is the logical one, and is very good for the
OP of the Q to review the question before pressing the send button.
Back to Usenet behavour:
Answering by second guessing the OQ is not good for the internal logical
cirquit developmment of the OP's brain.
Reinstating the on topic:
If you see this in the context of Javascript and CSS browser dialects and
the strict w3 ruling, who is "right" and what "works" give the same
dilemmas.
A simple document.styleSheets[0] will not find the first stylesheet in
Chrome, when Google Gestures is active, it's invisible own stylesheet
taking over place zero.
alert(document.styleSheets.length)
returning one more than I countd in the code,
was the first clue in my case.
Reversed Cyber-Asperger in its fullblown state, as I took the language
for granted where the browser had more litteral idea of correct language
interpretation.
Google for
javascript permutation algorithm
to see what you might be asking for (it was a very unclear question).
John
--
John Harris
>Captain Paralytic wrote:
>>>>> I am trying to get all 5 numbers, 1-5, each time but in a different
>>>>> order each time ...
>>>
>>> the order may be repeated at random intervals - is this what you mean?
>>
>> You really should try to get your brain in gear before you start your
>> fingers up. The above 2 statements are mutually exclusive and as TNP
>> points out, the first is impossible.
>
>There is a degree of ambiguity. "In a different order *each* time" is
>not the same as "In a different order *every* time". The difference is
>subtle, but it is there. "Different order *each* time" allows the
>possibility that it need only be different from the immediately previous
>result.
OK! A different order each time would be fine! The reason for this is
to minimise any memory effect since users are asked similar questions
in a previous different context.
Cheers
Geoff
> OK! A different order each time would be fine! The reason for this is
> to minimise any memory effect since users are asked similar questions
> in a previous different context.
The problem is rather simple,
Just get a random integer number between 0 and incl 4.
Check if that number is already given away.
Do this till you have all five.
Return them in an array all incremented by one:
<script type='text/javascript'>
function getSequence() {
var n,result = [],ar = [0,0,0,0,0];
while (result.length<5) {
n = Math.floor(5*Math.random());
if (ar[n]==0) {
ar[n] = 1;
result.push(n+1);
};
};
return result;
};
alert(getSequence());
</script>
Evertjan,
I found some code which I slightly altered to give the effect I am
looking for - regret have lost track of where I found it.
Is this overkill for what I want?
Cheers
Geoff
var unSorted = new Array( 5 );
var randomlist = new Array( 5 );
unSorted[ 1 ] = 1;
unSorted[ 2 ] = 2;
unSorted[ 3 ] = 3;
unSorted[ 4 ] = 4;
unSorted[ 5 ] = 5;
function Random( low, high ) {
return Math.floor(Math.random() * ( 1 + high - low ) + low );
}
for( ii=1; ii<=5; ii++ ) {
randomlist[ ii ] = ii;
}
for( ii=1; ii<=5; ii++ ) {
var randomNumber = Random( 1, 5 );
var temp = randomlist[ ii ]
randomlist[ ii ] = randomlist[ randomNumber ]
randomlist[ randomNumber ] = temp
}
for( ii=1; ii<=5; ii++ ) {
document.write(unSorted[randomlist[ ii ]]+"<br>")
}
>
> I found some code which I slightly altered to give the effect I am
> looking for - regret have lost track of where I found it.
>
> Is this overkill for what I want?
It is nearly the same Idea as I posted just now,
but my code seems more consize.
Always try first to verbally write out what the code should do before
programming.
Then write the code.
Then debug till the wole thing works.
I do not like the searching for an other one's code for a simple task like
this, as your own code and your own mistakes will teach you to become
better.
That is why I suggest next time start with your own code, and ask where you
get stuck.
So, the first random number you pick will always get used.
For your second number, you'll use, on average 1.25 random numbers.
For your third number, you'll use 1.66 random numbers
In tests I ran (I didn't trust my maths, above) I actually used 11.41
calls to random for each list of 5 numbers that I generate.
If you want only a small number of lists, and five was not just a small
number used as an example list length, then this is OK.
I ran a program that generates 100,000 of these lists.
When the number of entries in each list was 5, it took 2.2 seconds
When entries=10, it took 6 seconds
When entries=20, it took 22.5 seconds.
So, doubling the length of the lists more than trebles the time it takes.
My suggestion of generating a list of the possible list entries, picking
one at random, then removing it from the list, increases almost linearly
with list length. At least, it did the last time I benchmarked the
actual code that I use.
I was aiming at lists with thousands of entries, though. Eventually you
could spend many minutes just hunting for the last number in the list.
When I was in my first year at Grammar School, one of my classmates
asked "Sir, Can I open the window?", to which the English master replied
"Yes". When he opened the window, the master told him to write an essay
on the difference between "can" and "may".
If you'd approached the door not knowing whether or not the door could
be opened, how would you ask if you could open the door?
Me, I'd ask "can I open the door?", but I'm a pedant, a different sort
of disease.
>Geoff Cox wrote on 11 aug 2009 in comp.lang.javascript:
>
>> OK! A different order each time would be fine! The reason for this is
>> to minimise any memory effect since users are asked similar questions
>> in a previous different context.
>
>The problem is rather simple,
>Just get a random integer number between 0 and incl 4.
>Check if that number is already given away.
>Do this till you have all five.
>Return them in an array all incremented by one:
>
><script type='text/javascript'>
>
>function getSequence() {
> var n,result = [],ar = [0,0,0,0,0];
>
> while (result.length<5) {
> n = Math.floor(5*Math.random());
> if (ar[n]==0) {
> ar[n] = 1;
> result.push(n+1);
> };
> };
> return result;
>};
>
>alert(getSequence());
>
></script>
thanks Evertjan for the code and the explanation.
Cheers
Geoff
> var n,result = [],ar = [0,0,0,0,0];
>
> while (result.length<5) {
> n = Math.floor(5*Math.random());
> if (ar[n]==0) {
> ar[n] = 1;
> result.push(n+1);
> };
> };
> return result;
The traditional shuffling algorithm swaps elements in the array
instead, and only uses n-1 calls to random.
function shuffle(array) {
for (var i = array.length; i > 1; i--) {
// Elements above index i have been selected randomly.
var p = Math.floor(Math.random() * i);
var tmp = array[p]; // an omit swapping if i == p
array[p] = array[i - 1];
array[i - 1] = tmp;
}
}
However, if it is very important that all outcomes are exactly equally
likely, this algorithm actually fails that criteria, and the one above
works (if Math.random() is fair).
/L
--
Lasse Reichstein Holst Nielsen
'Javascript frameworks is a disruptive technology'
> Evertjan. wrote:
>> The problem is rather simple,
>> Just get a random integer number between 0 and incl 4.
>> Check if that number is already given away.
>> Do this till you have all five.
>
[..]
> So, doubling the length of the lists more than trebles the time it
> takes.
[...]
You are not called Swifty without reason, it seems.
The say 200 milisecs are unimportant if you want a random order of a
list of 5 questions on a page [the OP Geoff finally specified that to be
the Q] which 5 questions possibly would take more than 20 minutes to
answer.
Indeed if the execution time of random operations and the opposite,
sorting escalates, optimalisation is necessary.
==============
In this case, probably [Geoff am I right?] 5 or 6 sequenses are enough
to confuse the student examined, so a random choice between those 6
would be perfect. [This is a typical task that should be done with
serverside coding, eliminating manipulation by the student]
So if you go for milisecond speed and do not mind superficial
randomness, take this one, Geoff:
<script type='text/javascript'>
function getSequence() {
var n, sequences = [
[5,3,1,2,4],
[1,4,2,5,3],
[4,3,2,5,1],
[3,1,5,4,2],
[2,5,3,1,4],
[4,2,5,3,1]
]
n = Math.floor(6*Math.random());
return sequences[n];
In a random order:
[1,2,3,4,5].sort(function () { return 1- 2*(Math.random() < .5); })
e.g.:
javascript:do { alert([1,2,3,4,5].sort(function () { return 1- 2*
(Math.random() < .5); })); } while (confirm("Another one ?"))
--
Jorge.
Jorge
I have added as follows and can use your code
var newArray = [1,2,3,4,5,6,7,8,9,10].sort(function () { return 1-
2*(Math.random() < .5); });
alert(newArray);
but could you set it out in a slightly more long winded way so that I
can follow it?!
Cheers
Geoff
> optimistx wrote:
[About asperger]
...
> Me, I'd ask "can I open the door?", but I'm a pedant, a different sort
> of disease.
Although the two are often correlated :)
> In a random order:
>
> [1,2,3,4,5].sort(function () { return 1- 2*(Math.random() < .5); })
>
> e.g.:
>
> javascript:do { alert([1,2,3,4,5].sort(function () { return 1- 2*
> (Math.random() < .5); })); } while (confirm("Another one ?"))
I would not recommend this for shuffling. Its unlikely to give a
sufficiently even distribution of the resulting arrays.
The exact bias depends on the implementation of the sort function,
but for something like insertion sort (often used for small arrays),
an element moves only an average of two locations away from its
start position (independently of the lenght of the array).
Even worse, if the comparison function is not consistent (comparing
the same two elements twice doesn't necessarily give the same result),
or even reflexive (an element isn't equal to itself), some algorithm
implementations might never terminate!
(I've seen that in a quicksort implementation that assumed that the
pivot would be equal to itself).
>Jorge <jo...@jorgechamorro.com> writes:
>
>> In a random order:
>>
>> [1,2,3,4,5].sort(function () { return 1- 2*(Math.random() < .5); })
>>
>> e.g.:
>>
>> javascript:do { alert([1,2,3,4,5].sort(function () { return 1- 2*
>> (Math.random() < .5); })); } while (confirm("Another one ?"))
>
>I would not recommend this for shuffling. Its unlikely to give a
>sufficiently even distribution of the resulting arrays.
Lasse,
Oh dear!
Could you please show me how then you think best to re-order 1,2,3,4,5
in different ways?
thanks
Geoff
> Could you please show me how then you think best to re-order 1,2,3,4,5
> in different ways?
There is no "best way" in programming, that is just personal,
it depends on your requirements, your prefrerences, your mood.
What I like most is not what you could think best, as my mood is mostly
jocular,and I like to make some jokes even in my private script code,
and I like strict readable script formatting, but do not like to much
comment behind //s.
If you do not mind the time taken for the process and the impact on the
cpu, but require a strict randomness, then you will write a totally
differend code from when time/cpu is at the essense, but the randomness
is only secondary.
Do you like nicely readable script source?
Do you want the intermediate values understandably named and the code
chopped in intermediate variables for readability or for easier
debugging?
Do you want the shortest script character count for quicker download?
Do you want obfuscation, so that the first moron cannot reuse your code?
Like I showed you, your requirement probably does not need more than 6
different sequences, so randomizing those would be very fast cpu wize.
Then again if you do clientside code, the cpu time spent is not that
important in your case.
But if you do serverside coding on a heavily used server, the cpu time is
important.
Do you want primarily to be sure that the same sequence does not occur
following the former? Then perhaps do rotating sequences in stead of
randomized sequences. Quick and dirty programmingwize and cpu/runtime-
wize.
Perhaps you have 10 students each with their own laptop sitting next to
eachother, and you do not want them to to work on the same question at
the same time? Here serverside programming is best, but a large random
number of sequences would be a good second choice.
So there is no "best" code in programming, Geoff.
[].sort(f(a,b));
Arrays inherit .sort method that accepts a function f(a,b) -to compare
the values- that returns a negative value if a < b, 0 if a == b, or a
positive value if a > b.
What I did is provide an f that returns either 1 or -1, randomly.
It kind of works, but -as Lasse has pointed out wisely- it's not a
good idea for the reasons he has given already, and also because it
will often take an unnecessarily large number of iterations to get it
(un) "sorted" :
javascript:while(confirm((n=0, [0,1,2,3,4,5,6,7,8,9].sort(function ()
{ n++; return 1- 2* (Math.random() < .5); })+ "\r\niterations: "+ n)))
{}
--
Jorge.
function unSort (oldArray) {
var newArray= [];
while (oldArray.length) {
newArray.push( oldArray.splice(oldArray.length* Math.random(),
1) );
}
return newArray;
}
unSort( [0,1,2,3,4,5,6,7,8,9] );
javascript:function unSort (oldArray) { var newArray= []; while
(oldArray.length) { newArray.push(oldArray.splice(oldArray.length*
Math.random(), 1)); } return newArray; } while (confirm(unSort
([0,1,2,3,4,5,6,7,8,9]))){}
--
Jorge.
One problem with this is that it returns a new, different array
object, and that it destroys the oldArray object.
If you'd need/want to preserve the oldArray object intact (just
unSorted), we'd need to re-fill it :
function unSort (oldArray) {
var newArray= [];
while (oldArray.length) {
newArray.push( oldArray.splice(oldArray.length* Math.random(),
1) );
}
while (newArray.length) {
oldArray.push( newArray.splice(0, 1) );
}
return oldArray;
}
javascript:function unSort (oldArray) { var newArray= []; while
(oldArray.length) { newArray.push( oldArray.splice(oldArray.length*
Math.random(), 1) ); } while (newArray.length) { oldArray.push
( newArray.splice(0, 1) ); } return oldArray; } while (confirm(unSort
Shouldn't that be:
function unSort(oldArray) {
var newArray = [ ];
while (oldArray.length) {
newArray.push(
oldArray.splice(oldArray.length * Math.random(), 1)[0] );
// ^^^
}
while (newArray.length) {
oldArray.push( newArray.splice(0, 1)[0] );
// ^^^
}
return oldArray;
}
I would also refill original array with simple assignment, rather than
splicing (for performance reasons):
...
var i = newArray.length;
while (i--) {
oldArray[i] = newArray[i];
}
...
[...]
--
kangax
Oh, yes:
javascript:alert(Object.prototype.toString.call([1].splice(0,1)));
-> [object Array]
> I would also refill original array with simple assignment, rather than
> splicing (for performance reasons):
>
> ...
> var i = newArray.length;
> while (i--) {
> oldArray[i] = newArray[i];}
>
Yes too... it's faster. (and as it duplicates the array, it also
requires/uses twice as much memory)
Another "duplicator", single-liner, using the evil eval, for these
arrays containing only numeric values, could have been:
eval("oldArray.push("+ newArray.join() +")");
Thanks !
--
Jorge.
It will not matter for 5 elements; but that method is unnecessarily
inefficient and not especially short. Read the FAQ, etc.
--
(c) John Stockton, near London. *@merlyn.demon.co.uk/?.?.Stockton@physics.org
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Correct <= 4-line sig. separator as above, a line precisely "-- " (SoRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SoRFC1036)
Experiment has proved that the approach you recommend generally yields,
for this task, something unnecessarily slow or lengthy, or which does
not give ALL outcomes with nominally equal probability.
The best approach may well be to Google for words describing the task in
combination with the magic strings Donald & Knuth. Try deal shuffle
javascript knuth for example.
--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk Turnpike v6.05 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.
>First create a string '12345'
>Then loop five times:
> Select a random number from 1 to {length of string}
> (probably 0 to length-1 for JavaScript)
> Pick the letter at that offset as your next number
> Delete that letter from the string
>
>This has the advantage that you loop only 5 times. If you pick random
>numbers from 1 to 5 and ignore ones you've already used, you risk
>wasting time, possibly for minutes. or even until the universe ends if
>your luck is as bad as mine sometimes is.
>
>It gets inefficient when you are picking from much larger ranges, as
>you are continually shrinking the initial string. Depending on how this
>is handled, it might range from quick to very slow.
That is, basically, the right algorithm. However, JavaScript is slow at
doing that sort of thing with strings. Use instead an Array; don't
remove, but maintain a marker of the pseudo-end, and, each time, swap a
random one with the pseudo-end one, and shift the end down.
That gets you to the Fisher-Yates shuffle , as recommended by sages.
However, if the result is a to be permutation of sequential digits,
there's no need to start with making a list of them. A Dealing
algorithm will generate then as needed, saving time.
--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk DOS 3.3 6.20 ; WinXP.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links.
PAS EXE TXT ZIP via <URL:http://www.merlyn.demon.co.uk/programs/00index.htm>
My DOS <URL:http://www.merlyn.demon.co.uk/batfiles.htm> - also batprogs.htm.
The singular is "criterion" <g>.
Have you a proof that, for perfect Math.random, that code does NOT give
a perfectly even distribution? If so, it will be of interest to compare
it with the one which I have which proves that it DOES give a perfectly
even distribution. (I'm assuming that your algorithm has no mistakes in
it).
--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk BP7, Delphi 3 & 2006.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.bancoems.com/CompLangPascalDelphiMisc-MiniFAQ.htm> clpdmFAQ;
NOT <URL:http://support.codegear.com/newsgroups/>: news:borland.* Guidelines
Then search the FAQ for the exact words "Deal" and/or "Shuffle". That
will indicate all that you need to know. Or consider sig line 3.
If you want all the possibilities from 12345 to 54321 in a random order,
then repeating in the same of a different random order. then work by
generating an array of the permutations (js-misc0.htm) and shuffling it.
If you want to choose at random, but rejecting ones that have recently
appeared, then maintain either an LRU list or, for each entry, an "age".
--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk IE7 FF3 Op9 Sf3
news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
<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.
Unwise.
>var newArray = [1,2,3,4,5,6,7,8,9,10].sort(function () { return 1-
>2*(Math.random() < .5); });
Specification stipulates that the function used for sorting is
deterministic. Breach that, and there is no guarantee what may happen;
in particular, it may depend strongly in browser sort internals.
Tests have shown the method to be slower than a well-coded Fisher-Yates
in at least one "popular" browser.
It's a good idea to read the newsgroup c.l.j and its FAQ. See below.
>In comp.lang.javascript message <Xns9C64CDE5...@194.109.133.242>
>, Tue, 11 Aug 2009 18:14:26, Evertjan. <exjxw.ha...@interxnl.net>
>posted:
>>
>>I do not like the searching for an other one's code for a simple task like
>>this, as your own code and your own mistakes will teach you to become
>>better.
>>
>>That is why I suggest next time start with your own code, and ask where you
>>get stuck.
>
>Experiment has proved that the approach you recommend generally yields,
>for this task, something unnecessarily slow or lengthy, or which does
>not give ALL outcomes with nominally equal probability.
>
>The best approach may well be to Google for words describing the task in
>combination with the magic strings Donald & Knuth. Try deal shuffle
>javascript knuth for example.
Thanks John - I have done that and am trying a Javascript Knuth
version.
Cheers
Geoff
A perfect Math.random would be great, but if we assume that it's
a PRNG (pseudo-random number generator) that generates a finite number
of results in the range [0..1[ with equal probability, then we get
the problem.
Shuffling n+1 elements makes n calls to Math.random. If there are k
different possible results, then there are k^n different outcomes.
However, there are (n+1)! different ways to shuffle, and (n+1)!
doesn't divide k^n in general (it might for small n and special k
values, but you can pick an n s.t. it doesn't ... usually n = 3
suffices because k is a power of 2).
I.e., each possible permuatation can't have the same probability.
> If so, it will be of interest to compare
> it with the one which I have which proves that it DOES give a perfectly
> even distribution. (I'm assuming that your algorithm has no mistakes in
> it).
If Math.random is perfectly random, with each sampling
Math.floor(Math.random() * i)
giving all integer values in the range [0..i[ with equal probabilty,
*and* samplings being independent, then the shuffling is perfect.
With PRNG's based on manually multiplying a floating point number, the
the integer values are typically not equally likely.
Tests (see in my js-randm.htm) have shown that Math.random() in most
browsers does not generate only & all possible X = N*2^-53 for 0<=X<1;
but, as you realise, I am here considering only the algorithm, not
Math.random itself. Marsaglia's method, as recently discussed here -
Google the group for Baagoe - is very much better than any likely
Math.random for generating random numbers.
>Shuffling n+1 elements makes n calls to Math.random. If there are k
>different possible results, then there are k^n different outcomes.
But there are not constant k different possible results of those
Math.floor calls. k is n, n-1, n-2, ... 2 and k^n is replaced by n!.
>However, there are (n+1)! different ways to shuffle, and (n+1)!
>doesn't divide k^n in general (it might for small n and special k
>values, but you can pick an n s.t. it doesn't ... usually n = 3
>suffices because k is a power of 2).
>I.e., each possible permuatation can't have the same probability.
Then there are exactly the right number of possible paths, each
generating a different number. See my pas-rand.htm, referenced from js-
randm.htm.
>> If so, it will be of interest to compare
>> it with the one which I have which proves that it DOES give a perfectly
>> even distribution. (I'm assuming that your algorithm has no mistakes in
>> it).
>
>If Math.random is perfectly random, with each sampling
> Math.floor(Math.random() * i)
>giving all integer values in the range [0..i[ with equal probabilty,
>*and* samplings being independent, then the shuffling is perfect.
>With PRNG's based on manually multiplying a floating point number, the
>the integer values are typically not equally likely.
That is at most slightly true (but not very important if the float is a
good random Double). The requirement for perfection of the algorithm is
that the results of the function (used to be Random) given in the FAQ
are perfect.
function Random(X) { return Math.floor(X*(Math.random())) }
If perfection is more important than speed, then one can use the
previously-cited KISS2007 (or better) to generate pairs of good 32-bit
randoms, then use exactly 53 of those bits to be (in effect) the un-
normalised mantissa of a Double. That avoids the defects of most
implementations of Math.random.
Or one can use, to generate a random integer in 0 to K, KISS to generate
a sufficiently long random number, then mask it with the MSB of K
followed by all ones, then accept only if <= K otherwise try again. An
average of two tries should be needed.
The ECMA & ISO/IEC standards should be upgraded to specify that
Math.random() generates only all possible X = N*2^-53 for 0<=X<1; that's
easy enough to code for in C or ASM. Also, whether a cycle length of
2^53 is allowed. Disallowing Lehmer generators may be a step too far.