Shuffling an Array (Java)

Question

I’m trying to randomly shuffle integers in an array. That seems simple enough, but I have to shuffle them so that they still remain in a particular order (odd, even, odd, even, etc). For example, if the original array contained [1, 2, 3, 4, 5, 6, 7, 8] then the shuffled array might look like [5, 8, 7, 4, 1, 6, 3, 2], but always retaining the same alternating order, starting with odd.

Thanks for the help. By the way, this isn’t my exact homework problem. I just want to figure out how to do this so that I can do my homework. I don’t know where to start.

Answer 1

I would probably:

1. Grab all the elements at the ODD indexed positions into a separate array and shuffle that
2. Grab all the elements at the EVEN indexed positions into a separate array and shuffle that; then
3. Splice them back to together

Answer 2

You can let the desired elements of the array appear as a List<Integer>, by implementing AbstractList accordingly, as a view on the relevant array elements. Then, a simple Collections#shuffle on the lists will do the trick.

This may seem "unconventional" at the first glance, but has some advantages:

• it operates on int arrays (although you can change it to Integer if you want to)
• it does not need to copy the array (no additional memory overhead)
• it does not need to "process" the array in any way (other than shuffling it)

Implemented here as an MCVE:

import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class ConstrainedShuffle
{
    public static void main(String[] args)
    {   
        int array[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };

        System.out.println("Before: " + Arrays.toString(array));

        constrainedShuffle(array, new Random(0));

        System.out.println("After : " + Arrays.toString(array));
    }

    private static void constrainedShuffle(int array[], Random random)
    {
        Collections.shuffle(asList(array, 0, 2), random);
        Collections.shuffle(asList(array, 1, 2), random);
    }

    private static List<Integer> asList(int array[], int offset, int stride)
    {
        int size = (array.length - offset + stride - 1) / stride;
        return new AbstractList<Integer>()
        {
            @Override
            public Integer get(int index)
            {
                return array[offset + index * stride];
            }

            @Override
            public Integer set(int index, Integer element)
            {
                int i = offset + index * stride;
                Integer old = array[i];
                array[i] = element;
                return old;
            }

            @Override
            public int size()
            {
                return size;
            }
        };
    }
}