取消混洗复合混洗列表

Question

我正在尝试取消随机排列的复合随机列表。我无法弄清楚如何完成此操作。

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
}

还有我的洗牌方法。

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]);
}

编辑：修复了 ArrayList。

Answer 1

你需要知道的两件事：

Behavior of the Random class。这句话特别贴切：

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.

Behavior of the Collections#shuffle() method。这段是重点：

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.

有了这些知识和一两个图表，您应该能够弄清楚如何扭转这种行为。

Answer 2

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 3

如果您在洗牌前知道 Random 函数的初始种子，如果您使用相同的种子调用它，确实可以进行去洗牌。

实际上 seed 可以被视为此自定义（所以不是一个好的选择）加密算法的密钥。

假设您正在使用 Fisher-Yates 洗牌算法（我认为 Collections.shuffle 显然使用了该算法）尝试使用以下算法进行洗牌和去洗牌。它用于 int[]，将其更改为您的 Object[].

// implementing Fisher–Yates shuffling using a seed
public static void shuffleArray(int[] ar, int seed) {
    Random r = new Random(seed);
    for (int i = ar.length - 1; i > 0; i--) {
        int index = r.nextInt(i + 1);
        // simple swap
        int a = ar[index];
        ar[index] = ar[i];
        ar[i] = a;
    }
}   

// implementing Fisher–Yates deShuffler
//(you should know the **seed** used for shuffling - this is the decryption key)
public static void deShuffleArray(int[] ar, int seed) {
    //rebuild your random number sequence
    Random r = new Random(seed);
    int[] randoms = new int[ar.length-1];
    int j = 0;
    for (int i = ar.length - 1; i > 0; i--) {
        randoms[j++] = r.nextInt(i + 1);
    }

    //deShuffling
    for (int i = 1; i < ar.length; i++) {
        //use the random values backwards
        int index = randoms[ar.length - i - 1];
        // simple swap
        int a = ar[index];
        ar[index] = ar[i];
        ar[i] = a;
    }
}

取消混洗复合混洗列表

Un-shuffle a compound shuffled list

java

shuffle