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

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

alanbe
Guest
Posts: n/a

 05-27-2005
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
Guest
Posts: n/a

 05-27-2005
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] = i;
}

slot.shuffle();

where the shuffle method is defined by:

Array.prototype.swap = function(i, j) {
var t = this[i]; this[i] = 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

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

alanbe
Guest
Posts: n/a

 05-28-2005
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
Guest
Posts: n/a

 05-28-2005
JRS: In article <rPJle.40952\$(E-Mail Removed)> , dated
Fri, 27 May 2005 18:39:19, seen in news:comp.lang.javascript, Michael
Winter <(E-Mail Removed)> posted :

>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

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.

--
<URL:http://www.jibbering.com/faq/> JL/RC: FAQ of news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.

Michael Winter
Guest
Posts: n/a

 05-28-2005
On 28/05/2005 16:42, Dr John Stockton wrote:

> JRS: In article <rPJle.40952\$(E-Mail Removed)> , dated
> Fri, 27 May 2005 18:39:19, seen in news:comp.lang.javascript, Michael
> Winter <(E-Mail Removed)> 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).

[snip]

Mike

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

fox
Guest
Posts: n/a

 05-29-2005

Michael Winter wrote:
> On 28/05/2005 16:42, Dr John Stockton wrote:
>
>> JRS: In article <rPJle.40952\$(E-Mail Removed)> , dated
>> Fri, 27 May 2005 18:39:19, seen in news:comp.lang.javascript, Michael
>> Winter <(E-Mail Removed)> 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).
>
> [snip]
>
> Mike
>

2 cents worth:

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

Dr John Stockton
Guest
Posts: n/a

 05-30-2005
JRS: In article <d7cc6v\$5mh\$(E-Mail Removed)>, dated Sun, 29 May
2005 07:22:39, seen in news:comp.lang.javascript, fox
<(E-Mail Removed)> posted :
>Michael Winter wrote:
>> On 28/05/2005 16:42, Dr John Stockton wrote:
>>
>>> JRS: In article <rPJle.40952\$(E-Mail Removed)> , dated
>>> Fri, 27 May 2005 18:39:19, seen in news:comp.lang.javascript, Michael
>>> Winter <(E-Mail Removed)> 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
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>.

--
<URL:http://www.jibbering.com/faq/> JL/RC: FAQ of news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.

Tony
Guest
Posts: n/a

 05-31-2005

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>
<title>Shuffler</title>
<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] = 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[i] = r;
}
}

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

</script>

</body>
</html>

Michael Winter
Guest
Posts: n/a

 05-31-2005
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

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

Dr John Stockton
Guest
Posts: n/a

 05-31-2005
JRS: In article <(E-Mail Removed). com>,
dated Tue, 31 May 2005 06:03:31, seen in news:comp.lang.javascript, Tony
<(E-Mail Removed)> posted :
>
>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[i] = r;
>}
>}

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 /// ???

--
<URL:http://www.jibbering.com/faq/> JL/RC: FAQ of news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.