Shuffling a list of track indices

Question

This question has a follow-up: Follow up to Shuffling a list of track indices

I have a bunch of paths in an ArrayList<String> and when a user has activated the shuffle button, I want to have a random order to play all of them. This class should help me get every index once. The methods getNext() and getPrevious() should help me to get the last / next song when the user clicks on either the next or previous button.

public class ShuffleGenerator {

    private ArrayList<Integer> indexList;
    private int currentIndex;

    public ShuffleGenerator(){
        indexList = new ArrayList<Integer>();
        currentIndex = 0;
    }

    public void initalize( int seed, int size ){

        if( !indexList.isEmpty() ){
            indexList.clear();
        }

        if( size > 0 ){

            //fill it with indices
            ArrayList<Integer> indices = new ArrayList<Integer>();
            for( int i = 0; i < size; i++ ){
                indices.add(i);
            }

            Random rnd = new Random(seed);

            do{


                int index = rnd.nextInt(indices.size());
                indexList.add( indices.get(index) );
                indices.remove(index);

            }while( indices.size() > 0 );

        }

    }
    /**
     * Get the next index.
     * @return -1 if failed otherweise the index.
     */
    public int getNext(){

        //if currentIndex is invalid
        if( currentIndex+1 >= indexList.size() || indexList.isEmpty() ){
            return -1;
        }

        currentIndex++;
        return indexList.get(currentIndex);
    }

    /**
     * Get the previous index.
     * @return -1 if failed otherwise the index.
     */
    public int getPrevious(){

        //if currentIndex is invalid
        if( currentIndex-1 < 0 || indexList.isEmpty() ){
            return -1;
        }

        //decrement the current index so we can get the previous one
        currentIndex--;

        return indexList.get(currentIndex);
    }


} 

I tested it twice and it seems like I get every index from 0 to size-1 in a random order. But is it really giving me every index? I might have made a mistake and just not noticed yet. And is there anything to improve?

Answer 1

Sorting Algorithm

Your sorting algorithm is fine. Note that as pointed out in the other answers, improvements could be made to it to speed it up. As it is right now, however, it does produce good results.

However, java.util.Random uses a long as seed. I suggest changing public void initalize( int seed, int size ) to public void initalize( long seed, int size ). Keep in mind that you should use a varying seed if you want to implement some sort of randomize function.

An optimization: indices.remove(int index) will return the removed element. This means you can replace

indexList.add( indices.get(index) );
indices.remove(index);

with

indexList.add( indices.remove(index) );

Additionally, checking if indexList is empty is not needed. You're free to clear the list regardless of whether it has content or not.

Other functions

if( currentIndex+1 >= indexList.size() || indexList.isEmpty() ){//in getNextIndex()

You never allow currentIndex to get below 0. Collection.size() can't return a value lower than 0. Thus, the second condition will never evaluate to true.

Additionally, when shuffling, you don't reset currentIndex to 0. Is that intended?

Naming

initalize is a typo, I think. It should be initialize. Names with typo's are hard to remember as you need to remember which way it is written exactly.

Use of built-in functions

while( indices.size() > 0 );//in initalize

You have .isEmpty() for that. I suggest you use it.

Comments

/**
 * Get the next index.
 * @return -1 if failed otherweise the index.
 */
(...)
/**
 * Get the previous index.
 * @return -1 if failed otherwise the index.
 */

This comment has typo's and a grammatical issue. I recommend @return -1 if failed, otherwise the index. instead. Clarifying what the index is wouldn't be a bad idea either.

---

    //if currentIndex is invalid
    if( currentIndex+1 >= indexList.size() || indexList.isEmpty() ){
        return -1;
    }

"Invalid" is arbitrary. How about "if the next index is out of bounds"?

---

One of your public methods, initialize (or that's what it should be called after you've fixed your typos), is lacking javadoc. I suggest you add it - in particular, explain what the parameters are for. Lastly, you might want to explain the purpose of the class by placing javadoc at the top of the class.

Answer 2

I would remove the:

if( size > 0 )

and replace the

do {...} while

with a

while {...}

to simplify the structure of the code.

You can also redesign your algorithm to simplify it further. You can use an Array instead of ArrayList and use the following shuffle algorithm which avoids the use of a supplementary array. Here is the complete code:

import java.util.Random;

public class ShuffleGenerator {
    private int indices[];
    private int nextIndex;

    ShuffleGenerator(int size) {
        indices = new int[size];
        nextIndex = 0;
        for( int i = 0; i < size; i++ ){
            indices[i]=i;
        }
    }

    public void shuffle(Random rnd){
        for( int i = 0; i < indices.length; i++){
            // place a random element j>=i into position i
            int j = i + rnd.nextInt(indices.length-i);
            // swap i and j
            int c = indices[i];
            indices[i] = indices[j];
            indices[j] = c;
        }
    }

    /**
     * Get the next index.
     * @return -1 if at the end of the sequence.
     */
    public int getNext(){
        if( nextIndex >= indices.length){
            return -1;
        }
        return indices[nextIndex++];
    }

    /**
     * Get the previous index.
     * @return -1 if at the start of the sequence.
     */
    public int getPrevious(){
        if( nextIndex <= 0){
            return -1;
        }
        return indices[--nextIndex];
    }
}

BTW I think it makes more sense to pass a Random object instead of a seed. How do you choose the seed to pass to the function?

added thanks to @Pimgd I noticed that there was a problem in your code: the first call to getNext() should return the first element of the sequence not the second...

Actually the interface getNext,getPrevious is not very good in my opinion (image how you would use it). I think it would be best to have getCurrent, next, prev where next and prev return void. Or you could simply define length and at methods and remove the cursor from the class.

Answer 3

This is far too complicated and is trying to duplicate the work of a standard library method. Worse still, it is notoriously easy to create a bad shuffle which does not allow some permutations to ever result. The more complicated the code, the more likely it is that you've made a bad shuffle which is hard to detect. The Collections library already uses the known good Fischer-Yates algorithm and takes only one line.

import java.util.*;

public class ShuffleAlist {
   public static void main(String args[]) {
      List<String> alist = new ArrayList<>();
      alist.add("A");
      alist.add("B");
      alist.add("C");  

      System.out.println("original: " + alist);

      Collections.shuffle(alist);      

      System.out.println("shuffled: " + alist);
   }
}

Answer 4

But is it really giving me every index?

Answer is yes. It also seems that you'd getting quite a random permutation (I don't think your application cares about cryptographically strong random). You have some performance problem though.

Removal from the midst of an ArrayList results in shifting elements on the right of the removed one, that is a random removal cost is \$O(n)\$, resulting in a \$O(n^2)\$ total complexity. Besides, the mere presence of indices adds a linear space complexity. All these complications are unnecessary.

Shuffling indexList in-place by means of swapping values reduces complexity to linear time and constant space.

And I dare to propose using a plain int indexList[] instead of ArrayList<Integer>.

Answer 5

Do you care if the sequence is "seemingly random" instead of actually random? If the answer is "no" then there is a really fast, simple and cool trick you can use:

"Fake shuffle"

If you are shuffling between \$k\$ items. Pick any prime \$p>k\$ (use a sieve at program start, or hard-code a list of big primes). Finally pick any random starting index \$0\le i_0<k\$.

Then the next index to visit is always \$i_j=(i_{j-1}+p) \mod k\$.

This deceivingly simple algorithm will visit all the \$k\$ items in a seemingly random order without visiting any item twice (in any loop over all items).

Example

Don't believe me? Try this: \$k=8\$, \$p=11\$,

• \$i_0 = 4\$.
• \$i_1 = (4+11) \mod 8 = 7\$
• \$i_2 = (7+11) \mod 8 = 2\$
• \$i_3 = (2+11) \mod 8 = 5\$
• \$i_4 = (5+11) \mod 8 = 0\$
• \$i_5 = (0+11) \mod 8 = 3\$
• \$i_6 = (3+11) \mod 8 = 6\$
• \$i_7 = (6+11) \mod 8 = 1\$

We have visited all indexes exactly once in 8 steps. What would the next index be? Well \$i_8 = (1+11) \mod 8 = 4\$ and the cycle would repeat. Want another cycle? Pick another \$p\$!

Previous index

Getting the previous index is a bit more difficult. Consider the modulus of a positive number: \$ R = a \mod b \$ then we have that \$\frac{a}{b}=Q+\frac{R}{b}\$ for some integer \$Q\$. In our case: \$R=i_j\$ and \$b=k\$ and we're interested in \$a=i_{j-1}+p\$.

So solving the above gives: \$i_{j-1} = k\cdot Q+i_j-p\$. We then have \$0\le i_{j-1}<k\$ and there exists only one \$Q\$ for which this is true.

Just assume \$Q=0\$ for starters, then \$i_j<k<p \Leftrightarrow i_j-p<0\$ then we have \$Q=\left\lceil\frac{i_j-p}{-k}\right\rceil\$.

So finally: \$i_{j-1}=k\cdot \left\lfloor\frac{p-i_j+k-1}{k}\right\rfloor+i_j-p\$

Example reverse

Here we go: \$i_6=6 \rightarrow i_5 = 8\cdot \left\lfloor\frac{11-6+8-1}{8}\right\rfloor+6-11=3 \$.

The others are left as an exercise for the reader. :)

Caveat

If the number of items happens to be prime, then this will "shuffle" to just a plain reverse. You should detect prime sizes and then padd the size and just skip indicies outside of the range.

Note: I don't remember the name of this algorithm, if some one can help me I'd be very happy!

Edit

Couldn't stop myself, here's an implementation. :)

public class ShuffleGenerator {
    // Add more here
    private static final int[] PRIMES = new int[]{ 941083987, 776531401, 573259391};

    private final int size;
    private final int actualSize;
    private final int prime;
    private int currentIndex;

    public ShuffleGenerator(int aSeed, int aSize ){
        actualSize = aSize;
        size = 2*3*4*aSize; // Make sure size is not prime

        // TODO: Make sure size < prime
        prime = PRIMES[aSeed % PRIMES.length];
        currentIndex = ((prime + aSeed)*aSize) % size;
    }

    /**
     * @return the next index.
     */
    public int getNext(){
        do{
            currentIndex = (currentIndex + prime) % size;
        }while(currentIndex >= actualSize);
        return currentIndex;
    }

    /**
     * @return the previous index.
     */
    public int getPrevious(){
        do{
            // Yes, parenthesis are needed to floor.
            currentIndex = size * ((prime - currentIndex + size - 1)/size) + currentIndex - prime;
        }while(currentIndex >= actualSize);
        return currentIndex;
    }

    public static void main(String[] args){
        int size = Integer.parseInt(args[0]);    
        ShuffleGenerator sg = new ShuffleGenerator(0, size);

        System.out.println("Forwards");
        for(int i = 0; i < size; ++i){
            System.out.println(sg.getNext());
        }

        System.out.println("Backwards");
        for(int i = 0; i < size; ++i){
            System.out.println(sg.getPrevious());
        }
    }
}