List of numbers without repetition

Question

I need to print random numbers from 1 to 99 without repeating them. The following code gives me stack overflow.

int newNumb= Random.Range(1, 99);
if(acum.Count > 0)
{
    while (acum.Contains(newNumb))
    {
         newNumb= Random.Range(1, 99);
    }
}

There's no way you are getting a stack overflow from that code — Charleh, May 25 '18 at 00:12
@Charleh, your probably right, but you could still get a stackoverflow, your just assuming you know the type of acum — johnny 5, May 25 '18 at 00:13
[Fisher-Yates Shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) — juharr, May 25 '18 at 00:14
Your sample code doesn't show us how `acum` is declared, nor does it show why `acum.count` would be greater than zero. Assuming those two issues are resolved sensibly - your code gets a stack overflow because there's nothing to stop it running for ever. But @Jarod42 is correct, there are better ways to do this. — Frank Boyne, May 25 '18 at 00:20
This is the third time in 3 days I've seen this question :-D — ProgrammingLlama, May 25 '18 at 00:53
@johnny5 good point :) natural assumption would probably be `List` due to `.Count` and `.Contains`, but I based my comment on the question content and reputation of the OP which suggests a certain level of experience! — Charleh, May 25 '18 at 08:52
@Charleh fair point. I suspect the infinite loop is leading to the overflow but without a [mcve] I'm just guessing. We don't even know the type of the variable `Random`. We might assume it's an instance of `System.Random` but `Range` isn't a method on that class. Is `Range` an extension method on `System.Random` or is the variable `Random` some other type? Likewise we don't know what kind of container `acum` is nor do we see the code that adds new numbers to the container as they are generated. Who knows what else we might not be seeing? — Frank Boyne, May 25 '18 at 16:39

Joel Coehoorn · Answer 1 · 2018-05-25T00:41:51.817

4

The typical solution to this problem is to generate the sequential ordered range from 1 to 99 and then shuffle it:

static Random _random = new Random();

public static void Shuffle<T>(IList<T> items)
{
    for (int i = thisList.Count - 1; i > 0; i--)
    {
        int j = _random.Next(0, i);
        T tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }
}

var numbers = Enumerable.Range(1,99).ToList();
Shuffle(numbers);
foreach (var number in numbers)
{
     Console.WriteLine(number);
}

edited May 25 '18 at 00:41

answered May 25 '18 at 00:24

Joel Coehoorn

399,467
113
570
794

I think you could stop your `for` loop at `i>0`. When `i==0` you're going to call `random.Next(0,0)` which will return 0. Swapping `items[0]` with `items[0]` isn't wrong per se but you don't really need to do it. – Frank Boyne May 25 '18 at 00:38
@FrankBoyne fixed, thanks. – Joel Coehoorn May 25 '18 at 00:41
Wouldn't it be better to create a new list (instead of in-place replacing) to make this more functional (and you could even have a `yield return` there...)? – Camilo Terevinto May 25 '18 at 00:42
@CamiloTerevinto It can be. Depends on if you want to allocate new memory or not. – Joel Coehoorn May 25 '18 at 00:43
The upper bound on `Random.Next` is exclusive, so this may be an example of implementing Sattolo's algorithm when intending to implement Fisher-Yates. – Jonathon Chase May 25 '18 at 00:55

Jimi · Answer 2 · 2018-05-25T01:11:21.247

This will generate a list of random integers, each time a different one, and add it to a list.

The shuffle method is better, but since the range is so limited, also discarding duplicate numbers could work.

Over 100 runs, measuring the elapsed time with a StopWatch(), the list generation never went over 200 Ticks.
The shuffled list 5x times (1029~1395 Ticks) on my machine.

If the list count is set to a value > then the upper range limit (100+ in this case), the the generation procedure will of course never end. There are not enough distinct random values to fill the list.

Random random = new Random();

    List<int> acum = new List<int>();

    while (acum.Count < 99)
    {
        int Number = random.Next(1, 100);
        if (!acum.Contains(Number))
        {
            acum.Add(Number);
        }
    }

To verify the result, order the list and see that it's ordered from 1 to 99:

List<int> acum2 = acum.OrderBy(n => n).ToList();

score -1 · Answer 3 · answered May 25 '18 at 00:15

-1

the best way to do this would be to generate all the necessary numbers, and pull from that list until its empty, creating a new order; this is commonly known as shuffling.

your current code takes way too long, you need to track which numbers have been chosen, and only choose from the remaining ones. in psudocode

generate list
while list not empty
    choose number from list
    remove it from list
    add to new list

answered May 25 '18 at 00:15

esoterik

245
1
7

Perfect. It's true that what you say works but why does my code give me a stack overflow? ` for (int j = 1; j < 100; j++) { int newNumb= Random.Range(1, 9); if(acum.Count > 0) { while (acum.Contains(newNumb)) { nuevo = Random.Range(1, 9); } } acum.Add(newNumb); }` – Nogerad May 25 '18 at 00:19
@Nogerad no idea, you shouldn't get a stack overflow, but your fragment will run forever since there are only 8 numbers [1,9], and you are trying to force 100 unique numbers. – esoterik May 25 '18 at 00:22
what is solution? – Hossein Golshani May 25 '18 at 00:25

Mohammed Noureldin · Answer 4 · 2018-05-25T00:44:11.663

-1

Do this simply:

var list = new List<int>();
for (int i = 0; i < 99; i++)
{
    list.Add(i);
}

var resultList = list.OrderBy(i => Guid.NewGuid());

Or as suggested by @Camilo:

var resultList = Enumerable
    .Range(0, 99)
    .OrderBy(i => Guid.NewGuid());

UPDATE

This solution seems to be inefficient. Please use fischer-yates shuffle (shown in @Joel's answer).

edited May 25 '18 at 00:44

answered May 25 '18 at 00:17

Mohammed Noureldin

14,913
17
70
99

1

Or... `Enumerable.Range(0, 99)` and avoid a loop – Camilo Terevinto May 25 '18 at 00:17
@CamiloTerevinto, added to the answer, thanks. – Mohammed Noureldin May 25 '18 at 00:20
Order does not work, use OrderBy – Hossein Golshani May 25 '18 at 00:25
@HusseinGolshani, thanks, I just wrote the code on the fly. – Mohammed Noureldin May 25 '18 at 00:26
Strictly speaking the request was for the numbers 1..99 not 0..98. :-) – Frank Boyne May 25 '18 at 00:26
It's also very bad to order by a new guid instead of doing a real shuffle. This can be _biased_ (not as random as it seems), and it can lead to extra loops and sub-optimal performance in the sorting algorithm because it will generate guids for the same item in the sequence more than once; this can even cause an exception. – Joel Coehoorn May 25 '18 at 00:27
@JoelCoehoorn, how is that, could you clarify more please? – Mohammed Noureldin May 25 '18 at 00:27
1

When sorting, an algorithm will go through a sequence comparing pairs of values, and maybe swapping them. This code generates a new guid for **every** comparison. Say the sequence includes number 13, 30, and 45. It's possible to compare 13 and 30 so that 13 comes first. Then compare 30 and 45 so that 30 comes first (13, then 30, then 45), and then also compare 13 and 45 so that 45 should come before 13. It's just bad. Don't do it this way. It's not that hard to write a real fischer-yates shuffle. – Joel Coehoorn May 25 '18 at 00:32
@JoelCoehoorn, what about using Singleton `Guid` (or I mean a short term existing Guid)? – Mohammed Noureldin May 25 '18 at 00:33
Doesn't matter. This still generates a different guid for a value every time that value comes up for comparison. You _can_ use linq to do this, but you have to first `.Select()` to an anoymous type with fields for the original value and generated guid (so the guid is preserved), `.OrderBy()` to sort by the generated guid from the select, and then `Select()` back to just the values... – Joel Coehoorn May 25 '18 at 00:35
...but this is still much slower than fischer-yates because the sort has to look at each item and put it into a specific spot via a series of compares, rather than just looking at each spot and selecting a random item once. It also still has potential for bias. – Joel Coehoorn May 25 '18 at 00:40
@JoelCoehoorn, I do not understand how using singleton generates a new Guid? Please Check the update (I am just trying to understand why). – Mohammed Noureldin May 25 '18 at 00:40
The enhancement is worse... now every item has the **same** value. – Joel Coehoorn May 25 '18 at 00:41
@JoelCoehoorn, ok got it. Thank you. – Mohammed Noureldin May 25 '18 at 00:44
1

Think about what the `i => Guid.NewGuid()` expression does. When the sorting algorithm needs to compare two values, this is the code it uses (for _both_ values) to determine how those values are compared. So every time any comparison is made in in the process of performing the `OrderBy()`, it generates a whole new guid _again_, even if it's already done it before for that value. In a shuffle, that would be okay... but `OrderBy()` is written to produce _ordered_ results, and this can lead it to strange places, and take much longer than necessary to get there. – Joel Coehoorn May 25 '18 at 00:46
1

This is why javascript's sorting algorithm, for example, instead asks for a function that looks at **two** values (`a` and `b`) instead of just one `i`), where the function just does the compare... https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort – Joel Coehoorn May 25 '18 at 00:49

Hossein Golshani · Answer 5 · 2018-05-25T01:36:43.143

-2

Non efficient way (see comments):

Random rand = new Random();
HashSet<int> randomHashSet = new HashSet<int>();
while (randomHashSet.Count < 99)
    randomHashSet.Add(rand.Next(1, 100));
List<int> randomList = randomHashSet.ToList();

Update

Efficient way:

Random r = new Random();
var result = Enumerable.Range(1, 99).ToList();
for (int i = 0, j = r.Next(0, 99); i < 99; i++, j = r.Next(0, 99))
    result[i] = result[i] + result[j] - (result[j] = result[i]); // Swap

edited May 25 '18 at 01:36

answered May 25 '18 at 00:19

Hossein Golshani

1,847
5
16
27

This will duplicate a lot of numbers. – Mohammed Noureldin May 25 '18 at 00:20
This will be insanely slow, you might generate thousands and thousands of useless numbers – Camilo Terevinto May 25 '18 at 00:21
No, Hashset does not allow Duplicate! – Hossein Golshani May 25 '18 at 00:21
This question is not about performance problem! – Hossein Golshani May 25 '18 at 00:23
2

@HusseinGolshani no you don't understand, every duplicate will be ignored, and this code could run forever. – esoterik May 25 '18 at 00:23
as @esoterik said, there will be a duplicate, but they will be ignored (which is just a waste of CPU ticks). – Mohammed Noureldin May 25 '18 at 00:24
Yes, they will be ignored, which makes this algorithm largely the same as what is in the OP. Keep generating numbers until you hit no duplicates. However if you keep randomly generating the same set of numbers, you will end up in the same spot. – Evan Trimboli May 25 '18 at 00:25
This questioner need to print value not about solving problem of wasting CPU ticks! ya mohammad – Hossein Golshani May 25 '18 at 00:29
1

While it's also inefficient, it's not just about CPU ticks, this solution leads to the same problem, a potential stack overflow. The code in the answer replaces the `Contains` call in the OP with a `HashSet` for finding duplicates, but the result is the same. Taking your code, imagine the RNG keeps generating `1` forever. What happens? – Evan Trimboli May 25 '18 at 00:31
stack will never overflowed! `HashSet` count never exceeds over 99! – Hossein Golshani May 25 '18 at 00:34
Sorry, you're right, it won't overflow. But it may run forever. – Evan Trimboli May 25 '18 at 00:38
In theory of true random set you are right. but supposing above algorithm and random in programming language, all numbers seen after period of time not forever! – Hossein Golshani May 25 '18 at 00:44
thanks all for commenting and replying – Hossein Golshani May 25 '18 at 00:46

List of numbers without repetition

5 Answers5

UPDATE