9
\$\begingroup\$

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?

\$\endgroup\$
0

5 Answers 5

5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Pimgd
    Aug 6, 2014 at 21:05
  • 1
    \$\begingroup\$ Yeah, good idea. I will post the code in a few minutes. Had no more time yesterday. \$\endgroup\$
    – Davlog
    Aug 7, 2014 at 15:17
7
\$\begingroup\$

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.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Pimgd
    Aug 6, 2014 at 21:12
  • \$\begingroup\$ 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. \$\endgroup\$ Aug 6, 2014 at 21:30
  • \$\begingroup\$ True, you're right about that. Still, cyclomatic complexity of that method is only 5 right now, so it's not that bad yet. \$\endgroup\$
    – Pimgd
    Aug 6, 2014 at 21:32
  • \$\begingroup\$ @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. \$\endgroup\$ Aug 6, 2014 at 22:21
  • 3
    \$\begingroup\$ 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! \$\endgroup\$
    – Pimgd
    Aug 7, 2014 at 7:04
6
\$\begingroup\$

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);
   }
}
\$\endgroup\$
1
  • \$\begingroup\$ Thank you. I'll guess I use it instead of my class in my program. I still want to improve this class, though. \$\endgroup\$
    – Davlog
    Aug 7, 2014 at 15:15
4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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());
        }
    }
} 
\$\endgroup\$
6
  • \$\begingroup\$ size = 2*3*4*aSize; // Make sure size is not prime How about 24*aSize instead? \$\endgroup\$
    – Pimgd
    Aug 7, 2014 at 19:27
  • \$\begingroup\$ 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. \$\endgroup\$
    – Emily L.
    Aug 8, 2014 at 7:39
  • \$\begingroup\$ Why can't you just *2? \$\endgroup\$
    – Pimgd
    Aug 8, 2014 at 7:43
  • \$\begingroup\$ Not sure, but I figured that having a few more factors was beneficial for the perceived randomness. Or at least it isn't detrimental. \$\endgroup\$
    – Emily L.
    Aug 8, 2014 at 8:16
  • \$\begingroup\$ 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. \$\endgroup\$
    – Pimgd
    Aug 8, 2014 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.