-1

只需检查此洗牌算法是否合适。或者可能会有改进？

public static void shuffleArray(Object[] arr, Random rnd){
    int lastIndex = arr.length - 1;
    for (int i=0; i<=lastIndex; i++){
        int k = rnd.nextInt(lastIndex+1);
        Object a = arr[i];
        Object b = arr[k];
        arr[i] = b;
        arr[k] = a;
    }
}
4

3 回答 3

4

您的随机数应在 i..lastIndex+1 范围内而不是 0..lastIndex+1 范围内选择。Google for Fisher-Yates 洗牌以获得解释。

您还可以在交换期间通过直接从一个数组位置复制到另一个位置来保存一个分配，而无需中介：x = arr[i]、arr[i] = arr[k]、arr[k] = x。

于 2013-06-13T13:35:31.923 回答
4

如果你说的是均匀分布，那么不，不是。考虑到对于每次迭代，对于每个可能的配置，您都会以相等的概率生成 N 个可能的下一个配置。最后，你有N ^ N相等的可能性，而只有N!排列，在正常情况下，前者不能除以后者，因此不可能均匀分布。

事实上，我认为 Jeff Attwood 在这里有一个解释：

编码恐怖——天真的危险

于 2013-06-13T13:37:13.483 回答
1

我需要这个来洗牌一个字符数组

您可以像这样为原语调整洗牌代码

public static void shuffle(char[] chars, Random rnd) {
    int size = chars.length;
    for (int i = size; i > 1; i--) {
        int idx = rnd.nextInt(i);
        char tmp = chars[idx];
        chars[idx] = chars[i-1];
        chars[i-1] = tmp;
    }
}

你可以做

Collections.shuffle(Arrays.asList(array), random);

或者你可以看看这段代码。使用一个临时变量并在进行时减小随机变量的大小会稍微更有效。请参阅 Collections.shuffle 了解如何执行此操作。

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {

public static void swap(List<?> list, int i, int j) {
    final List l = list;
    l.set(i, l.set(j, l.get(i)));
}

注意：你正在做(lastIndex+1)，但 lastIndexarr.length - 1真的是这样arr.length

于 2013-06-13T13:30:26.030 回答