The Four Digit Problem

Computer Science Teacher
Computer Science Teacher - Thoughts and Information from Alfred Thompson

The Four Digit Problem

  • Comments 8

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.
  • // 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];

    }

    }

  • I like that one Phil. Clean and easy.

  • Phil's solution is pretty good, but there is one small issue: the distribution is slightly skewed. Getting a '0' as second digit is more likely than it should be.

    The naive fix would be swapping a first-pos-zero with a randomly chosen item, but that still makes a zero slightly more likely for the last 3 digits.

    A better fix would be adding the digits in reverse order (or just with 0 at the last position) and using the 9-1 range on the first run... and increasing it by one for the successive runs.

    The result looks like this (Java):

    public static int foo(){

    Random random=new Random();

    int[]digits=new int[]{9,8,7,6,5,4,3,2,1,0};

    for(int i=0;i<4;i++){

    int picked=random.nextInt((i==0?9:10)-i)+i;

    if(picked==i)continue;

    int digit=digits[picked];

    digits[picked]=digits[i];

    digits[i]=digit;

    }

    return digits[0]*1000 + digits[1]*100 + digits[2]*10 + digits[3];

    }

  • 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;

    }

  • 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...

  • >it seems to be the most efficient

    It isn't. Putting stuff into some collection and removing it is slower than accessing some stuff in some array. For example random access with linked lists is slow, but insert/remove is quick. With array backed collections it's the other way around, because insert/remove means lots of stuff need to be moved around (especially if it's the first item).

    Math.pow is also somewhat slow.

    Phil's and my approach are basically using the Fisher-Yates algorithm. The only difference is the special handling of the first item (no zero allowed) and limiting it to the first 4 items.

    A better collection based approach could look like this (Java again):

    public static int foo(){

    ArrayList<Integer>d=new ArrayList<Integer>();

    Random rand=new Random();

    for(int i=1;i<10;i++)

    d.add(i);

    int s=d.remove(rand.nextInt(d.size()))*1000;

    d.add(0);

    int m=100;

    for(int i=0;i<4;i++){

    s+=d.remove(rand.nextInt(d.size()))*m;

    m/=10;

    }

    return s;

    }

    First 1-9 are added, then a randomly chosen element is removed, it's multiplied with 1000 and it's used to initialize the sum variable... then 0 is added to the list, a multiplier is initialized with 100, then 3 randomly chosen items are removed... and each is multiplied with the multiplier and added to the sum, and that multiplier is reduced to 10% of its previous value after each cycle.

    This algorithm is far easier to understand than my previous one, but it's quite a bit slower.

    Well, it's pretty unlikely that something like that turns out to be the bottleneck of some application. Coming up with a better solution than this one is most likely not required. At least its behavior is far more predictable than the VBS(?) version at the top, which could in theory take forever to finish.

    Also note that randomizing twice doesn't make it any more random. It's either random with good distribution or with a bad one.

    Without that "no leading 0" requirement using a ShuffleBag would be a very elegant solution, because the shuffling is limited to the number of drawn items. See:

    http://kaioa.com/node/53

    (Unfortunately the add() behavior isn't compatible with that "no leading 0" requirement.)

  • >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

  • 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;

    }

Page 1 of 1 (8 items)