[General Algorithme] Shuffling Cards

[kv83]

Yeah, this are the fun parts of programming. I am working on a game, and I am at the point where I want to shuffle cards (Don't telling you what kind of cards though).

The algorithme I was thinking about, was like this;

All cards are stored in an array; like this:

Code: Select all

.db Card1, Card2, Card3, Card4, Card5 ....

I will take the first card, make a random number (in this case between 0 and 4) and put it in another array on that location. Let's say 3

Code: Select all

.db 0,0,0,Card1,0

than i will repeat this. If the position is already taken, I will generate a new random number. This will be done till all cards are stored

Code: Select all

.db Card3, Card5, Card2, Card1, Card4

Now my question is: How would you approach such a thing? Maybe You have a better way? I would really like to know

[CoBB]

This is fine. I'd probably not generate a new random number if the slot chosen is already taken, but I'd rather start going in either direction (with wraparound at the borders) until I find the first free slot. The direction doesn't have to be always the same, you can decide it e. g. according to the LSB of the original number.

[kv83]

I'd probably not generate a new random number if the slot chosen is already taken, but I'd rather start going in either direction (with wraparound at the borders) until I find the first free slot. The direction doesn't have to be always the same, you can decide it e. g. according to the LSB of the original number.

Yeah... good idea... I already worried that in case of alot cards (around 60), generating every time a new random number would take up a lot of time...

[Kozak]

There is a chance that it will stay in that random loop for years .

[Kalimero]

You can shuffle an array in place by picking a random spot and swap that with the first. Pick one of the remaining random spots and swap it with the second and so on. Actually, what you do is making a new deck with random cards from the old one. The following code does it backwards, which has some advantages.

Code: Select all

int num_of_cards = 50;
cards[num_of_cards];
for (int i = num_of_cards-1; i > 0; i--) {
  int rand = randint(...); // 0 <= rand < i
  tempcard = cards[rand];
  cards[rand] = cards[i];
  cards[i] = tempcard;
}

If you need to preserve the original order, just make a copy.

[teoryn]

I'd go with Kalimero and the in place swap. Besides the benifit of in place swaping, you don't have to worry about spending a long time looking for an empty spot. Even if you step to one side and searching for an empty spot, if you've got 52 cards, those last few cards could take some time to get in place.

[kv83]

You can shuffle an array in place by picking a random spot and swap that with the first. Pick one of the remaining random spots and swap it with the second and so on. Actually, what you do is making a new deck with random cards from the old one. The following code does it backwards, which has some advantages.

Code: Select all

int num_of_cards = 50;
cards[num_of_cards];
for (int i = num_of_cards-1; i > 0; i--) {
  int rand = randint(...); // 0 <= rand < i
  tempcard = cards[rand];
  cards[rand] = cards[i];
  cards[i] = tempcard;
}

If you need to preserve the original order, just make a copy.

Hey, that's nice... I already thought there would be another way... I think I will use this one

[CoBB]

Instead of the real data you can also shuffle an array of indices (initialised by id=i for each i) and use them to address the items. In that case you retain the original order as well.

[tr1p1ea]

Is this just for fun? Are you going to fill us in on your project?

[kv83]

Is this just for fun? Are you going to fill us in on your project?

Not yet my friend, not yet