CODEWITHSUNDEEP
algorithmshuffle
dharam
dharam

Reputation: 8096

Shuffling a bunch of keys

This question primarily relates to a famous interview question of shuffling a pack of cards. I wandered through SO and found similar questions but the answers are mostly not up to the mark or they are ignored.

The question given was to build a function to shuffle the pack of cards.

My solution: This is possible if I put all the cards in a linked list in any order ( say sorted or unsorted - order doesn't matter). I generate a random number, take its mod to the current total number of cards and remove that index from the linked list to store the card in my shuffledArray.

This solution I think is great and it has the following running time: O(n) for building the linked list in any order. O(n) for removing it from the linked list. O(1) for generating a random number each time.

So more or less we have a lower bound of O(n) for this algorithm.

What I am worried about is the space. The space taken at present is as follows: 1) O(n) for linked list 2) O(n) for shuffledArray.

Again a lower bound of O(n).

Can this be done in place ? I mean without using this n extra space. Can it be done in time less than O(n) ?

Upvotes: 1

Views: 130

Answers (3)

spicavigo
spicavigo

Reputation: 4224

How about iterating over the cards. On each step, you generate a random number between 1 and 52 and swap the current card with the card at this random number?

What do you think about that?

Upvotes: -1

kilotaras
kilotaras

Reputation: 1419

Fisher-Yates shuffle works inplace and does exactly n-1 random number generatings.

Upvotes: 3

Andrew Tomazos
Andrew Tomazos

Reputation: 68638

void shuffle(vector<T> v)
{
    int n = v.size();
    for (int i = 0; i < n; i++)
        swap(v[i], v[i+rand(n-i)]);
};

Proof by induction:

  1. a single element vector is trivially sorted
  2. the first element is randomly selected, and by induction the remainder of the vector is shuffled

Upvotes: 0

Related Questions