Can someone please explain to me why this is an infinite loop?

Question

can someone please explain to me why this is an infinite loop? unity just hangs when i try this. im trying to build a deck of 52 cards

    public class Deck {
        private List<Card> deckList = new List<Card>();

        public Deck() {
            for (int i = 0; i<52; i++) {
                System.Random rnd = new System.Random();
                Card newCard = new Card(rnd.Next(1,13), rnd.Next(1,4));
                if (!deckList.Contains(newCard) || i == 0) {
                    deckList.Add(newCard);
                } else { i--; }
            }
        }
    }

Don't write a title like "how do I [do this thing]" if that's not what your question is about. — Robert Harvey, Feb 02 '15 at 22:27
Just so you know, `rnd.Next(x, y)` returns an integer in the range [x,y). So it won't include 13. https://msdn.microsoft.com/en-us/library/2dx6wyd4(v=vs.110).aspx — mbomb007, Feb 02 '15 at 22:30
Also, your method is really inefficient. Don't randomly add cards; you already know what a deck of cards should contain (one of each). Just create a normal, ordered deck, then use a method to shuffle it. http://stackoverflow.com/questions/273313/randomize-a-listt-in-c-sharp — mbomb007, Feb 02 '15 at 22:33
well it definetly has something to do with thte random numbers... — ken, Feb 02 '15 at 22:37
Having `rnd` inside the for loop is a bad idea, it is going to keep picking the same random number over and over because it is going to re-use the same time stamped seed. see: http://stackoverflow.com/questions/767999/random-number-generator-only-generating-one-random-number — Scott Chamberlain, Feb 02 '15 at 22:37
You can see just how horrible this method is for randomization when you consider what happens when the list gets nearly full. When there are 51 cards in the deck you know what the last one has to be, and yet you keep on trying to generate it randomly. This method is really, really awful and you should never use it under any circumstances. If you want a shuffle then use a shuffle algorithm. — Eric Lippert, Feb 02 '15 at 22:45
Another important point here is that even if you fixed the bugs, you're using a 32 bit seed to shuffle a 52 card deck. That means there are 2^32 possible shuffles, but there are 52! possible real decks of cards. There are trillions upon trillions of possible decks that you can never generate. Use a crypto-strength source of randomness for shuffling cards. — Eric Lippert, Feb 02 '15 at 22:47
sorry rob, i thought i wasn't using the list properly. i tried the new random line inside and outside, scott. I'm going to take mbomb007's advice and try to shuffle it instead — ken, Feb 02 '15 at 22:48
@EricLippert is the 32-bit VS 52! comparison valid? he is not using a single random number to generate the entire deck, he is using a single random number to pull a single card, which has at most 52 possibilities. — Dave Cousineau, Feb 04 '15 at 15:58
@EricLippert ok I think I understand. there are only 2^32 possible sequences of random numbers (since 2^32 seeds), so the numbers are not quite as "random" as they could be. thanks. — Dave Cousineau, Feb 04 '15 at 17:27
@Sahuagin: correct; `Random` is misnamed. It is a *pseudo-random number generator*; if you know the seed then the sequence is completely predictable and not "random" at all. Since there are only ~10^9 seeds, there are only ~10^9 possible sequences of numbers, and therefore only ~10^9 possible different decks generated. But there are ~10^67 possible decks in real life; this algorithm only gets a vanishingly small fraction of them. That might be important if this game is played for money. — Eric Lippert, Feb 04 '15 at 17:31
@EricLippert thinking about this, is this only an issue when you instantiate a new `Random` object every time you shuffle? there might only be 2^32 sequences of random numbers, considering only the start of the sequences, but are there not more possible shuffles than that if you could be anywhere within one particular random sequence? or does the 2^32 limitation still hold in some way? — Dave Cousineau, Feb 04 '15 at 19:31
@Sahuagin: OK, let's suppose that you come into the sequence at some point after it has been initially seeded. You wish to skip the first k numbers where k is less than 2^n for some reasonably sized n. Problem 1: How is this effectively different than simply using a different random number generator that has a seed of 32 + n bits, aside from being more expensive? Problem 2: how do you randomly generate a number between 1 and k? If you have a mechanism for generating that number then you already have a random number generator! — Eric Lippert, Feb 04 '15 at 19:37
@EricLippert I guess my question could be reworded as: if for your shuffles you used only one seed, and just continually used the same sequence for every shuffle, would there still only be 2^32 possible shuffles, or approximately that many? Or maybe there would be more? or maybe less? Would there be more than 2^32 if you at some point switched to a new seed as well? (Obviously I should spend some time reading about PRNGs rather than wasting your time. thanks and sorry.) — Dave Cousineau, Feb 04 '15 at 19:55
@Sahuagin: Ah, so now your question is: we pick a seed and then we generate many decks in a row, starting from that seed. How many decks can we get out before we repeat? The `Random` generator "loops back" on itself after I think about 2^55 iterations, and each shuffle takes let's say about 2^6 iterations. So that's 2^49 decks this way, which is still a vanishingly small fraction of the ~2^225 decks available in real life. Also, again we have the practical problem of *how do you choose one of those 2^49 decks at random*? — Eric Lippert, Feb 04 '15 at 20:45
@Sahuagin: But yes, if you have more questions about this you should probably post a new question; this is a question-and-answer site after all! We are at this point close to if not over the edge of my knowledge of PRNGs. — Eric Lippert, Feb 04 '15 at 20:45

score 6 · Accepted Answer · edited May 23 '17 at 12:06

You are re-creating Random in your tight loop. This uses the same seed value each time, so you are generating the same card every time. Since you decrement your loop variable if the card already exists in the deck, it spins "forever". In reality, if the seed eventually changed, you would be OK.

Your code should be:

       System.Random rnd = new System.Random();
       for (int i = 0; i<52; i++) {
            Card newCard = new Card(rnd.Next(1,14), rnd.Next(1,5));
            if (!deckList.Contains(newCard) || i == 0) {
                deckList.Add(newCard);
            } else { i--; }
        }

Note that this is a very weird loop. I would have just used a while loop that checked if there were any cards left or something. Regardless, don't instantiate Random in a tight loop like that.

Even better, just create all the cards and shuffle them.

I missed one other change noted in the comments, you need to use rnd.Next(1,14) and rnd.Next(1,5) so that every card is actually generated. Otherwise there is no way out. Remember, rnd.Next's max value is exclusive.

i tried it this way first and i started with a while loop. this has changed a lot with my frustration, but you're right its definitely something with the random numbers. i'm going to try what others said and make a deck and shuffle it. — ken, Feb 02 '15 at 22:42
it was the most helpful but this does not work either. i actually had it this way first before i messed it up even worse and made my post — ken, Feb 02 '15 at 22:53

Robert Harvey · Answer 2 · 2015-02-02T22:31:51.100

2

Because you're changing the loop variable inside the loop.

} else { i--; }

so the terminating condition

i<52

never becomes false.

In general, you shouldn't monkey with loop variables this way. It's very confusing, and violates the Principle of Least Surprise. Find a better way to do it that doesn't involve messing with the loop variable.

edited Feb 02 '15 at 22:31

answered Feb 02 '15 at 22:28

Robert Harvey

178,213
47
333
501

1

I believe `i` remains incremented every time a unique card is added to the deck. It *should* terminate, if he actually generates all the cards (which I don't think he is). A terrible loop/practice though. – BradleyDotNET Feb 02 '15 at 22:31

Can someone please explain to me why this is an infinite loop?

2 Answers2