Jaa

The Four Digit Problem

  • Artikkeli

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.

Comments

  • Anonymous
    July 11, 2008
    // how about this solution public static int GetNumber() { Random random = new Random(); int[] digits = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; for (int i = 0; i < 4; i++) { int picked = random.Next(i, 9); if (picked == i) continue; int digit = digits[picked]; digits[picked] = digits[i]; digits[i] = digit; } if (digits[0] == 0) { return digits[1]*1000 + digits[0]*100 + digits[2]*10 + digits[3]; } else { return digits[0]*1000 + digits[1]*100 + digits[2]*10 + digits[3]; } }

  • Anonymous
    July 11, 2008
    I like that one Phil. Clean and easy.

  • Anonymous
    July 13, 2008
    The comment has been removed

  • Anonymous
    July 13, 2008
    I like Phil's solution but I see one problem and one thing I dislike.  The random number generator wasn't seeded.  I like Jos's solution to Phil's bit switching if it is zero. Lemme see if I can't over engineer a cool solution.  This solution also scales to more than 4 digits and will provide a random fixed digit solution. There is one assumption, 0 can be the last digit.  It is a legal 4 digit number, if it can't, I'd add in a if that says something like  if( i == amountOfDigits -1 && unUsedNumbers[0] == 0) unUsedNumbers.RemoveAt(0); as the start of the For loop. // Ticks is a long, doing a mod and casting to int if over int.max private readonly Random random = new Random((int)(DateTime.Now.Ticks % int.MaxValue)); private int RandomNonRepeatingNumber() { return RandomNonRepeatingNumber(4); } private int RandomNonRepeatingNumber(int amountOfDigits) { if (amountOfDigits < 0 || amountOfDigits > 10) throw new Exception("can only form a number between 0 and 10 digits long"); Collection<int> unUsedNumbers = new Collection<int> {0,1,2,3,4,5,6,7,8,9}; int returnVal = 0; int currentBase = 0; for (int i = 0; i < amountOfDigits; i++) { int index = random.Next(0, unUsedNumbers.Count - 1); // incrementing currentBaseAfter use. returnVal += (int)Math.Pow(10, currentBase++) * unUsedNumbers[index]; // popping off collection unUsedNumbers.RemoveAt(index); } return returnVal; }

  • Anonymous
    July 15, 2008
    I like Clint's solution, it seems to be the most efficient. Collections.RemoveAt is insanely efficient for dynamic lists. It would be cooler to Fisher-Yates shuffle the array before picking numbers from it for added randomness - http://www.pherg.net/2007/11/29/unbiased-shuffle-algorithm/ and I would probably use the RNGCryptoServiceProvider instead of the more generic Random for added overkill...

  • Anonymous
    July 15, 2008
    The comment has been removed

  • Anonymous
    July 16, 2008
    >The random number generator wasn't seeded. I forgot to mention that PRNGs are typically seeded with the date if no seed is given (check the documentation). So, the only real way one might want to improve it is an optional parameter for the PRNG if determinism is required. For example: At the very beginning the application creates a seed, which is stored somewhere. This seed is then used to initialize the PRNG. And this PRNG is then passed to any method which needs some randomness. This allows you to reproduce 100% identical results. That's for example interesting for games which need some randomness. You can for example send a single seed to multiple machines, which in turn create identical procedural maps. A nice real world example for this is Tribal Trouble: http://tribaltrouble.com/ Check the paper if you're interested in the details: http://www.oddlabs.com/download/terrain_generation.pdf

  • Anonymous
    July 29, 2008
    I don't think I'm doing much different than what has already been posted.  However, I thought it would be nice to share a C# (3.5) example. As stated above, this is not likely to be a performance concern.  So, I opted to keep it simple (at least in my mind). The first parameter for Random.Next is inclusive, while the second is exclusive. I've purposefully left out any error handling. Cheers, Will private static Random random = new Random(); private static long GetRandomNumberWithNonRepeatingDigits( int targetLength ) {    List<int> availableDigits = Enumerable.Range( 0, 10 ).ToList();    //first digit    long result = ExtractRandomDigit( availableDigits, 1 );    //remaining digits    for( int i = 0; i < targetLength - 1; i++ )    {        result *= 10;        result += ExtractRandomDigit( availableDigits, 0 );    }    return result; } private static int ExtractRandomDigit( List<int> availableDigits, int minIndex ) {    int digitIndex = random.Next( minIndex, availableDigits.Count );    int digit = availableDigits[digitIndex];    availableDigits.RemoveAt( digitIndex );    return digit; }