The Four Digit Problem

So I was remembering a piece of code I had to write once. Honestly I don’t remember exactly why I had to write it. I think it may have been part of a set of patterned data for some test software though. In any case the problem was to generate a four digit random number with no duplicated digits. Now there are lots of ways to do this. A simple brute force way is below.

     Function Digit4() As Integer

        Dim i(4) As Integer
        i(0) = r.Next(1, 9)
        Do
            i(1) = r.Next(0, 9)
        Loop Until i(1) <> i(0)
        Do
            i(2) = r.Next(0, 9)
        Loop Until i(2) <> i(0) And i(2) <> i(1)
        Do
            i(3) = r.Next(0, 9)
        Loop Until i(3) <> i(0) And i(3) <> i(1) And i(3) <> i(2)
        Return i(0) * 1000 + i(1) * 100 + i(2) * 10 + i(3)
    End Function

Yes I left out the comments to save space. (That’s my story and I’m sticking to it) The way it works is to pick a single random digit, then pick a second one looping back to pick a new one if by some chance the digit drawn is the same as the one previously checked. This is done again except that the next one has two numbers to compare against and the final number has three numbers to compare against. It works (I tested it) but it doesn’t scale well.

The task I would assign students is to come up with at least two other ways to solve this problem that are more scalable and then compare them all for performance. I might hint at the word “recursion” which I’ve been thinking a lot about lately. This sample code is in Visual Basic because that is my hack something together language of choice. Converting it to other languages is another exercise left to the student.

Two notes: The best part about this post is all the discussion in the comments so don't miss them. Second is that the "solution" I entered is what students often come up with and not what I would use is a real application. I wanted to get some discussion going and that seems to have happened.

Edit: 12/2/2009 Bart Massey

of Portland State University has a very helpful reply post called Random non-repeating sequences that I highly recommend. I appreciate his letting me know about it as I think it is an interesting solution that is well explained. So please go read it.