0

The Requirement:

  1. I need to generate 4-digit non-duplicate number - even my application get closed, generation of number must not have to be duplicate.

  2. I don't want to store all previous number in any storage.

Is there any algorithm which has highest possibility to produce most of unique number in a day ?

Thank you

Hearen
  • 7,420
  • 4
  • 53
  • 63
amoljdv06
  • 2,646
  • 1
  • 13
  • 18
  • 1
    Use GUID, see URL for duplicate https://stackoverflow.com/questions/39771/is-a-guid-unique-100-of-the-time – Tony Dong Jul 18 '18 at 18:06
  • For a four digit non-duplicate number use a [Format Preserving Encryption](https://en.wikipedia.org/wiki/Format-preserving_encryption) and encrypt the numbers from 0000 to 9999. Any reasonable algorithm will produce all those numbers in a fraction of a second. – rossum Jul 18 '18 at 18:08
  • You could store a checksum of the previously generated numbers to reduce risk of collision, but in this way you cannot ensure that there won't be repetitions. – ppablo Jul 18 '18 at 18:09
  • @TonyDong GUID is likely to be *unique*. It's not guaranteed to be *random*. How do you propose to select a 4-digit, unique, number from the digits of the GUID? – Jim Mischel Jul 18 '18 at 18:11
  • If you won't allow storage of already generated numbers, then generating a new set of non-duplicate 4-digits random numbers on application start is a good as any other algorithm. Adding encryption logic or anything else will just change the randomization algorithm, it won't increase the probability of not clashing with what was already generated in earlier run. – Andreas Jul 18 '18 at 18:13
  • Need most of unique number in a day as I want to generate Job ID.,once job get terminate ,then I can use terminated job's Id again. One job need at least 14-16 hr to successfully terminate. – amoljdv06 Jul 18 '18 at 18:20
  • @JimMischel [Version 4 UUID](https://en.wikipedia.org/wiki/Universally_unique_identifier#Version_4_(random)) has 122 of its 128 bits randomly generated. See [`java.util.UUID.randomUUID()`](https://docs.oracle.com/javase/10/docs/api/java/util/UUID.html#randomUUID()). – Basil Bourque Jul 18 '18 at 19:01
  • @BasilBourque Yes, I realize that. Now, select 10,000 numbers in the range 0 through 9999, without repeating a number. Can you do it without generating a duplicate? – Jim Mischel Jul 18 '18 at 20:12
  • @JimMischel I said nothing about the problem of 10,000 numbers. I was simply correcting your statement about UUIDs not being random. – Basil Bourque Jul 19 '18 at 02:18

3 Answers3

3

Don't generate a random number. Instead, generate a sequential number from 0000 to 9999, and then obfuscate it using the technique described in https://stackoverflow.com/a/34420445/56778.

That way, the only thing you have to save is the next sequential number.

That example uses a multiplicative inverse to map the numbers from 0 to 100 to other numbers within the same range. Every number from 0 to 100 will be mapped to a unique number between 0 and 100. It's quick and easy, and you can change the mapping by changing the constants.

More information at http://blog.mischel.com/2017/06/20/how-to-generate-random-looking-keys/

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
2

Ten thousand is too few

Generating more than a few random numbers within a range of 0 to 9,999 is not likely to go well. Depending on how many such numbers you need, you are quite likely to run into duplicates. That seems rather obvious.

Cryptographically-strong random number generator

As for generating the most randomness, you need a cryptographically-strong random number generator that produces non-deterministic output.

java.security.SecureRandom

Java provides such a beast in the java.security.SecureRandom class. Study the class documentation for options.

SecureRandom secureRandom = new SecureRandom();

Notice that a SecureRandom is a java.util.Random. On that interface you will find convenient methods such as nextInt​(int bound). You get a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive).

int r = secureRandom.nextInt( 10_000 ) ;

Let's try it.

SecureRandom secureRandom = new SecureRandom();
for( int i = 1 ; i <= 20 ; i ++ ) 
{
    System.out.println( secureRandom.nextInt( 10_000 ) ) ;
}

7299

3581

7106

1195

8713

9517

6954

5558

6136

1623

7006

2910

5855

6273

1691

588

5629

7347

7123

6973

If you need more than few such numbers, or they absolutely must be distinct (no duplicates), than you must change your constraints.

  • For a small range like 10,000, keep a collection of generated numbers, checking each newly generated number to see if it has been used already.
  • Dramatically expand your limit far beyond 10,000.

UUID

If you need a universally unique identifier, use, well, a Universally Unique Identifier (UUID). Java represents a UUID value with the java.util.UUID class.

UUIDs were designed for systems to be able to independently generate a virtually unique identifier without coordinating with a central authority. They are 128-bit values. That is quadruple the 32-bits of a int integer primitive in Java. UUIDs are often displayed to humans as a canonically-formatted 36-character hexadecimal string grouped with hyphens. Do not confuse this textual representation for a UUID value itself; a UUID is a 128-bit value, not text.

The Version 1 type of UUIDs are ideal, as they represent a point in both space and time by combining a date-time, a MAC address, and a small arbitrary number. This makes it virtually impossible to have duplicates. By “virtually impossible”, I mean literally astronomically-large numbers. Java does not bundle a Version 1 generator because of security/privacy concerns. You can add a library, make a web services call, or ask your database such as Postgres to generate one for you.

Or, for most cases where we need a relatively small number of instances, use the Version 4 UUID where 122 of the 128 bits are randomly generated. Java bundles a Version 4 generator. Simply call UUID.randomUUID.

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
1

I agree with Basil Bourque and others about whether what you propose is the "right" approach. However, if you really want to do what you are proposing, then one way to achieve your goal (generate as many numbers as possible within range in pseudorandom order without having to store all previous values generated):

  • find a random number generator that has a period roughly within the range that you require;
  • to generate the next ID, take the next number generated, discarding ones that are not within range.

So for four digit numbers, one option would be an XORShift generator configured to generate 16 bit numbers (i.e. in the range 1-16383, near enough to 1-999):

    private int seed = 1;

    public int nextJobID() {
      do {
        seed = (seed ^ (seed << 5)) & 0x3fff;
        seed = (seed ^ (seed >>> 3)) & 0x3fff;
        seed = (seed ^ (seed << 7)) & 0x3fff;
      } while (seed >= 10000);

      return seed;
    }

To generate a new sequence each "day", set 'seed' to any number between 1 and 16383. [It'll be the same sequence, just starting at a different point. You could vary the sequence a little e.g. by taking every nth job ID where n is a small number, reversing the pattern of shifts (do >>>, <<, >>> instead of <<, >>>, <<) or finding some other combination of shifts (not 5/3/7) that produce a complete period.]

This technique is guaranteed to produce all numbers in range in "random" order. It doesn't offer any other guarantee, e.g. that it will be the most efficient or produce the "highest quality" of randomness achievable. It's probably good enough -- if not as good as you can get -- given the requirements you set out.

Neil Coffey
  • 21,615
  • 7
  • 62
  • 83