creating a shuffle method for playlist in java

Question

Although the instructions below seem to be clear, I am utterly confused on how to implement this code.

One of the most popular features of contemporary music software is the ability to randomize the order of the songs in a playlist—an action called “shuffling” the songs. Create a shuffle method using the below pseudo code as a guide:

create a new empty arraylist (called newList)

while (there are still songs left)

randomly select the index of one song on the playlist

remove it from the current playlist and place it at the end of newList

songs = newList

Hint: Generate a random number using the Random class in the Java library. Its method is: public int nextInt(int n). This returns a pseudorandom, uniformly distributed int value as low as 0 and as high as n. Therefore, nextInt(songs.size()) gives you a random index. Remember that the size of songs lessens by one each time you add a randomly selected song to newList. You will need to account for this each time you generate a random number.

This is what I have which causes the program to crash. I need help with retrieving a song from the array, removing it, and placing it in a new array list. PLEASE HELP ME!

public int nextInt(int n) {

int index = randomGenerator.nextInt(songs.size());
              return index;
 }
public void shuffle (){
    newList = new ArrayList<Mp3> ();
    while (songs.size()>0){
        Mp3 song = songs.get(nextInt(songs.size()));
        newList.add(song);
        System.out.println("new list" + newList);
   }
 }

Answer 1

import java.util.Random;

public class SuffleSongs {

    public static void main(String[] args) {

        List<String> playList = new ArrayList<String>();
        playList.add("Song1");
        playList.add("Song2");
        playList.add("Song3");
        playList.add("Song4");
        playList.add("Song5");
        playList.add("Song6");
        playList.add("Song7");
        playList.add("Song8");
        playList.add("Song9");
        playList.add("Song10");
        playList.add("Song11");
        playList.add("Song12");
        playList.add("Song13");
        playList.add("Song14");
        playList.add("Song15");
        playList.add("Song16");
        playList.add("Song17");
        playList.add("Song18");
        playList.add("Song19");
        playList.add("Song20");
        playList.add("Song21");

        // shuffle the playlist
        for (int i=0; i<playList.size(); ++i) {
            Random rand = new Random();
            int temp = rand.nextInt(playList.size() -i) + i;
            Collections.swap(playList, i, temp);
        }

        // print the shuffled playlist
        for(int j = 0; j < playList.size(); ++j) {
            System.out.println(playList.get(j));
        }

    }

}

This will shuffle without need of creating new playlist (ArrayList).
Basically this code just gets a playlist ArrayList and then shuffle within the same ArrayList.

Answer 2

You're on the right track there, but you forgot to implement one step of the description:

remove it from the current playlist and place it at the end of newList

The method Shuffle needs to be rewritten to the following:

public void shuffle (){
    newList = new ArrayList<Mp3> ();
    while (songs.size()>0){
        Mp3 song = songs.get(nextInt(songs.size()));
        songs.remove(song); // the forgotten step
        newList.add(song);
        System.out.println("new list" + newList);
   }
 }

Answer 3

The program goes crash, it is because, in your shuffle method, while (songs.size()>0){ is always be true. The size of list is not changed.

If you want to write a shuffle method with your own, then a simple way is to iterater the songs list and swap 2 songs of current index i and the song with a random index.

     public void shuffle (List<Mp3> songsList)
     {
         for(int i=0;i< songsList.size(); i++)
         {
             //Do something here
                              //generate a random number
             //Swap songs according to the i index and and random index.
         }
     }

The simpliest way is to use Collections # shuffle method to make the list to be random.

Corresponding source code of shuffle in Collections is as follows:

/**
 * Randomly permutes the specified list using a default source of
 * randomness.  All permutations occur with approximately equal
 * likelihood.<p>
 *
 * The hedge "approximately" is used in the foregoing description because
 * default source of randomness is only approximately an unbiased source
 * of independently chosen bits. If it were a perfect source of randomly
 * chosen bits, then the algorithm would choose permutations with perfect
 * uniformity.<p>
 *
 * This implementation traverses the list backwards, from the last element
 * up to the second, repeatedly swapping a randomly selected element into
 * the "current position".  Elements are randomly selected from the
 * portion of the list that runs from the first element to the current
 * position, inclusive.<p>
 *
 * This method runs in linear time.  If the specified list does not
 * implement the {@link RandomAccess} interface and is large, this
 * implementation dumps the specified list into an array before shuffling
 * it, and dumps the shuffled array back into the list.  This avoids the
 * quadratic behavior that would result from shuffling a "sequential
 * access" list in place.
 *
 * @param  list the list to be shuffled.
 * @throws UnsupportedOperationException if the specified list or
 *         its list-iterator does not support the <tt>set</tt> method.
 */
public static void shuffle(List<?> list) {
    shuffle(list, r);
}