CareerCup

public void shuffle()
{
for ( int i = 0; i < deck.length; i++ )
{
int j = ( int ) ( Math.random() * 52 );
Card temp = deck[ i ]; // swap
deck[ i ] = deck[ j ];
deck[ j ] = temp;
}
}

move every card to its next position

public void shuffle()
{
for ( int i = 51; i >= deck.length; i-- )
{
int j;
do {
j = ( int ) ( Math.random() * i );
}
while (j == i); // to check if getting same postion as before
Card temp = deck[ i ]; // swap
deck[ i ] = deck[ j ];
deck[ j ] = temp;
}
}

public void shuffle(Card[] deck)
{
    for ( int i =  deck.length - 1; i > 0; i-- )
    {
        int j = ( int ) ( Math.random() * (i - 1) );
        Card temp = deck[ i ]; // swap
        deck[ i ] = deck[ j ];
        deck[ j ] = temp;
    }
}

i think if we consider the shuffle as a real life scenario, it wont be a single card to another card swap. Basically its like moving k cards from down to the top. in other words its basically k elements rotation problem.

Considering that, we can first generate a random number (say N) which will indicate the number of times shuffle will be done. Next we have to generate N random numbers(basically N different values of k).
To ensure the above stated criteria, keep on adding these N k-values.(k1+k2+...kN).
If the sumofKs%sizeofdeck, that will indicate the relative displacement of each card. If it is 0 then keep on generating ks till the sumofKs%sizeofdeck=0.

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

int main() {
  vector<int> cards(52);
  for (int i = 0; i < 52; ++i) cards[i] = i;

  srand(time(NULL));
  for (int i = 0; i < 52; ++i) { // get a random permutation of 0..51
    int j = rand() % (i + 1);
    cards[i] = cards[j];
    cards[j] = i;
  }

  for (int i = 0; i < 26; ++i) { // how to shuffle: swap pairs of cards
    cout << cards[i] << " <-> " << cards[i + 26] << endl;
  }

  return 0;
}

1. Given an array of size 52 (indexes 0 to 51) we want to shuffle it such that no card will get the same position as previously.

2. Start from the end of the array i.e. at index 51. Generate a random number x between [0,50] using rand() and mod 51 operation. Swap arr[51] and arr[x].

3. Repeat the same step for the rest of the array. That is, in the second step go to index 50. Generate a random number x between [0,49]. Swap arr[50] and arr[x].

4. In the end you come to index 0. You don't have to worry about arr[0] not being swapped as when you were processing at index 1 it would have been definitely been swapped with arr[0].

guys..check the solution in CC book.

shuffle(int deck[])
{
   for(i=51;i>=0;i--)
   {
       r=rand()%i;
       t=deck[r];
       deck[r]=deck[i];
       deck[i]=t;
   }
}

The main focus of the problem is not letting the card getting placed in the position it earlier occupied.
If there is no restriction of doing it in-place
Then we can maintain a hash table<card,pos> which would take card object as the key and position as the value. It updates the value after every successful shuffle.

So you can use any random number generator and before the swap first check if the resulting position is not the one it occupied earlier.
If yes then generate a new random number.
This would maintain the condition of not placing the card in its earlier position.

ps: Any random number generator, how good it might be would give duplicate values.

Its standard algorithm by Knuth.
For ith card, generate a random number below i, swap the card and decrement i.

I think i can come up with a more interesting algorithm.
Let the Deck of cards be an Array Deck[N]
1) Consider that you actually have a two decks. One deck of cards at odd indices, and one with even indices. O(1)
ie {D[0],D[2]....D[50]] and {D[1],D[3]...D[51]}
2) Now sort both the arrays separately by doing k swaps. where K << 52. O(k)
3) Now rotate the deck by one place, by putting odd elements in even places and even elements in odd places. O(N).

Email: sancho.nitw@gmail.com