CareerCup

Knuth is your friend.

void shuffle(Card[] deck) {
int numCards = deck.length;
for (int i = 0; i < numCards; i++) {
int selectedCard = (int)rand()%(numCards-i) + i;
swap(deck[i], deck[selectedCard];
}
}

void shuffle(Card[] deck) {
    int numCards = deck.length;
    for (int i = 0; i < numCards; i++) {
        int selectedCard = (int)rand()%(numCards-i) + i;
        swap(deck[i], deck[selectedCard];
    }

}

Anonymous, it does not look like your algorithm generates all permutations with the same probability.

For instance, I think Card[0] has more than 50% chance of being in the right half.

Basically, you keep shifting Card[0] to the right...

Here it algo which is commonly used.

Even though it looks very similar to above code, it is different.

// We fill the array starting from the right end.
// First we select a random card from N, and place it in Card[N]
// Then we selected a random card from remaining N-1 and place it is Card[N-1]
// etc...
// This is O(n) time algorithm.

void fisherYatesShuffle(Card [] deck) {
    
    int numCards = deck.Length;
    for (int i = numCards; i > 0; i--) {
        int selectedCard = GetRandomInteger(1, i); // Get random integer in {1,2,..., i}
        Swap(deck[i-1], deck[selectedCard-1]);
    }
}

Hi T,

Could you please specify whether this algorithm is different from the first one above? Seems that it keeps pushing the last one to the left......

Hi T,

Could you please specify whether this algorithm is different from the first one above? Seems that it keeps pushing the last card to the left......

I wasn't sure if it the above algorithm (by Anonymous) was wrong, but now I think that it is in fact correct! Thanks Bo...

For a proof (of anonymous algorithm):

Consider chances that a particular card is in position 0. it is 1/n.
Chances that a particular card is in position 1. is it (n-1)/n * 1/(n-1) = 1/n
and so on...

basically same as the fischer yates shuffle.

Sorry for causing confusion.

#include<iostream>
#include<vector>

using namespace std;

int rand()
{
static int i=32676;

i=(i*269+321)%123678+17;


return i;

}

void shuffle(vector<int> list,int k)
{

int i=0,temp=0;
int sz=list.size();
int p=0;

while(i++<k)
{
temp=rand()%sz;

swap(list[(p++)%sz],list[temp]);

}


for(i=0;i<sz;i++)
cout<<list[i]<<"\t";

return;

}

Yes, My son !! Its a random Programme. Like dad, Like son!!

void Shuffle() {
        int bagSize = SUITS_PER_DECK * CARDS_PER_SUIT;
        int index = 0;
        srand(time(NULL));
        while (bagSize) {
            index = rand() % bagSize;
            swap(cards[--bagSize], cards[index]);
        }
    }

knuth algo O(n).....as stated by T is most popularly used!!!

123678