Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Good enough for homework?

December 28, 2010

I saw a question--and answer--on an online discussion group recently that made me fear for the future of software engineering.

The question was straightforward enough: You have a 3x4 array. How do you redistribute that array's values randomly? It might be possible to excuse someone asking such an elementary question by noting that this discussion group includes many beginners. What I don't know how to explain, however, is how many people suggested answers that were just plain wrong.In the following discussion, I am going to assume that we have a reliable method of picking a random integer in a given range. As I mentioned recently, this problem is harder than it looks; nevertheless, I'll continue discussing it later.

The first solution that was proposed to the array-scrambling problem seemed reasonable enough on its surface: Look at each element of the array and swap that element with a randomly chosen element. However, as I was looking at that solution, the first thought that came to mind was: Does it work?

For problems of this kind, one way to see whether a proposed solution makes sense is to start with a trivial case. Shuffling a single element is meaningless, so we should start by seeing whether this algorithm works correctly for a 2-element array.

My first thought was that the algorithm is broken even in this simple case. We start by swapping the first element with a random element. Half the time, this does nothing; the other half the time, it interchanges the two elements. Then we swap the second element with a random element, which does the same thing.

In other words--or so I thought--the two elements of the array would be swapped three quarters of the time and left alone one quarter of the time. This behavior can hardly be considered random. So I mentioned that behavior as a problem.

I got two responses, both of which astounded me.

The first was that it didn't really matter that the algorithm fails for two elements, because the problem as assigned was to use a 12-element array. So even if it failed for two elements, that said nothing about whether it would work for twelve.

The second response was that even if the algorithm didn't work, it was "good enough for homework."

Both of these responses run counter to years of experience.

If an algorithm fails on a trivial case, it probably fails on more complicated cases too. It sometimes happens that approximate algorithms work better as the data become larger, but it is a mistake to assume that such improvement will always be the case. If you are trying to solve a problem, and you can prove that your proposed solution fails on a simple version of that problem, the responsible course of action is to understand the reason for that failure before moving on.

The second response makes no sense because an instructor who gives a homework assignment usually does so for the purpose of teaching a particular idea or technique. Problems that are encountered in more practical settings usually occur because of a desire for a particular result. Accordingly, I think that a program that produces a result that is only approximately correct may be good enough in practical applications even when it is not adequate as a solution to a homework problem.

But what really amazed me about the responses to my comment is that not one single commenter noticed that I was wrong. In fact, the algorithm that was suggested does work for a two-element array. It fails only when there are three or more elements in the array.

The easy way to see that it works for a two-element array is to realize that once you've swapped the elements with probability 0.5, those elements are now randomly ordered. Unless you know whether they were swapped, anything you do in the future will not affect that randomeness. Another way to look at it is that the number of swaps will be 0 one quarter of the time, 1 half the time, and 2 the remaining quarter of the time. Swap a pair of elements twice and you get back to where you started. So in fact my original claim about the algorithm was wrong: It does work if there are only two elements.

However, I stand by my claim that it fails for three elements. The number of distinct ways of permuting three elements is 3! (3 factorial), and the number of distinct sequences of random swaps among three elements is 3^3 (3 to the 3rd power). 3^3 has only 3 as its factors, but 3! has 2 as a factor, so there is no way to arrange 3^3 sequences of swaps to produce 3! equally likely outcomes.

This line of reasoning generalizes to an array with 12 elements: The number of sequences of swaps is 12^12, but the number of possible permutations is 12!. 12! has 11 as a factor, but 12^12, like any power of 12, has only 2 and 3 as its prime factors. So the technique of swapping each element in turn with a randomly chosen element cannot possibly result in a uniformly random result.

To sum up this comedy of errors: Someone mentioned a homework problem. Someone proposed a possible solution. I claimed that this solution didn't work even for a trivial case, so one should not trust it for the actual problem. The responses included two rebuttals that I consider specious, but failed to notice either that my claim was incorrect for the specific example I cited, or that my claim was correct in the more general case.

I think the most important lesson to learn from this experience is that problems that seem simple are sometimes harder than they look, and it is easy to make mistakes when one reasons about probability.

My next post will talk about how to solve this problem for real.Even if the algorithm didn't work, it was "good enough for homework."

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