# Shuffling a list of track indices

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++ ){
}

Random rnd = new Random(seed);

do{

int index = rnd.nextInt(indices.size());
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?

-
I just posted the new code. I decided not to use an integer array for the indexList because I want to be able to change the size of it without recreating a new ShuffleGenerator instance. Or do you think I should still do it? –  Davlog Aug 7 '14 at 15:27
You should post that new code as a follow-up question. We no longer allow appended improved code. –  Jamal Aug 7 '14 at 15:29
@Jamal oh, I didn't know that. So I just ask a new question with the improved code, add "Follow up question" to the title and link it to this question? –  Davlog Aug 7 '14 at 15:32
Yes, that'll work. You can also roll back this edit. –  Jamal Aug 7 '14 at 15:33
Here is the new question –  Davlog Aug 7 '14 at 15:41

## 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.

/**
* 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.

-
May I suggest that you post this code again as an iterative review once you've applied my suggestions? I'm not sure whether it could be improved more, but that's because I've pointed out so much things that seeing the things I missed is hard. ... I think I didn't review blank space yet. –  Pimgd Aug 6 '14 at 21:05
Yeah, good idea. I will post the code in a few minutes. Had no more time yesterday. –  Davlog Aug 7 '14 at 15:17

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.

-
Whilst simplifying the structure, it might make a couple unneeded objects. Other valid options would be to return early if size <= 0, or to add a comment, maybe. –  Pimgd Aug 6 '14 at 21:12
I think it is not worth optimizing the fastest case, also because it should very rarely be used (who want to shuffle an empty list?). If one wants to optimize the code I would allocate an Array of the right size instead of growing it, and will use itself to keep track of unused indices instead of creating a supplementary temporary list. –  Emanuele Paolini Aug 6 '14 at 21:30
True, you're right about that. Still, cyclomatic complexity of that method is only 5 right now, so it's not that bad yet. –  Pimgd Aug 6 '14 at 21:32
@Pimgd the code didn't compile because it was only a snippet without the containing class. I took the time to complete the source file so now you can copy/paste and compile without errors. –  Emanuele Paolini Aug 6 '14 at 22:21
Upvoted - Wow, by changing that you fixed a bug! In the original code, there's no way to retrieve the first element other than calling getNextIndex() and then getPreviousIndex(), but yours allows you to access the first index! –  Pimgd Aug 7 '14 at 7:04

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<>();

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

Collections.shuffle(alist);

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

-
Thank you. I'll guess I use it instead of my class in my program. I still want to improve this class, though. –  Davlog Aug 7 '14 at 15:15

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>.

-

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());
}
}
}

-
size = 2*3*4*aSize; // Make sure size is not prime How about 24*aSize instead? –  Pimgd Aug 7 '14 at 19:27
2*3*4 makes it obvious that there is more than one prime factor in there. While the observant knows that 24 is not prime, they might not think about the factors involved. –  Emily L. Aug 8 '14 at 7:39
Why can't you just *2? –  Pimgd Aug 8 '14 at 7:43
Not sure, but I figured that having a few more factors was beneficial for the perceived randomness. Or at least it isn't detrimental. –  Emily L. Aug 8 '14 at 8:16
Except in the case where int overflows because you've multiplied it by 24. That'd be starting from 89478486... which is smaller than the primes you've selected. Fun stuff is bound to happen. –  Pimgd Aug 8 '14 at 8:29