An Efficient way of randomizing an array - Shuffle

Question

I was asked this question in an interview and I gave various solutions but the interviewer was not convinced. I am interested to find a solution. Please throw in your views :

Q: Write an efficient data structure to implement the shuffle in an ipod. It must play all the songs, each time in different random order, the same song should not be repeated. ( mostly O(n))

One solution , I thought off after the interview : I can do a randomized quick sort without recursion. Where we randomly, chose 1 pivot O(1) and then do quicksort O(n). Now songs will be sorted in some order and I play them till the end. Once it reaches the end, I will Again chose a random pivot and , repeat this process again and again.

Regards, Sethu

Answer 1

Nate's (edited) and Brian's algorithms are the Fisher–Yates shuffle O(n), while shuffling by sorting is O(nlogn), but may actually be faster in practice (http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Comparison_with_other_shuffling_algorithms). Getting song shuffling wrong may have insignificant consequences, but if you are writing a shuffling algorithm for an online poker game, make sure you know what you are doing (http://www.cigital.com/news/index.php?pg=art&artid=20).

Answer 2

You want the Fisher-Yates shuffle. Be aware of the implementation errors mentioned on that page, as your currently accepted answer falls foul of one.

Answer 3

Well, the first linear-time solution that springs to mind:

You could make a linked list of all the songs, which would take about O(n) (given that insertions are constant time operations). Then, generate a random number, modulo the size of the list to get a random index, and remove that index and append it to a new list (both of which are constant time operations).

An insertion for each O(n) + a removal for each O(n) + a second insertion O(n). This would overall lead to a linear time solution.

Edit: I completely forgot about walking the list. So, instead, you could make the result a fixed length array. Pop the head of the linked list, assign it the random index, and populate the array.

Answer 4

What you want is the Fisher-Yates Shuffle. Here's an implementation in java:

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

How it works is it treats the entire array as a hat and starts pulling random elements and lining them up at the front of the array. All elements after i are 'in the bucket', all elements before i are shuffled.

Answer 5

I am a beginner, let me say a solution that strikes to mind, if anything is wrong please make me know.

Lets assume songs are stored in either singly or doubly linked list. Every time when the music player is opened pick a random number less than (any number you wish) assume k, and reverse every k nodes in the list, similarly do it twice or at max thrice (as you wish) which would take O(2n) or O(3n) time to shuffle. finally have a pointer to the last node of the list. And every time a song is listened (a node is visited) remove the node and insert it next to the last node which can be done in O(1) time. This continues till the music player is closed.

Thanks, Eager to know the correctness of the answer.

Answer 6

Place all the songs in an array... For each element in the array swap it with a random position.