Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

More Than Good Enough for Homework

April 06, 2011

In an earlier column, I discussed an incorrect solution to the problem of putting the elements of an array in a random sequence. Trying to find a correct solution, a reader made the following suggestion in a comment:

It seems that a reasonable approach is to start with the first element and to randomly assign it a new position in a new array. Then take the remaining elements in turn and randomly assign each a position in the new array. This immediately runs afoul of the possibility of collisions. What do you do if the random element in the new array has already been filled?

There are numerous possibilities: 1) take the next empty position, 2) recalculate the random assignment until you don't get a collision.

This strategy seems at first like it might not generate the right answer. After all, suppose there are 12 elements to be distributed in this way. You put the first element somewhere, say in position number 5. Now the probability of the second element being in position number 5 is zero, because the first element is already there. So how can you possibly say that each element has the same probability of being in each possible position?

The answer is subtle, because it has to do with conditional probability -- the notion that making two choices in sequence has a different effect from making those choices together. In this case, we can think of it this way: 1/12 of the time, the first element went into position 5. The remaining 11/12 of the time, the first element went somewhere else and position 5 was still clear.

When it came time to place the second element, position 5 was already full 1/12 of the time. The rest of the time, there were 11 places where that second element could go, so it would go into position 5 1/11 of the time. Therefore, the probability of the second element going into position 5 is

1/12 * 0 (the case where the first element was in position 5) +
11/12 * 1/11 (the case where the first element went somewhere else)
 

Of course, 11/12 * 1/11 is 1/12 -- which means that the second element also goes into position 5 with probability 1/12. Similar reasoning will eventually show that each element has the same probability of being in each position when we're all done.

However, as the reader noted, this algorithm has a recordkeeping problem: When we put elements in random positions, we have to keep track of which ones are full. For this reason, it is easier to put randomly selected elements into sequential positions.

Here's one way to do it. Assume that v is a vector with n elements, numbered v[0] through v[n-1], and that nrand(n) is a function that returns a uniformly distributed random integer such that 0 ≤ nrand(n) < n. Then we can solve the problem this way:

     size_t i = n;
     while (i > 1) {
           std::swap(v[i-1], v[nrand(i)]);
           --i;
     }

This example has a few subtleties, but basically it swaps each element of v in turn with an element that strictly precedes that element in v. I could have written it to start from the beginning of v, but the code would be more complicated -- try it yourself and see.

Let's look at what happens the first time through the loop. The variable i starts out being equal to n, provided that i > 1. Is it correct to stop if i is equal to 1? Yes, because in that case, the vector has only one element, and we can't do anything about shuffling it.

In the loop, we swap v[i-1] with a randomly selected element of v with an index strictly less than i. Because we have called nrand(i), not nrand(i-1), it is possible that we will swap v[i-1] with itself; this possibility is intentional. After the first swap, it should be clear that v[i-1] is now a randomly selected element of v, and the former value of v[i-1] has been swapped to an earlier position in v.

Once we have used swap to place the last element of v, we do not touch that element again. Instead, we swap one of the remaining elements into the previous position, and so on backward through the vector. We stop before we reach the first element of v, because when there is only one element left, there is no other element to swap there.

Notice that this solution is similar in effect to the erroneous one that began the discussion in my earlier note. In fact, we can transform this solution into that one by changing nrand(i) to nrand(n) and changing the loop to visit the entire vector instead of skipping the v[0]. Nevertheless, the reasoning process that went into this seemingly simple change is trickier than it looks:

  1. We observed that the original algorithm chose from among nn results, whereas to be correct it would have had to choose from among a multiple of n! results, and in general, n! does not divide nn.
  2. We next observed that we can randomize a sequence by ensuring that one element of that sequence is randomly chosen, and then (recursively) randomizing the rest of the sequence.
  3. Finally, we found a simple iterative expression of our strategy.

So now we have a solution to our problem that is more than good enough for homework. Of course, in the real world, I hope we would bypass all of this effort and use std::random_shuffle instead.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video