How to generate 32-bit random number without duplicate each time?

Article
2017-12-26

Question

_{Tuesday, December 26, 2017 6:11 AM}

Dear All,

In my application, a 32-bit random number is assigned to each a certain instance which is created.

The random number cannot be duplicate, each instance has a unique random number among these instances.

My solution is to use a List instance randomList to store random number generated by Random instance rn, see function RandomNumInit().

Instance got the random number by calling GetRandomNum().

The reason is to save check time when system has a lot of instances, that keep the same time to read random value from List randomList. The drawback is too many memoy is occupied.

Is there any better way to get different 32-bit random number without duplicate?

Thanks and regards,

E-John

        public void RandomNumInit()
        {
            Random rn = new Random();
            int i = 0, r1 = 0;
            UInt32 tmp;

            randomList.Clear();

            for (i = 0; i < TotalRandomNumerCount; i++)
            {
                randomList.Add((UInt32)i);
            }

            for (i = 0; i < TotalRandomNumerCount; i++)
            {
                r1 = rn.Next(i, TotalRandomNumerCount);
                if (r1 != i)
                {
                    tmp = randomList[r1];
                    randomList[r1] = randomList[i];
                    randomList[i] = tmp;
                }
            }
        }        public UInt32 GetRandomNum()
        {
            int i = 0;
            UInt32 random_num_taken = 0x00000000;

            for (i = 0; i < TotalRandomNumerCount; i++)
            {
                if (randomList[i] != 0x00000000)
                {
                    random_num_taken = randomList[i];
                    randomList[i] = 0x00000000;      // fill 0x00000000 means this value is taken
                    break;
                }
            }

            return random_num_taken;
        }

All replies (12)

_{Tuesday, December 26, 2017 11:32 PM ✅Answered}

Check if the next GetNextNumber gives random-enough 32-bit unique numbers:

static class MyClass
{
    static readonly List<UInt16> h;
    static List<UInt16> a;
    static int k;
    static readonly Random r;

    static MyClass()
    {
        r = new Random();
        h = new List<UInt16>();
        a = new List<UInt16>();
        for( int i = 0; i <= UInt16.MaxValue; ++i )
        {
            h.Add( (UInt16)i );
        }
    }


    public static UInt32 GetNextNumber()
    {
        if( a.Count == 0 )
        {
            if( h.Count == 0 ) throw new Exception( "No more numbers" );
            var ih = r.Next( h.Count );
            k = h[ih];
            h.RemoveAt( ih );

            a = new List<UInt16>();
            for( int i = 0; i <= UInt16.MaxValue; ++i )
            {
                a.Add( (UInt16)i );
            }
        }

        var ia = r.Next( a.Count );
        var v = a[ia];
        a.RemoveAt( ia );

        var m = ( v + k * ( UInt16.MaxValue + 1 ) );
        var b = BitConverter.GetBytes( m );

        return BitConverter.ToUInt32( b.Reverse().ToArray(), 0 );
    }
}

_{Tuesday, December 26, 2017 6:33 AM}

Are the numbers in a sequential range, as in every integer between one and a million? That might not affect the answer or it might be a critical piece of information.

Or are there non-sequential values? In a deck of playing cards there are four suits and 13 cards of each suit. So shuffling a deck of cards can be done by randomly selecting one of the 52 cards and for that a good solution is to have a list of cards to be selected and to remove each one when selected. I think that is similar to what you are describing, except you have many more possible selections, right?

Would a Sparse matrix - Wikipedia help?

Sam Hobbs
SimpleSamples.Info

_{Tuesday, December 26, 2017 8:32 AM}

In my application, a 32-bit random number is assigned to each a certain instance which is created.

The random number cannot be duplicate, each instance has a unique random number among these instances.

Most would just use a GUID, which can be generated using C# code.

https://betterexplained.com/articles/the-quick-guide-to-guids/

_{Tuesday, December 26, 2017 10:36 AM}

Hello E-John,

For the reference type, the each instance will generate a unique "random" number named hash code. The "random" means the CLR will produce a hash number that distinguish all reference type instances through complex algorithms. you could get the hash value by using GetHashCode method in C#. The code should be like as below.

class T1 {
            public int id;
        }
        static void Main(string[] args)
        {
            T1 t1 = new T1 { id=12};
            T1 t2 = new T1 { id=12};
            T1 t3 = new T1 { id =12};

            Console.WriteLine(t1.GetHashCode());
            Console.WriteLine(t2.GetHashCode());
            Console.WriteLine(t3.GetHashCode());           
        }

Note: Do not persist storage the hash value because the hash number can be changed when CLR update.

Best regards,

Neil Hu

MSDN Community Support
Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact [email protected].

_{Tuesday, December 26, 2017 10:43 AM}

Hi E-John,

Please look into the below thread as it has the similar issue related to your's. Hope the solution might work

C# Unique Random Integer Create

Thanks,
Sabah Shariq

[If a post helps to resolve your issue, please click the "Mark as Answer" of that post or click "Vote as helpful" button of that post. By marking a post as Answered or Helpful, you help others find the answer faster. ]

_{Tuesday, December 26, 2017 10:33 PM}

For the reference type, the each instance will generate a unique "random" number named hash code. The "random" means the CLR will produce a hash number that distinguish all reference type instances through complex algorithms.

Where does the documentation say that the default implementaion generates a unique value? The Object.GetHashCode Method says:

do not use the default implementation of this method as a unique object identifier for hashing purposes

And many StackOverflow posts say that the default hashcodes are not guaranteed to be unique.

Sam Hobbs
SimpleSamples.Info

_{Wednesday, December 27, 2017 12:59 AM}

Hi Sam,

Are the numbers in a sequential range, as in every integer between one and a million?

> They are non-sequential value, each time the node in treeview is created, the random number is assigned to the new created node.

I think that is similar to what you are describing, except you have many more possible selections, right?

> Yes, like playing cards, but in my application, we need to shuffle (0xffffffff + 1) number. Each time the node is created, it takes a number from the List as its ID.

Thanks and regards,

E-John

_{Wednesday, December 27, 2017 1:24 AM}

GUIDs are globally unique, but substrings of GUIDs aren’t

Btw, looking at the parts of GUID, since the nodeid part will occupy 48-bit, discard 32-bit from it will make it 16-bit remaining which won't change though out the course, so IMO it don't fit the definition of "random".

_{Wednesday, December 27, 2017 1:34 AM}

I am sorry but I still don't understand what the requirements are.

Sam Hobbs
SimpleSamples.Info

_{Wednesday, December 27, 2017 1:57 AM}

Hi Neil,

GetHashCode() return same value when application restart.
It is needed to get random number when application restart in my application.

1st start application, the results are
46104728
12289376
43495525

2nd start application, the results are
46104728
12289376
43495525
they are the same.

Thanks and regards,
E-John

_{Wednesday, December 27, 2017 3:07 AM}

Why are you even messing around with the 32bit integer number nonsenses collision, if all you are trying to do is get unique instance identifiers?

https://blog.stephencleary.com/2010/11/few-words-on-guids.html

Assuming a perfect source of entropy on each device generating random GUIDs, there is a 50% chance of collision after 2.7e18 random GUIDs have been generated. That’s more than 2.7 million million million. That’s a lot.

Even if you reduce the chance of collision to 1%, it would still take about 3.27e17 random GUIDs for just a 1% chance of collision. That’s more than 326 million billion. That’s a lot.

<end>

_{Wednesday, December 27, 2017 3:14 AM}

Hi Viorel,

Thanks for your algorithm, this may meet my requirement. Thanks for your great helps.

There is only one question,

Unique 32-bit random is generated by concatenating k and v to form a 32-bit value via this algorithm

Unique 32-bit random value exists after doing BitConverter? Will there be duplicate case?

If my old method is used, it takes 2^32 = 4294967296 number of Uint32

In your algorithm, it takes 2 * (2^16) = 131072 number of Uint16

The algorithm is summary as follows,

1. There are two UInt16 array to store different values, range from 0 to 0xffff.

h[] and a[], h[] is the low 16-bit part and a[] is the high 16-bit part before manipulation.

2. If a[] is empty, get a value k from h[] by random, and this value is removed from h[].

And create array a[], count number of a[] is equal to 0xffff.

          var ih = r.Next( h.Count );
            k = h[ih];
            h.RemoveAt( ih );

3. Use random class r.Next(a.Count) to get a value v from a[], and this one is used this time, remove it from array a[]

      var ia = r.Next( a.Count );
        var v = a[ia];
        a.RemoveAt( ia );

4. Concatenate k and v to form a 32-bit value m by following formula, and do a BitConverter of m

      var m = ( v + k * ( UInt16.MaxValue + 1 ) );
        var b = BitConverter.GetBytes( m );

5. Repeat step 1 to step 4, will get 2^32 UInt32 data

Thanks and regards,

E-John

Share via

How to generate 32-bit random number without duplicate each time?

Question

All replies (12)

Additional resources