Why am I getting duplicates in my array?

Question

So I am making an array of 52 ints, I add in random numbers and make sure there all different. If there is a duplicate I would generate a new number so that current index that am at is different. Where am I going wrong?

for(i=0; i < SIZE; i++){

    deck[i] = (rand() % 52);

    for(c= 0; c <= i; c++ ){
            if(deck[c] == deck[i+1]){

            deck[i] = (rand() % 52);
        }

    }
}

So, if `deck[c]` matching `deck[i+1]`, you decide to re-randomize `deck[i]`? What does that fix? You need to rerandomize the guy you are testing, and also, you need to then reset `c` to `0` and start from the beginning after you rerandomize a guy. Also this is not an efficient way of shuffling the deck, you might want to look up the knuth shuffle. — Chris Beck, Sep 26 '17 at 23:25
@ChrisBeck should I should make c = 0 after getting out the inner loop and compare deck[c] == deck[i]? — Cmi, Sep 26 '17 at 23:30
You set `deck[i]` and then you are matching it with `deck[i+1]` which is not set yet. Why? Also looping once may not ensure you do not have duplicates. I agree with Chris on this being inefficient. — Ketan Mukadam, Sep 26 '17 at 23:31
https://stackoverflow.com/questions/6127503/shuffle-array-in-c — pm100, Sep 27 '17 at 00:04
in theory your way of doing it may be very slow. For the last card you need , say, 14 (its the only card left) so you have to keep calling `rnd` until you get 14, which might not happen for a long time. Better is to shuffle the array — pm100, Sep 27 '17 at 00:06

Matt Gregory · Accepted Answer · 2017-09-26T23:58:16.653

3

You can't try merely once for the random number in your inner for loop. After you generate it, you have to check all the previously generated items again to make sure you didn't generate the same random number as another item. This would do the trick (assuming SIZE = 52):

for(i=0; i < SIZE; i++){
    deck[i] = (rand() % SIZE);
    for(c= 0; c < i; c++ ){
        if(deck[c] == deck[i]){
            // Try another number
            i--;
            break;
        }
    }
}

That said, it's not a very fast solution (it could potentially never end). It's better to create an array of numbers 0 to 51 and then shuffle them by swapping two elements at a time. I'm not going to write that for you, but it's a standard way of doing it.

edited Sep 26 '17 at 23:58

answered Sep 26 '17 at 23:29

Matt Gregory

8,074
8
33
40

Doesn't the deck[c] == deck[I] give an infinite loop? So should I put the c = -1; outside the if statement? – Cmi Sep 26 '17 at 23:44
No, it's comparing the item at c with the random number you just generated. If it's the same, then you want to try another number and reset the loop variable. It has to be -1 because the first thing that's going to happen when it loops is the c++, so the next time around c will be zero. – Matt Gregory Sep 26 '17 at 23:47
It might actually be more clear to decrement `i` by one and then `break` out of the inner loop. Then you wouldn't have write that line `deck[i] = (rand() % SIZE);` twice. The `if` block would just consist of `i--; break;` – Matt Gregory Sep 26 '17 at 23:50
I tried the code you linked and I got duplicates and if you do I-- how will you get to the 51th index? I am a little confused – Cmi Sep 26 '17 at 23:55
Oh, you really don't want to bother with the case where c == i. That's actually a huge bug. I'll fix it. – Matt Gregory Sep 26 '17 at 23:57
In any case, it's totally the wrong approach. Just fill the array with 0..51 and shuffle it. – Lee Daniel Crocker Sep 27 '17 at 00:08
@LeeDanielCrocker: It's not wrong, it's just not very good. It works perfectly fine for a small array like this. – Matt Gregory Sep 27 '17 at 00:17
Thanks @MattGregory , it works well am going to run it in eclipses and go step by step through the code, so I understand it better. – Cmi Sep 27 '17 at 00:24
Even for a small array, this approach wastes a lot of time and a lot of random numbers. Think about the last one, for example: It's already generated every number except, say, 12. Now it sits in a loop generating random numbers, checking them against all 51 others every time, until it happens to generate 12. A proper fill-and-shuffle is probably hundreds of times more efficient. There is a time to use random-and-check-for-dups, but then you should use Floyd's algorithm and and better checking method. – Lee Daniel Crocker Sep 27 '17 at 00:28

score 2 · Answer 2 · answered Sep 27 '17 at 00:25

2

Totally the wrong approach. You don't want random numbers; you want precisely the numbers 0 to 51, in random order. To do this, fill the array with the values 0..51, and then shuffle it properly:

for (int i = 0; i < 52; i += 1) deck[i] = i;
for (int i = 52; i > 1; i -= 1) {
    int j = rand() % i;
    int temp = deck[j];
    deck[j] = deck[i-1];
    deck[i-1] = temp;
}

answered Sep 27 '17 at 00:25

Lee Daniel Crocker

12,927
3
29
55

In the future I will do this, as you did make valid reasons why I shouldn't do it the way I had it before – Cmi Sep 27 '17 at 22:53

Why am I getting duplicates in my array?

2 Answers2