How to create an array of unique random numbers for an online quiz

[alanbe]

Greetings

I am making a flashcard type application to help me in my TCP/IP
protocols test.
My instructor will test us periodically on how a device or networking
function relates to the OSI layer. EG. bits-layer 1.
Any way, I want the quiz to reorder the problems each time I take it.

Here is part of the code i did so far for 62 components in the quiz.


var slot=new Array(62);
var test=0;

for(n=0;n<62;n++)
{
slot[n]=99;
}

do
{
test=Math.floor(62*Math.random());
if (slot[num]==99)
{
slot[num]=test;
num++;
}
} while (num<62);

}


The problem is, I don't get a different number in each slot. What am I
missing here. Also, is there a more efficient way to do this?


allen

 

[Michael Winter]

On 27/05/2005 18:35, alanbe wrote:

[snip]

Any way, I want the quiz to reorder the problems each time I take it.

It would probably be best to shuffle a pre-filled array.

var slot = [];

for(var i = 0; i < 62; ++i) {
slot = i;
}

slot.shuffle();

where the shuffle method is defined by:

Array.prototype.swap = function(i, j) {
var t = this; this = this[j]; this[j] = t;
};

Array.prototype.shuffle = function() {
var i = this.length;

while(i--) {
this.swap(i, Math.floor((Math.random() % 1) * (i + 1)));
}
};

[snip]

Mike

 

[alanbe]

Thanks Michael. This helps me. Also had to go back and study all the
methods associated with arrays.
http://4umi.com/web/javascript/array.htm


I am constantly surprised at the power of JavaScript.

I also saw where my code went wrong after I posted the question.

alanbe

 

[Dr John Stockton]

JRS: In article <[email protected]>, dated
Fri, 27 May 2005 18:39:19, seen in Michael

It would probably be best to shuffle a pre-filled array.

It could probably be better; it could not be best, when the array is to
be filled with consecutive numbers.

In that case, one can deal the numbers directly. That removes the
loading loop, and slightly simplifies the arranging loop.

Unless of course one requires the shuffle routine elsewhere and is more
concerned about code size than speed.

Faq 4.22 HTM, blue box, refers.

 

[Michael Winter]

JRS: In article <[email protected]>, dated
Fri, 27 May 2005 18:39:19, seen in Michael

It would probably be best to shuffle a pre-filled array.

[...] one can deal the numbers directly.

I couldn't think of a succinct algorithm at the time of posting, and I
forgot you covered it in addition to shuffling (and drawing).

[snip]

Mike

 

[fox]

JRS: In article <[email protected]>, dated
Fri, 27 May 2005 18:39:19, seen in Michael

It would probably be best to shuffle a pre-filled array.

[...] one can deal the numbers directly.

I couldn't think of a succinct algorithm at the time of posting, and I
forgot you covered it in addition to shuffling (and drawing).

[snip]

Mike

2 cents worth:

http://fxmahoney.com/demo/drawfromdeck.htm

 

[Dr John Stockton]

JRS: In article <[email protected]>, dated Sun, 29 May
2005 07:22:39, seen in fox

JRS: In article <[email protected]>, dated
Fri, 27 May 2005 18:39:19, seen in Michael
Winter <[email protected]> posted :

It would probably be best to shuffle a pre-filled array.


[...] one can deal the numbers directly.

I couldn't think of a succinct algorithm at the time of posting, and I
forgot you covered it in addition to shuffling (and drawing).

2 cents worth:

http://fxmahoney.com/demo/drawfromdeck.htm

The code shown in the page is hard to read, since you override the
readers' choices of font face and style; I see a minute fixed-pitch font
with oblong 0 and square brackets that look almost doubled.

I think that the font face problem is because you have used monospace as
the font name, whereas it should be the font-family name - and there is
in any case no need to specify font-family within pre/xmp, AFAICS.

Font sizes should never be specified in px/pt, unless there is a real
graphics-design need; that is contrary to DDA, ADA, etc. Although,
AIUI, W3 prefers use of em units, % seems more logical to me, if there
is a need to make fonts bigger or smaller.

<FAQENTRY> ISTM that accessibility is important, and javascript can
affect this. Therefore, I suggest a small entry in FAQ Section 4,
mainly as an indication of importance, which would deprecate overriding
readers' choices without true need, link to Web information, deprecate
the unnecessary use of features not common to "all" browsers, and refer
to provision for those without JS. And/or link(s) in Sec 3. </FAQENTRY>



W3's TIDY of 2003-11-01 gives 17 warnings, of 10 types, two of which are
script-related : <script> needs type; in strings, </ should be <\/.
<xmp> is obsolete.



For me, the code does not run; this is because of the use of array
method pop. Where pop is used in demonstration code, ISTM that there
should be a warning that it is comparatively new.

With this change, that part runs for me :
// arr[draw] = arr.pop();
arr[draw] = arr[arr.length-1]; arr.length-- /// ???

Then I get "undefined is undefined"; I tend to use var U and then U
is definitely undefined in value. With that change, the code runs to
completion.


The constants 13 & 52 in the code should be PL = pips.length & PS = PL *
suits.length, or similar. It would then be easier to test for true
randomness with a smaller number of cards.


There's now an algorithm error, or so it seems; consider the first call
of DrawOne, on an array [1,2,3,4,5,6] of length 6.

functiondrawOne(arr){
var draw = Math.floor((arr.length-1) * Math.random());
var copy = arr[draw];
arr[draw] = arr.pop();
return copy }

Now arr.length = 5 and 0 <= Math.random() < 1 ; therefore we will get
0 <= draw < 5 and so copy cannot on this first call return arr[5]==6.

To confirm, we note that in properly dealing a deck of N there are N!
equi-probable possible orders, so we need to be able to get (a multiple
of) N! combinations of results from the randomisation; the code
presented does not provide the leading factor of N.



However, in the present context, none of that matters. The code
presented requires a pre-loaded array, from which it extracts cards; it
is the code for what I term a Draw. (It is not a Shuffle, since it does
not work in-place.) But what the OP calls for is what I term a Deal;
the "cards" are generated (sequentially) during the process and end up
in random order.

Where a Deal is needed, code that Deals is better than code that Draws
or Shuffles. Note that FAQ 4.22 cites <URL: http://www.merlyn.demon.co.
uk/js-randm.htm>.

 

[Tony]

Try this. It's not more efficient but it gets the job done.
ParseInt is used instead because floor tends to discriminate
against the 1st and last array elements being pulled first.

<html>
<head>
<title>Shuffler</title>
</head>
<body>

<script type="text/javascript">

var testArray1 = ["a1","a2","a3","a4","a5","a6"];

var testArray2 = [1,2,3,4,5,6];

var testArray3 = [];
for (i = 0; i < 62; i++){
testArray3 = i;
}

function shuffleThis(a){
var shuffled = [];
for (i = 0; i < a.length; i++){
var r = a[parseInt(Math.random() * a.length)];
for (j = 0; j < a.length; j){
if (r != shuffled[j]){
j++;
}
else{
r = a[parseInt(Math.random() * a.length)];
j = 0;
}
}
shuffled = r;
}
alert("Original\n"+a+"\n\nShuffled\n"+shuffled);
}

shuffleThis(testArray1);
shuffleThis(testArray2);
shuffleThis(testArray3);


</script>

</body>
</html>

 

[Michael Winter]

On 31/05/2005 14:03, Tony wrote:

[snip]

ParseInt is used instead because floor tends to discriminate
against the 1st and last array elements being pulled first.

If you're referring to what I think you are, then you're confusing
Math.round and Math.floor methods. In terms of the end result, parseInt
and Math.floor are the same as both discard the floating point portion
of a number. This leads to an even distribution across the range.
However, using Math.round would create an uneven distribution that would
be biased against the first and last values.

The Math.floor method should be used in preference the parseInt as the
latter must first convert its argument to a string, then parse that back
into an integer. As you know the values are always numbers, this
conversion process is pointless.

[snip]

Mike

 

[Dr John Stockton]

JRS: In article <[email protected]>,
dated Tue, 31 May 2005 06:03:31, seen in Tony

Try this. It's not more efficient but it gets the job done.

It looks less efficient than the method cited in the FAQ, and it is
longer code (which may be good for those paid by the yard). It's rarely
worth re-inventing any wheel that Knuth offers as good.

ParseInt is used instead because floor tends to discriminate
against the 1st and last array elements being pulled first.

Correctly used, it does not. However, IIRC and un-retested at this
moment, if the arrays are not over about 2^31 in length one can truncate
with |0 faster than with Math.floor (faster for at least some browsers).

function shuffleThis(a){
var shuffled = [];
for (i = 0; i < a.length; i++){
var r = a[parseInt(Math.random() * a.length)];
for (j = 0; j < a.length; j){
if (r != shuffled[j]){
j++;
}
else{
r = a[parseInt(Math.random() * a.length)];
j = 0;
}
}
shuffled = r;
}
alert("Original\n"+a+"\n\nShuffled\n"+shuffled);
}

That calls Math.random an uncertain number of times, with a.length
different outcomes each time. Can you prove whether your method
(assuming Math.random to be perfect) gives all possible outcomes equally
probably? It can easily enough be shown that the standard method has
that property.

The code uses global variables i and j. That can have a very
unfortunate effect on a test routine that uses i or j.

Tested with
Z = []
for (jj=0; jj<1200; jj++) {
k = parseInt(shuffleThis([0,1,2,3]).join(''), 4)
Z[k] ? Z[k]++ : Z[k]=1 }
Z.join('x').split(/x+/)
the result Z shows no obvious non-uniformity. 4 is the length of the
array.



+ + +


The following, or similar, *might* be good in recent browsers to shuffle
an array in place; I cannot test it. If all parameters to splice are
evaluated before any other actions are performed, one can omit the use
of T.

function Shuf(A) { var j, k, T
for (j=A.length ; j>1 ; j--) { k = Randum(j)
T = A[k] ; A.splice(k, 1, T) } }

or using instead of the middle line ???
for (j=A.length ; j>1 ; j--) {
if ((k = Randum(j))==j-1) continue /// ???

 

[Michael Winter]

On 31/05/2005 23:32, Dr John Stockton wrote:

[snip]

However, IIRC and un-retested at this moment, if the arrays are not
over about 2^31 in length one can truncate with |0 faster than with
Math.floor (faster for at least some browsers).

Array lengths are capped at 2^32-1, as indicies are exposed to the
internal ToUint32 'operator'.

Operands of the bitwise operators are exposed to ToInt32, and the
specification states that ToUint32(ToInt32(x)) == ToUint32(x).

[snip]

The following, or similar, *might* be good in recent browsers to shuffle
an array in place; I cannot test it.

Good in what respect: performance or result?

[snip]

Mike

 

[Richard Cornford]

On 31/05/2005 23:32, Dr John Stockton wrote:

Array lengths are capped at 2^32-1, as indicies are exposed
to the internal ToUint32 'operator'.

Operands of the bitwise operators are exposed to ToInt32,
and the specification states that ToUint32(ToInt32(x)) ==
ToUint32(x).

<snip>

Disregarding sparse arrays, while the number of possible elements in an
array might be 2^32-1 the vast majority of array applications are not
going to get anywhere near even 2^31. If we (unrealistically, given the
ECMAScript types) assumed just one byte per element, 2^31 elements would
occupy half the physical memory map in a 32 bit OS, and have most
desktop computers swapping memory onto their hard disks at a rate that
would probably render any code using such an array non-viable.

OR zero (or its other bitwise alternatives) should be a viable
alternative to Math.floor in most circumstances when the range was
known, as those ranges would tend to be sufficiently small.

My timing tests suggest that OR zero is between 4 and 14 times faster
than Math.floor, with LRN's suggestion of - n<<0 - or - n>>0 - being at
least as good, with a different spread of performance advantages across
environments. Which makes them good options for tasks that should be
fast, like calculating (integer) pixel positions in
animation/interactive code.

Richard.

 

[Dr John Stockton]

JRS: In article <[email protected]>,
dated Tue, 31 May 2005 23:18:12, seen in

On 31/05/2005 23:32, Dr John Stockton wrote:

Good in what respect: performance or result?

Both.

I usually reckon that untested code is assuredly wrong, but that
particular code does look about right; and as most of the work is done
by a single call there is potential for efficiency by using "internal"
code.

If it's not right for all array lengths from 0 upwards, performance is
irrelevant.


But for the Web, I'd suggest something like

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 }

function Deal(N) { var J, K, Q = new Array(N)
for (J=0; J<N; J++) { K = Random(J+1) ; Q[J] = Q[K] ; Q[K] = J }
return Q }

in which it may be possible to make improvements to the loop handling
but probably not to the algorithms as such.

 

[Michael Winter]

On 01/06/2005 22:15, Dr John Stockton wrote:

[snip]

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 }

Thinking about this, using Array.prototype.splice doesn't, and can't
work, unless I'm missing something.

In your normal Shuffle function, a random element in the array is
swapped with the current element. However, no swapping will occur when
using splice as it's purpose is a combination of deletion and insertion
at an arbitrary location within an array.

[JRS:]

function Shuf(A) { var j, k, T
for (j=A.length ; j>1 ; j--) { k = Randum(j)
T = A[k] ; A.splice(k, 1, T) } }

After execution of the assignment expression on the last line, T will
hold a random element from the array. During completion of the function
call, this value is, in principle, removed from the array then
immediately reinserted.

Granted, this is because one occurrence of k should be j, but then the
removed element will be lost forever as there are no statements that
will reinsert it.

[snip]

For the future, you could use this implementation of the
Array.prototype.splice method:

Array.prototype.splice = function(s, dC) {
var A = [],
l = this.length | 0,
iC = Math.max(arguments.length - 2, 0),
i, j, n, u;
s = Math.floor(+s || 0);
s = (0 > s)
? Math.max(s + l, 0)
: Math.min(s, l);
dC = Math.min(Math.max(Math.floor(+dC || 0), 0), l - s);

i = 0; j = s; while(dC > i) {A[i++] = this[j++];}
if(dC > iC) {
i = s + dC; j = s + iC; while(l > i) {this[j++] = this[i++];}
i = l; n = l - dC + iC; while(i > n) {this[--i] = u;}
} else if(iC > dC) {
i = l; j = l + iC - dC; n = s + dC;
while(i > n) {this[--j] = this[--i];}
}
i = s; j = 2; n = iC + 2; while(n > j) {this[i++] = arguments[j++];}
this.length = l - dC + iC; return A;
};

Aside from some loop optimisations (I need to rewrite a reference
implementation for a proper comparison), this should exhibit
per-specification behaviour, including a somewhat redundant loop that
explicitly deletes elements so that the method can be used generically
on non-array objects.

I'm reasonably confident that it contains no bugs: I ran a comparison
against Firefox's built-in method over a continuous range of input
values that amounted to around 2000 combinations. A well-defined series
of test cases would probably be more reassuring, but I'm not
particularly adept at forming them.

I posted code similar to this in March, but I found that to be erroneous
just recently. I don't know how the problem went unnoticed. The code has
been deleted from the Google Groups archive to try and make sure that
no-one finds and uses it. I should probably see if I can e-mail the OP
of that thread in case he used it (there were other bits of code he
might have chosen instead).

Mike

 

[Dr John Stockton]

JRS: In article <[email protected]>,
dated Thu, 2 Jun 2005 00:16:43, seen in

On 01/06/2005 22:15, Dr John Stockton wrote:

[snip]

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 }

Thinking about this, using Array.prototype.splice doesn't, and can't
work, unless I'm missing something.

For some unknown reason, I was under the impression that splice removed
elements from the "middle" but added them to the end. I think that
would work, since it is not necessary to maintain any particular order
in either the selected or the unselected elements.

For the future, you could use this implementation of the
Array.prototype.splice method:
...

I've put that in js-tests.htm with one simple test to check that I've
not obviously broken it in doing so and the hope of doing more.

 

[Michael Winter]

On 02/06/2005 01:16, Michael Winter wrote:

[snip]

Array.prototype.splice = function(s, dC) {
var A = [],
l = this.length | 0,

To be conforming, that should be:

l = this.length >>> 0,

otherwise values above 2^31-1 would become negative 32-bit integers.

[snip]

Mike