How to unshuffle a list?

Question

I am using Collections.shuffle(list); to shuffle a list but I don't know how to unshuffle it?I was thinking of saving the list before shuffling and then shuffle it so that a backup is maintained and can re restored whenever required ,but this seems like a inefficient way of doing it and will take up time and memory ....if you know a more logical way of doing it,can you please elaborate it ?? by the way here is how my app looks :D

Answer 1

There's no such concept of unshuffling - after you've shuffled a deck of cards, how would you get back to the previous state, for example?

If your original collection is ordered in some definitive way, just sort it again. Otherwise (e.g. if it's been hand-ordered) you must take a copy before you shuffle.

In theory you could:

• Generate a random seed and remember it
• Create a Random and pass that into shuffle
• Later, create an ArrayList<Integer> from 0 to size (exclusive)
• Shuffle that list with a new Random created with the original seed
• Use the results to work out the original index of each item (because you know where each original item ended up in the shuffled list)

... but that's an awful lot of work. Unless your collection is really too big to keep the extra copy (don't forget it's just a copy of references, not whole objects), I'd just clone the collection before shuffling.

Answer 2

First, Jon's answer should be used, because that's the simplest and cleanest. Anyway, it is possible to reverse the shuffling with a known random source, since Collections.shuffle() specifies the used algorithm. Again, do not do this, but here's the process for anyone curious:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Unshuffle {
    public static void main(String[] args) {
        List<Integer> data = new ArrayList<Integer>();
        for (int i = 0; i < 20; i++) {
            data.add(i);
        }
        System.out.println(data);
        Collections.shuffle(data, new Random(42));
        System.out.println(data);
        unshuffle(data, new Random(42));
        System.out.println(data);
    }

    private static <T> void unshuffle(List<T> list, Random rnd) {
        int[] seq = new int[list.size()];
        for (int i = seq.length; i >= 1; i--) {
            seq[i - 1] = rnd.nextInt(i);
        }
        for (int i = 0; i < seq.length; i++) {
            Collections.swap(list, i, seq[i]);
        }
    }
}

And the output is:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
[15, 16, 14, 13, 5, 11, 17, 18, 8, 2, 6, 7, 3, 1, 19, 4, 12, 0, 9, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]