Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Rearrangement of a sequence into random order

• To: mathgroup at smc.vnet.net
• Subject: [mg28452] Re: [mg28434] Rearrangement of a sequence into random order
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Thu, 19 Apr 2001 03:26:41 -0400 (EDT)
• References: <200104180723.DAA17248@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Loren Dill wrote:
> 
> Hi,
> 
> I'm a math teacher, and need to prepare exams from time to time.  I
> typically prepare questions for the exam in a sequential order starting at
> the beginning of the material and going to the end.  I may have something
> like 20 short-answer questions.  I want a program that will randomize the
> order of the questions.  In other words, I want to provide n, the number of
> questions, and have the program provide a list of length n that contains all
> the numbers from 1 to n in a random order without any number being repeated
> or omitted.  I'm sure that this is an easy task for Mathematica, but I can't
> figure out the best way to do it.
> 
> Loren Dill

This amounts to the basic shuffle-a-deck problem that has come up
several times in one guise or another over the past year or so. Below is
some code to do it. The idea is to iterate over the list of
{1,2,...,20}. At each position, pick a random position between that one
and the size of the list (inclusive of endpoints). Swap the elements at
those positions. This can be shown to give a uniform random shuffle.

shuffle = Compile[{{n,_Integer}},
  Module[{deck=Range[n], newj},
    Do[
      newj = Random[Integer, {j,n}];
      deck[[{j,newj}]] = deck[[{newj,j}]],
      {j,n-1}
      ];
    deck
    ]
  ]

Example:
In[9]:= shuffle[20]
Out[9]= {16, 1, 19, 12, 6, 18, 15, 3, 4, 9, 2, 20, 5, 13, 14, 8, 11, 10,
17, 7}

I use Compile in the code because, for large sets, it makes a
significant difference in speed. Actually I don't feel compelled to
apologize for this small added code complexity, because you tacitly
requested "the best way to do it". It may be quite useful if instead you
give an exam with 20 million questions:

In[13]:= Timing[shuffleddeck = shuffle[20000000];]
Out[13]= {578.71 Second, Null}

This is substantially the same code as I used in a conference notebook
that covers this topic among many others. It may be found at the URL
below.

http://library.wolfram.com/conferences/conference98/abstracts/symbolic_FAQ.html


Daniel Lichtblau
Wolfram Research

• References:
  • Rearrangement of a sequence into random order
    • From: "Loren Dill" <lorendill@mediaone.net>