Generate Random Unique Code

问题:

I need to generate a nine digit numeric code (random preferably) which is unique for a given day (same number cannot be generated again on the same day). I was thinking of using HHMMSSmmm (hours, minutes, seconds and milliseconds) to generate the unique code but is not really random. This code generation method can be accessed by multiple methods at the same time so I will have to put a lock on the method. But will this ensure that the number is unique as it is possible that number generation may take less than a millisecond and two threads get the same number?

Is there a better way to generate a random unique numeric code which is unique for a given day? The number of digits can be from 6 to 9 digits.

Edit: The number of random numbers to be generated depends on the number of transactions. Initially the number could be lower but over a period of time it can become very high (multiple transactions per second). Hence, I would not like to compare the number against a used list as this could have performance issues.

Randomness is needed as this number will be entered by the user on the phone. This number is the only way to link the online transaction with the phone transaction so I don't want user to enter a different number by mistake.

The random number generation needs to take place in a ASP.NET MVC application.

回答1:

If you start from a random number with 6 digits, then keep adding random, but small enough numbers, you may be abled to do that. You can use the filesystem as the locking storage if you want... but I think you should use a DB for production!

Here is the sample of what I am talking about:

This sample is a console application, that uses a file to control concurrency, and to store the last used number and date it was generated.

If you run it multiple times you will see what happens. Both will have their own unique numbers.

It will NOT store all generated numbers, like you required!

This sample can generate for about 999000 random numbers per day, in the range of 6 and 9 digits inclusive. That is about 11 numbers per second.

using System;
using System.IO;
namespace _5893408
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rand = new Random();
            var futureTime = DateTime.Now.AddSeconds(60);
            while (DateTime.Now < futureTime)
                Console.WriteLine(GetNextNumber(rand));
        }

        public static int GetNextNumber(Random rand)
        {
            var now = DateTime.Now;
            string filePath = @"C:\num.txt";
            FileStream fileStream = null;
            while (fileStream == null)
            {
                try { fileStream = File.Open(filePath, FileMode.OpenOrCreate, FileAccess.ReadWrite, FileShare.None); }
                catch { }
            }
            using (fileStream)
            {
                DateTime date;
                int prevNum;
                if (fileStream.Length == 0)
                {
                    date = now;
                    prevNum = rand.Next(100000, 999999);
                }
                else
                {
                    var reader = new StreamReader(fileStream);
                    {
                        date = DateTime.Parse(reader.ReadLine());
                        prevNum = int.Parse(reader.ReadLine());
                    }
                    if (date.DayOfYear != now.DayOfYear)
                        prevNum = rand.Next(100000, 999999);
                }
                int nextNum = prevNum + rand.Next(10, 1000);
                fileStream.Seek(0, SeekOrigin.Begin);
                using (var writer = new StreamWriter(fileStream))
                {
                    writer.WriteLine(now);
                    writer.WriteLine(nextNum);
                }
                return nextNum;
            }
        }
    }
}

I think that this fulfills your requirements... am I wrong?

If I am, just tell and I'll try to help more.

回答2:

Does it only have to be unique within the process?

Any reason not to just keep a counter which you increment atomically each time, and then reset it if the date rolls over?

回答3:

I would

1. Generate a set of unique random numbers at the beginning of each day, or rather, before each day in adequate time

2. Sequentially take a number from the stack every time one is needed

回答4:

If all the calls are within the same JVM, I think all you'd need is to create a static to hold the last number assigned, write a single function to increment the number and return the new value, and then synchronize on it. Like:

public class NumMaker
{
  static long num=0;
  public static synchronized next()
  {
    return ++num;
  }
}

If there are multiple JVMs, the easiest thing to do would be to store the number on a database and use database locking to keep the numbers unique.

Update

I see you've added a requirement that the numbers be random. If you want the numbers to be random AND unique, I don't see any alternative to keeping a list of all previously assigned numbers. You could keep them in some sort of hash table so you don't have to search the entire list each time. If you're assigning a lot of these the size of the hash table may begin to be a problem, even if you don't have to sequentially search it.

Depending on what you're trying to accomplish, you could come up with a scheme that assigns numbers non-sequentially but in a rigid sequence, so for some purposes they would appear random. For example, you could increment by a number that is very large with respect to the maximum and relatively prime with the maximum, and then every time the next increment would go over, subtract the maximum. Like just to scale it down, suppose you were assigning 2 digit numbers instead of 9 digit. Increment by 37. Then you'd assign 37, 74, 111 wraps to 11, 48, 85, 122 wraps to 22, etc.

回答5:

EDIT: This answer doesn't make sense when I realised the requirement to have multiple unique codes per day, but that they can repeat the next day. If you were looking for a single unique code per day (for whatever reason), then this answer is useful :)

so if the code is just required to be unique per day, then just use the date as the code...

maybe YYYYmmdd, which would give you (for today's date) 20110505, and tomorrow would be 20110506.

回答6:

You CAN'T ensure than random numbers will not repeat. (because, they're random)

Without a comparison with already generated numbers, you can have:

• random number OR
• unique number.

You need unique number with some random-look. If the milliseconds from the beginning of the day has not enough random look, try combine it with another unique number.

For example:

• combine number of milliseconds, and
• atomic counter (what is increment by one every time you generate a number)

for example when you sum them, you can generate: 999999999-86400000 = 913599999 unique numbers per one day.

While they will be not random, they will be unique - and predictable only at 00:00.

Here are variations for this, for example not resetting the counter at 00:00.

回答7:

How about a modified version of Shuffle Bag. Here's how it would work -

1. before your Start of day, you put N distinct numbers satisfying your criterion in a shuffle bag
2. during the course of day, you request a number from shuffle bag.
3. Shuffle bag gives you a random number from bag and discard it - i.e. will not return the same number again.
4. at the end of the day it would clear the bag, ready for next day.

Benefits

• Ensures number is not reused, without checking with existing list
• Numbers would be random, without any sequence
• Apply simple sanity rules to initialize Shuffle Bag, for e.g. no common / repeating sequences allowed (1111111 or 123456789)
• Simple to initialize shuffle bag - use random sequential numbers. i.e. start from six digit number keep on adding a small random number to initialize bag.
• Easy to modify the size of bag based upon historical usage.
• Very simple thread safe implementation in c#.

Original source is here - modified version might serve your purpose.

• Never-ending Shuffled Sequences - When Random is too Random

回答8:

Append a thread id to the end of the code to deal with concurrency.

回答9:

Use Guid.NewGuid() to get something like:

0f8fad5b-d9cb-469f-a165-70867728950e

Then, get rid of the '-'s, and convert the letters to their ASCII counterparts. (where a=97)

Then convert to a number.

回答10:

The suitable code generator depends on how much numbers should be generated in period. Consider following patterns:

HHMMSS+NNN- gives you space for 999 random numbers in a second.

HH+NNNNNNN - gives you space for 9999999 random numbers in a hour. Etc.

If number generation method call distribution in time is uniform, then any pattern is almost equal.

Anyway, considering random number lenght restriction there is always a limit for number of method calls before clashes will apper. E.g. if method is called > 1000 times per second.

回答11:

I continued your idea to use current time, I just added multi-thread synchronization, and storing used randoms to compare all next randoms with them to provide uniqueness.

private static DateTime DateInArray = DateTime.Today;
private static ICollection<string> UsedTodayRandoms = new List<string>();

[MethodImpl(MethodImplOptions.Synchronized)]
public static string RandomUniqueToday()
{
    if (! DateTime.Today.Equals(DateInArray) ) {
        UsedTodayRandoms.Clear();
        DateInArray = DateTime.Today;
    }

    string result = null;
    DateTime timeToGenerateUnique = DateTime.Now;
    do
    {
        result = timeToGenerateUnique.ToString("HHmmssfff");
        timeToGenerateUnique = timeToGenerateUnique.AddMilliseconds(-1);
    } while (UsedTodayRandoms.Contains(result));
    UsedTodayRandoms.Add(result);

    return result;
}

回答12:

public double GetRandomNumber() {object operation = new object(); lock(operation) { return new Random().NextDouble(); } } would do.

This does not depend on the day/time hence its even more random then your requirement. Now the fact that the number is less then 1 I'll leave to you as an exercise ...

Also, if you like to keep track of all number generated for a given day - keep a list of them and regenerate if duplicate is generated. But that I will not write for you as you are the programmer in your situation ...

回答13:

Depending on just how much randomness is required, a linear congruential generator with the appropriate parameters may be what you are looking for. For example, following the guidelines given on the Wikipedia entry about period length, a set of parameters that might work for you is: M=1000000000, a=21, c=3, then use any initial seed X₀ in [0..999999999], and compute X_n+1=(a*X_n+c)%M. This generates a sequence of X_n with period M, i.e., the sequence generates all numbers in [0..999999999] exactly once before starting to repeat.