Un-shuffle a compound shuffled list

Question

I am trying to un-shuffle a compound shuffled list. I am having trouble figuring out how to accomplish this.

public static void main(String[] args) {
    // Setup random
    Random rand = new Random();
    rand.setSeed(5);
    // Setup list
    ArrayList<Character> list = new ArrayList<Character>(Arrays.asList('v','y','2','w','9','n','8','v','a'));
    // Compound shuffle list
    for(int i=0;i<5;i++)
        Collections.shuffle(list, rand);
    // un-shuffle list
    // TODO
}

And also my un-shuffle method.

private static void unshuffle(ArrayList<?> list, Random rand) {
    // Create the sequence backwards
    int[] seq = new int[list.size()];
    for(int i=seq.length; i>1; i--)
        seq[i-1] = rand.nextInt(i);
    // Traverse the sequence and swapping it inversely
    for (int i=0; i<seq.length; i++)
        Collections.swap(list, i, seq[i]);
}

Edit: fixed ArrayList.

Answer 1

public class Main {

    public static void main(String[] args) {
        List<String> list = new ArrayList<String>(Arrays.asList("A", "B", "C", "D", "E", "F", "G"));
        compoundShuffle(list, 8, 13);
        compoundUnshuffle(list, 8, 13);
        System.out.println(list);
    }

    public static void compoundShuffle(List<?> list, int repetition, long seed) {
        Random rand = new Random(seed);
        for (int i = 0; i < repetition; i++)
            Collections.shuffle(list, rand);
    }

    public static void compoundUnshuffle(List<?> list, int repetition, long seed) {
        helper(list, repetition, seed);
    }

    private static <E> void helper(List<E> list, int repetition, long seed) {
        List<Integer> indices = new ArrayList<Integer>();
        int size = list.size();
        for (int i = 0; i < size; i++)
            indices.add(i);
        compoundShuffle(indices, repetition, seed);
        List<E> copy = new ArrayList<E>(list);
        for (int i = 0; i < size; i++)
            list.set(indices.get(i), copy.get(i));
    }
}

Answer 2

Two things you need to know:

1. Behavior of the Random class. This statement is particularly relevant:

If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers.

2. Behavior of the Collections#shuffle() method. This paragraph is the key:

This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.

With that knowledge and a diagram or two, you should be able to figure out how to reverse the behavior.