Shuffling chunks of ints in an array

Question

The shuffle method in ShuffleMethods.java takes an array of ints and shuffles them by chunks of ints in another array. So for example, if we had an array of ints called nums comprising of 0,1,2,3,4,5 and a chunks of ints of 2,1,3. The method reads the first element of the chunks array which is 2. The shuffle method then gets the first two elements of the nums array 0 & 1 and puts them at the end of the array to give this result: 2,3,4,5,0,1, Then for the next chunks of 1 the number is 2 is selected and put on top of the 0,1 giving this result 3,4,5,2,0,1. And then finally the last chunks of 3 selects 3, 4, 5 and puts them on top of the 2 giving this result 3,4,5,2,0,1.

The shuffle method algorithm complexity is currently \$O(n^3)\$. I am looking to get it down to \$O(n)\$. Also, I am hoping to improve the pairs method which finds the number of consecutive numbers from the original deck that are still together in the shuffled deck.

ShuffleApp.java

package Shuffle;

import java.util.Arrays;
public class ShuffleApp{

public static void main(String[] args){
      ShuffleMethods test = new ShuffleMethods();
      int[] test1 = {2, 1, 3};


     test.makeNew(6);
     test.shuffle(test1);
     test.pairs();
     test.print();
   }


}

Shuffle.java

package Shuffle;
public interface Shuffle{
    public void makeNew(int size);
    public int[] getCurrent();
    public void shuffle(int[] chunks);
    public int pairs();
}

ShuffleMethods.java

package Shuffle;
import java.util.*;

public class ShuffleMethods implements Shuffle{


    private int[] nums;
    private int[] numsCopy;

    /**Fills nums with ints based on user parameter from 0 to size-1**/
    public void makeNew(int size){
        nums = new int[size];
        for(int i = 0; i < size; i++){
            nums[i] = i;
        }
        numsCopy = nums.clone();
    }

    public int[] getCurrent(){
        return nums;
    }

    /**Shuffles the ints**/
    public void shuffle(int[] chunks){

        int temp = 0;   
        int count = 0;
        int endIndex = nums.length;



            count = 0;
            while(chunks[i] > count) {

                temp = nums[0];


                for(int k = 1; k < endIndex; k++) { 

                    //Move all the elements back
                    nums[k-1] = nums[k];

                }

                nums[endIndex-1] = temp;

                count++;

            }
            endIndex -= chunks[i];

        }
    } 

    /**Returns the number of pairs of consecutive numbers in the shuffled deck that were together in the original**/
    public int pairs(){

       ArrayList<Integer> pairList = new ArrayList<Integer>();
        int pairs = 0;

        for(int i = 1; i < numsCopy.length; i++) {

            if (numsCopy[i-1] == numsCopy[i] - 1  && !pairList.contains(numsCopy[i-1]) && !pairList.contains(numsCopy[i])) {
                pairList.add(numsCopy[i-1]);
                pairList.add(numsCopy[i]);
            }                
        }  

         for(int i = 1; i < nums.length; i++) {

           if (nums[i-1] == nums[i] - 1 && pairList.contains(nums[i-1]) && pairList.contains(nums[i])) {
             pairList.remove(Integer.valueOf(nums[i-1]));
             pairList.remove(Integer.valueOf(nums[i]));         
                pairs++;
            }

         }
       System.out.println("Number of pairs " + pairs);
        return pairs;



}

Answer 1

• pairs is overcomplicated indeed. Notice that a block of size k contributes k-1 pairs, and no other pair exists. So the total is a sum of (k - 1) taken over all blocks. Final observation is that the sizes of blocks add up to the size of array, therefore pairs = num.size() - blocks.size() is all you need.

• shuffle can be performed in linear time (strictly speaking, in \$O(kn)\$, where k is number of blocks) in place (\$O(1)\$ space complexity). The key algorithm is known as rotate. One possible implementation is

  void rotate(int[] array, int first, int mid, int last) {
      reverse(array, first, mid);
      reverse(array, mid, last);
      reverse(array, first, last);
  }
  

  There also is an arguably faster implementation, where each element is moved exactly once. Try to figure it out yourself.

Answer 2

First of all, it seems like you're way overcomplicating the pairs check. Since you start with the numbers 0 till size in consecutive order, you could just check how often 2 numbers are still in consecutive order. This is as easy as:

public int pairs(){
    int result = 0;
    for(int i = 1; i < nums.length; i++){
        if(nums[i] == nums[i-1] + 1){
            result ++;
        }
    }
    return result;
}

The only issue I have with this is that for your example main run, my pairs method returns 3 which I think is correct: (3-4, 4-5 and 0-1). But yours only returns 2. Did I misunderstand what you were trying to calculate here?

Notice also that this implementation just uses the shuffled nums list, making the numsCopy array obsolete.

---

I'm not sure why your makeNew(int size) isn't a constructor. Is it ever interesting for the same ShuffleMethods instance to reset to a new deck?

I would put it in a constructor instead, and remove the makeNew method from the interface.

If you want you can also put a factory method inside the interface to hide the ShuffleMethods class :

public static Shuffle makeNew(int size) {
    return new ShuffleMethods(size);
}

To use this let's look at the corrected main method:

public static void main(String[] args){
    int[] test1 = {2, 1, 3};

    Shuffle test = Shuffle.makeNew(6);
    test.shuffle(test1);
    System.out.println(test.pairs());
    System.out.println(test);
}

You'll notice that I changed some other things as well here. First, I changed the type of test to Shuffle. It's always better to use the interface over the concrete implementation. This also applies to List instead of ArrayList:

List<Integer> pairList = new ArrayList<Integer>();

Although with my new implemenation of the pairs method this isn't needed anymore.

The other thing I changed is replace the print method with a toString() method. Since your interface didn't have the method print we couldn't use it anymore. Now I could've just added that method to the interface, but it made more sense to me to just override the toString method. This also enabled me to simplify printing the deck to System.out.println(test). The toString() method is implicitly called for us.

---

The shuffle method can also greatly be simplified if we use System.arraycopy(...). This is a built in method that uses a greatly optimised partial copy from one array to another. I believe this is easiest to explain by just showing how I would use it:

public void shuffle(int[] blocks){
    int[] original = nums.clone();
    int originalIndex = 0;
    int newIndex = nums.length;
    for(int block : blocks){
        newIndex -= block;
        System.arraycopy(original, originalIndex, nums, newIndex, block);
        originalIndex += block;
    }
}

I first make a copy of the original array that I can use as a source for the arraycopy. That way we don't have to be afraid to overwrite any numbers that we haven't handled yet.

Next I keep track of 2 indeces. originalIndex is the first number in the original list that we haven't touched yet. newIndex is the place where it needs to be copied to.

I use a specialised foreach loop that takes each number from the blocks array one at a time. This is easier to use and easier to read. I believe it's available since java 5.

Then all that's left to do is update the indeces and copy the block of numbers from the original to our shuffled nums array.

---

Both algorithms now run in O(n) like you requested (I think). Not sure if they could still be improved or not.

---

The last thing I want to point out is that the name for ShuffleMethods is badly chosen. This class not only represents the methods that you can use on a deck, but also stores the deck itself. Either rename this to Deck so that the name fits what it actually is. Or change the entire implementation to a utility class instead (note that some people are really against utility classes, so I'm not going to say this is the ideal way to go. It depends on what you prefer).

The utility class would look something like this:

public class ShuffleMethods {
    public static int[] makeNew(int size) {
        ... //hey look, our factory method!
    }

    public static void shuffle(int[] nums, int[] blocks){
        //implemenation is the same, but takes `nums` as parameter instead of using field
    }

    public static int pairs(int[] nums) {
        //see shuffle method
    }
}

Note that you need to keep track of the int[] nums array outside of the class now.

---

A last minor thing to point out is that the convention for package names is to use all lower case letters. So this should be shuffle instead.

And that concludes my answer.