两种洗牌方法中哪一种效果更好

Question

我正在尝试随机洗牌列表中的整数集合，我想出了两种洗牌方法来完成这项工作。但是，我不确定哪个效果更好？大家有什么意见或建议吗？

public class TheCollectionInterface {
    public static <E> void swap(List<E> list1, int i, int j) {
        E temp = list1.get(i);
        list1.set(i, list1.get(j));
        list1.set(j, temp);
    }
// Alternative version:    
//    public static void shuffling(List<?> list, Random rnd){
//        for(int i = list.size(); i >= 1; i--){
//            swap(list, i - 1, rnd.nextInt(i));
//        }
//    }

    public static <E> void shuffling(List<E> list1, Random rnd) {
        for (int i = list1.size(); i >= 1; i--){
            swap(list1, i - 1, rnd.nextInt(list1.size()));
        }
    }
    public static void main(String[] args) {
        List<Integer> li2 = Arrays.asList(1,2,3,4,5,6,7,8,9);
        Random r1 = new Random();
        TheCollectionInterface.shuffling(li2, r1);
        System.out.println(li2);
    }
}

Answer 1

如果每个可能的结果可能性相等，则通常认为洗牌算法是好的。洗牌算法的"替代版本"被称为费舍尔-耶茨算法。给定足够好的随机性来源，该算法可以证明以相等的概率生成输入的每个可能排列。JDK Collections.shuffle()方法使用此算法。

未注释的算法在理论上较差，这很容易证明。为什么会这样，这在维基百科关于费舍尔-耶茨洗牌的文章中给出了解释。引用那篇文章，（为清楚起见进行了编辑）

实现费舍尔-耶茨洗牌时的一个常见错误是从错误的范围内选择随机数。有缺陷的算法可能看起来工作正常，但它不会以相等的概率产生每个可能的排列。总是在每次迭代时从整个有效数组索引范围中选择 j，会产生一个有偏差的结果，尽管不那么明显。这可以从以下事实中看出：这样做会产生n^n不同的交换序列，而 n 元素数组只有n!可能的排列。因为n^n永远不能被n!整除当n > 2（因为后者可以被n−1整除，它与n)没有素因数，一些置换必须由更多的交换n^n序列产生。

在此上下文中，j 是与元素i - 1交换的目标槽。似乎将当前元素与 0 和 list.size() 之间的全部元素交换会提供更好的洗牌，因为它似乎可以进行"更多"洗牌。事实上，与Fisher-Yates相比，还有更多不同的可能序列，但是额外的序列增加了偏差，降低了随机播放的质量。

维基百科的文章有关于为什么会这样的详细信息，它显示了洗牌 3 元素数组的每个结果的概率。

这很容易证明。取一个 3 元素数组或列表并对其进行洗牌，例如一百万次，并计算可能的六种排列中每一种的出现频率。我和Fisher-Yates一起做了这件事，结果都在±0.3%以内。在全范围洗牌中，其中三种排列发生的频率比其他三种排列高出约 20%。

您标记为"替代版本"的费舍尔-耶茨洗牌算法显然是更好的方法。

Answer 2

您是否考虑过在集合中随机播放的内置方法？

http://www.tutorialspoint.com/java/util/collections_shuffle.htm

还是自己写有特定的目的？