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

Discussion in 'Javascript' started by alanbe, May 27, 2005.

  1. alanbe

    alanbe Guest

    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
     
    alanbe, May 27, 2005
    #1
    1. Advertising

  2. Re: How to create an array of unique random numbers for an onlinequiz

    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

    --
    Michael Winter
    Replace ".invalid" with ".uk" to reply by e-mail.
     
    Michael Winter, May 27, 2005
    #2
    1. Advertising

  3. alanbe

    alanbe Guest

    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
     
    alanbe, May 28, 2005
    #3
  4. JRS: In article <rPJle.40952$>, dated
    Fri, 27 May 2005 18:39:19, seen in news:comp.lang.javascript, Michael
    Winter <> 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
    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.

    --
    © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
    <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.
    <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
     
    Dr John Stockton, May 28, 2005
    #4
  5. Re: How to create an array of unique random numbers for an onlinequiz

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

    > JRS: In article <rPJle.40952$>, dated
    > Fri, 27 May 2005 18:39:19, seen in news:comp.lang.javascript, Michael
    > Winter <> 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.
     
    Michael Winter, May 28, 2005
    #5
  6. alanbe

    fox Guest

    Re: How to create an array of unique random numbers for an onlinequiz

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

    --
    © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
    <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.
    <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
     
    Dr John Stockton, May 30, 2005
    #7
  8. alanbe

    Tony Guest

    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>
     
    Tony, May 31, 2005
    #8
  9. Re: How to create an array of unique random numbers for an onlinequiz

    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.
     
    Michael Winter, May 31, 2005
    #9
  10. JRS: In article <>,
    dated Tue, 31 May 2005 06:03:31, seen in news:comp.lang.javascript, Tony
    <> 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 = 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 /// ???

    --
    © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
    <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.
    <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
     
    Dr John Stockton, May 31, 2005
    #10
  11. Re: How to create an array of unique random numbers for an onlinequiz

    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

    --
    Michael Winter
    Replace ".invalid" with ".uk" to reply by e-mail.
     
    Michael Winter, Jun 1, 2005
    #11
  12. Michael Winter wrote:
    > 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>

    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.
     
    Richard Cornford, Jun 1, 2005
    #12
  13. JRS: In article <Ug6ne.43070$>,
    dated Tue, 31 May 2005 23:18:12, seen in news:comp.lang.javascript,
    Michael Winter <> posted :
    >On 31/05/2005 23:32, Dr John Stockton wrote:


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


    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.

    --
    © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
    <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.
    <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
     
    Dr John Stockton, Jun 1, 2005
    #13
  14. Re: How to create an array of unique random numbers for an onlinequiz

    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

    --
    Michael Winter
    Replace ".invalid" with ".uk" to reply by e-mail.
     
    Michael Winter, Jun 2, 2005
    #14
  15. JRS: In article <Ldsne.43751$>,
    dated Thu, 2 Jun 2005 00:16:43, seen in news:comp.lang.javascript,
    Michael Winter <> posted :
    >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.

    --
    © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
    <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.
    <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
     
    Dr John Stockton, Jun 2, 2005
    #15
  16. Re: How to create an array of unique random numbers for an onlinequiz

    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

    --
    Michael Winter
    Replace ".invalid" with ".uk" to reply by e-mail.
     
    Michael Winter, Jun 3, 2005
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. lallous
    Replies:
    5
    Views:
    576
    lallous
    Oct 20, 2003
  2. Xoomer

    Unique Random Numbers

    Xoomer, Mar 25, 2007, in forum: C++
    Replies:
    17
    Views:
    543
    Alexander D. B. Kim
    Apr 11, 2007
  3. globalrev
    Replies:
    4
    Views:
    771
    Gabriel Genellina
    Apr 20, 2008
  4. Jimmy Palmer

    generating unique random numbers

    Jimmy Palmer, Mar 25, 2008, in forum: Ruby
    Replies:
    14
    Views:
    216
    lasitha
    Mar 27, 2008
  5. VK
    Replies:
    15
    Views:
    1,174
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page