3
\$\begingroup\$

How to generate Random numbers without repeating any numbers in the given target like(1-5000) there should be no reparation and I should be able to get 5000 randomized numbers. I should be able to run the randomized as many times as the user wants,How to do with C#

For Sample Target is (1-10) No of times to run =2

First run: 5,4,6,8,3,1,2,0,7,10

second run 6,3,5,8,4,2,0,1,10,7

Like this I should be able to get the results as many times as I run..

\$\endgroup\$
4
  • 2
    \$\begingroup\$ The only way to do this, would be to create a list off all the numbers and randomly move numbers around n number of times. \$\endgroup\$ Feb 23, 2016 at 5:12
  • \$\begingroup\$ What have you tired so far? \$\endgroup\$
    – wondra
    Feb 23, 2016 at 7:19
  • \$\begingroup\$ @Jordan Is that a guess? Or do you know that. If that's true, then why is that the case? \$\endgroup\$
    – Evorlor
    Feb 23, 2016 at 15:24
  • 1
    \$\begingroup\$ This sounds like what you want is a shuffle bag \$\endgroup\$
    – Anthony
    Feb 24, 2016 at 13:17

5 Answers 5

11
\$\begingroup\$

As others have pointed out, what you're looking for is effectively a shuffled deck of cards. Every card (in this case, a unique number) is present exactly once, in a randomized order. By drawing cards from the deck one at a time, you create a psuedorandom number string with no repeats.

(Obviously, once you've exhausted the deck, you'll need to either reuse it or reshuffle it to generate the next number)

A fast way to do this is with a Fisher-Yates shuffle, also commonly called a Knuth Shuffle:

// Prepare a deck of sequential numbers from min to max:

int count = max - min + 1
int[] deck = new int[count];

for(int i = 0; i < count; i++)
{
   deck[i] = min + i;
}


// Shuffle it:

for(int i = count - 1; i > 1; i--)
{
    // Pick an entry no later in the deck, or i itself.
    int j = Random.Range(0, i + 1);

    // Swap the order of the two entries.
    int swap = deck[i];
    deck[i] = deck[j];
    deck[j] = swap;
}

// Now deck[] contains all numbers from min to max
// in a random order with no duplicates.

This can also be combined into one pass:

int count = max - min + 1;
int[] deck = new int[count];

for(int i = 0; i < count; i++)
{
    int j = Random.Range(0, i + 1);

    deck[i] = deck[j];
    deck[j] = min + i;
}

One neat trick is that you don't even have to shuffle all at once for this. You can randomize as you go, at a constant cost per card drawn:

[System.Serializable]
public class Deck<T> {
    [SerializeField]
    T[] deck; 

    // Tracks a partition between the deck & discard pile.
    // All entries at i < remaining are in the undrawn deck,
    // remaining <= i < deck.Length are in the discard pile.
    int remaining = 0;

    public T Draw() {
        // If we ran out of cards, shuffle the discards to make a new deck.
        if(remaining == 0)
            remaining = deck.Length;

        // Pick a card at random from the remaining deck.
        int chosenIndex = Random.Range(0, remaining);
        T chosenItem = deck[chosenIndex];

        // Remove the card from the remaining deck and place it at the
        // top of the growing discard pile.
        remaining--;
        deck[chosenIndex] = deck[remaining];
        deck[remaining] = chosenItem;

        return chosenItem;
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ The best answer I found, very simple with no memory allocations for shuffling the list, Thanks \$\endgroup\$
    – Ninja Dev
    Jul 1, 2019 at 13:22
5
\$\begingroup\$

You can achieve this by creating a list of numbers, populate it with your range, pick it and remove it. Simple cycle :)

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class AnyClass : MonoBehaviour
{
    // Your original list. Can be use to reset your list
    List<int> _originalList = new List<int> ();
    // List which will be used
    List<int> _numbersToGenerate = new List<int> ();

    void Start()
    {
        // For 0 - 9

        // Initializing original range. You can reset list by this
        for (int i = 0; i < 10; i++)
            _originalList.Add (i);

        // Assigning list to _numbersToGenerate list
        _numbersToGenerate = _originalList;

        // Getting unique numbers
        for (int i = 0; i < 10; i++) 
        {
            int index = Random.Range (0, _numbersToGenerate.Count);
            int nextNumber = _numbersToGenerate [index];

            print ("Next Number: " + nextNumber.ToString ());

            // On DMGregory's advise for optimization. Replacing selected index with the last index
            SwapElements (ref _numbersToGenerate, index, _numbersToGenerate.Count - 1);

            _numbersToGenerate.RemoveAt (_numbersToGenerate.Count - 1);
        }

        // Reset it again
        _numbersToGenerate = _originalList;
    }

    void SwapElements (ref List<int> list, int index1, int index2)
    {
        int tmp = list [index1];
        list [index1] = list [index2];
        list [index2] = tmp;
    }
}
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Removing from random indices in a list is unnecessarily slow for this use case, particularly if the removed item is close to the beginning of the list, because all the other later need to be copied down to fill the gap. You can improve this dramatically by swapping with the last element in the list and then removing from the end. \$\endgroup\$
    – DMGregory
    Feb 23, 2016 at 12:59
  • \$\begingroup\$ @DMGregory done bro :) And thanks for pointing it out :) \$\endgroup\$ Feb 23, 2016 at 13:20
1
\$\begingroup\$

The usual approach to this scenario is to build a collection and then shuffle the contents, much like a deck of playing cards. The Fisher-Yates shuffle is a simple and effective algorithm that suits our purpose well.

Here is a minimal implementation:

using System.Collections.Generic;

public class Deck<T>
{
    private int index;
    private List<T> values;

    public bool isEmpty
    {
        get { return index == values.Count; }
    }

    public Deck(IEnumerable<T> seedValues)
    {
        values = new List<T>(seedValues);
        Reshuffle();
    }

    public T Draw()
    {
        T next = values[index];
        index++;
        return next;
    }

    public void Reshuffle()
    {
        index = 0;
        Shuffle();
    }

    private void Shuffle()
    {
        // Durstenfeld's version of Fisher–Yates shuffle
        System.Random random = new System.Random();
        for (int i = values.Count - 1; i >= 1; i--)
        {
            int j = random.Next(0, i);
            T temp = values[j];
            values[j] = values[i];
            values[i] = temp;
        }
    }
}

That can be used like so:

int count = 5;
var numberPool = new List<int>(count);
for (int i = 0; i < count; i++)
{
    numberPool.Add(i);
}

Deck<int> deck = new Deck<int>(numberPool);

Debug.Log("Deal 1");
while (!deck.isEmpty)
{
    Debug.Log(deck.Draw());
}

Debug.Log("Deal 2");
deck.Reshuffle();
while (!deck.isEmpty)
{
    Debug.Log(deck.Draw());
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Whoops, looks like we were both writing a Fisher-Yates answer at the same time! I'll leave mine up for the moment since we use slightly different flavours. \$\endgroup\$
    – DMGregory
    Feb 23, 2016 at 13:20
  • \$\begingroup\$ @DMGregory No problems, they are different answers. \$\endgroup\$ Feb 24, 2016 at 0:17
0
\$\begingroup\$

An alternative to a List, could be a Hashset, which provides a much more efficient solution.

// Container to store our random values
HashSet<int> RandomNumbers = new HashSet<int>();

// Function to generate a range of unique random values
private void CreateRandomNumbers(int low, int high, int amount)
{
    int count = 0;

    while (count != amount)
    {
        int value = Random.Range (low, high);
        if (!RandomNumbers.Contains (value)) {
            RandomNumbers.Add (value);
            count++
        }
    }
}

// Output our Random Numbers
private void Print()
{
    foreach (int value in RandomNumbers)
        Debug.Log (value.ToString ());
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ As-written, this code will fail. value is generated once and never modified, so this generates a single random number, tries to add it to the set amount times (failing on every attempt after the first) and then leaves the set with only one new number in it. Even if this bug is fixed, the trial-and-error approach to adding a number gets slower the more of the numbers in the range are already in the set (in OP's example of random numbers from 1 to 5000, this approach would be expected to take ~5000 attempts to generate the last number) \$\endgroup\$
    – DMGregory
    Feb 23, 2016 at 12:55
  • \$\begingroup\$ Yep, brute force! \$\endgroup\$
    – jgallant
    Feb 23, 2016 at 19:04
0
\$\begingroup\$

This creates an unsorted list of numbers in a range, randomized them, and then iterates through them.

int count = 5000;
int[] randomNumbers = new int[count];
for(int i = 1; i <= count; i++)
{
    randomNumbers[i] = i;
}
randomNumbers = randomNumbers.OrderBy(a => (new Random()).Next());
foreach(int randomNumber in randomNumbers)
{
     //use randomNumber
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's a bit concerning that you're constructing a new instance of the Random class for every item in your source array, using it once, then discarding it. Even if this doesn't lead to a noticeable performance drain, it may impact the quality of randomness you get. According to the docs, each instance is assigned a time-dependent seed if you don't provide one, so if your code runs fast enough you might get runs of identical pseudorandom numbers doing it this way. \$\endgroup\$
    – DMGregory
    Feb 23, 2016 at 19:38
  • \$\begingroup\$ @DMGregory Yeah, good call. \$\endgroup\$
    – Evorlor
    Feb 23, 2016 at 19:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .