我们可以安全地对Java Collections shuffle(List <？>,Random)方法做出哪些假设？

Question

因此,我正在研究集合shuffle方法,并尝试提出一个列表,列出了运行它时是什么和不确定的.我提出了一些明显的案例如下:

1. 给出的列表将像之前一样在洗牌后包含相同的元素
2. 运行该方法后,该列表可能相同也可能不同(您最终可能会使用相同的元素顺序)
3. 该方法将以线性时间运行(我认为这是正确的但不是100%正面).

此列表是否总结或我是否遗漏了一些可能的案例？

Answer 1

关于会发生什么的官方文档Collections.shuffle有很多话要说.该列表将使用似乎是Fisher-Yates shuffle算法进行混洗,该算法(假设O(1)中的随机访问可用)在时间O(n)和空间O(1)中运行.如果没有随机访问,则实现将使用空间O(n).假设基础随机源是完全无偏的,那么任何特定排序发生的概率都是相等的(也就是说,你得到了可能排列的均匀随机分布).

那么,回答你的问题:

1. 该列表将包含相同的元素.
2. 它们可能处于不同的顺序,但是有1/n!机会比他们在同一个顺序.
3. 运行时为O(n),空间使用量为O(1)或O(n),具体取决于列表是否具有随机访问支持.