Java 使用 Collections.shuffle 包含两个元素的随机洗牌列表

Question

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

public class ShuffleList {
  public static void main(String[] args) {
    String [] file = {"1","2"};
    long seed = 3;
    ArrayList<String> fileList = new ArrayList<String>(Arrays.asList(file));
    for (int i=0; i<200; i++) {
      Collections.shuffle(fileList, new Random(seed));
      seed = seed +1;
      System.out.println(seed + "," + fileList);
    }
  }
}

输出是200行[1,2]，根本不是随机洗牌。事实上，对于所有 < 4000 的种子都是如此。这是为什么？我尝试使用 3 个元素的列表，从 1 到 100 的种子使列表看起来随机。但是 2 个元素的列表有什么问题？

Answer 1

问题不在于 shuffle - 它在于 Random 和小种子。这是一个演示的程序：

import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int total = 0;
        for (int seed = 0; seed < 4000; seed++) {
            Random rng = new Random(seed);
            total += rng.nextInt(2);
        }
        System.out.println(total);
    }
}

你期望输出大约 2000 - 大约一半调用 nextInt 应该 return 0，大约一半应该 return 1. 相反，它是 4000 - every call returns 1.

使用种子 [10000, 13999) 你得到 240 - 所以调用 return 0 比 1 多得多。

使用种子 [100000, 103999) 你得到 3226 - 变得更好了......

使用种子 [1000000, 1003999) 你会得到 2105 - 好多了。

我对随机数生成器的数学知识知之甚少，无法说明为什么会发生这种情况，但看起来 java.util.Random 对于小种子来说确实有点问题。

Answer 2

对于两个元素的列表，shuffle 所做的是将一个元素与随机位置交换：

    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    }

这是使用 Random 实例的地方（大小为 2，因此只有一次迭代）：

swap(list, 2-1, rnd.nextInt(2));

所以你所证明的是，对于 3 到 203 之间的种子，第一次调用 rnd.nextInt(2) returns 1. 你是否在所有测试中使用了随机种子或使用相同的 Random 实例，你会得到不同的结果。

例如，将 new Random(seed) 更改为 new Random(3)（实际上创建该实例一次并将其传递给 Collections.shuffle 更有意义）生成：

4,[1, 2]
5,[1, 2]
6,[2, 1]
7,[2, 1]
8,[1, 2]
9,[1, 2]
10,[1, 2]
11,[1, 2]
12,[2, 1]
13,[2, 1]
14,[2, 1]
15,[1, 2]
16,[1, 2]
17,[2, 1]
18,[1, 2]
19,[2, 1]
20,[2, 1]
21,[1, 2]
22,[1, 2]
23,[1, 2]
24,[2, 1]
25,[2, 1]
26,[2, 1]
27,[2, 1]
28,[2, 1]
29,[1, 2]
30,[1, 2]
31,[2, 1]
32,[2, 1]
33,[1, 2]
34,[2, 1]
35,[2, 1]
36,[2, 1]
37,[1, 2]
38,[2, 1]
39,[2, 1]
40,[1, 2]
41,[2, 1]
42,[1, 2]
43,[2, 1]
44,[1, 2]
45,[1, 2]
46,[2, 1]
47,[2, 1]
48,[1, 2]
49,[2, 1]
50,[2, 1]
51,[1, 2]
52,[1, 2]
53,[2, 1]
54,[2, 1]
55,[2, 1]
56,[2, 1]
57,[1, 2]
58,[2, 1]
59,[1, 2]
60,[1, 2]
61,[2, 1]
62,[2, 1]
63,[1, 2]
64,[2, 1]
65,[1, 2]
66,[2, 1]
67,[1, 2]
68,[2, 1]
69,[1, 2]
70,[2, 1]
71,[1, 2]
72,[1, 2]
73,[2, 1]
74,[1, 2]
75,[2, 1]
76,[1, 2]
77,[2, 1]
78,[1, 2]
79,[2, 1]
80,[1, 2]
81,[2, 1]
82,[2, 1]
83,[1, 2]
84,[1, 2]
85,[1, 2]
86,[2, 1]
87,[2, 1]
88,[1, 2]
89,[1, 2]
90,[2, 1]
91,[1, 2]
92,[1, 2]
93,[2, 1]
94,[1, 2]
95,[1, 2]
96,[1, 2]
97,[1, 2]
98,[1, 2]
99,[1, 2]
100,[1, 2]
101,[1, 2]
102,[2, 1]
103,[1, 2]
104,[2, 1]
105,[2, 1]
106,[1, 2]
107,[1, 2]
108,[1, 2]
109,[2, 1]
110,[2, 1]
111,[1, 2]
112,[2, 1]
113,[1, 2]
114,[1, 2]
115,[2, 1]
116,[2, 1]
117,[2, 1]
118,[1, 2]
119,[2, 1]
120,[1, 2]
121,[1, 2]
122,[1, 2]
123,[2, 1]
124,[1, 2]
125,[2, 1]
126,[1, 2]
127,[2, 1]
128,[2, 1]
129,[1, 2]
130,[1, 2]
131,[2, 1]
132,[2, 1]
133,[1, 2]
134,[1, 2]
135,[1, 2]
136,[2, 1]
137,[1, 2]
138,[2, 1]
139,[1, 2]
140,[2, 1]
141,[2, 1]
142,[1, 2]
143,[1, 2]
144,[2, 1]
145,[1, 2]
146,[1, 2]
147,[2, 1]
148,[2, 1]
149,[1, 2]
150,[2, 1]
151,[1, 2]
152,[1, 2]
153,[2, 1]
154,[2, 1]
155,[1, 2]
156,[2, 1]
157,[2, 1]
158,[2, 1]
159,[1, 2]
160,[1, 2]
161,[1, 2]
162,[1, 2]
163,[2, 1]
164,[2, 1]
165,[2, 1]
166,[1, 2]
167,[2, 1]
168,[2, 1]
169,[1, 2]
170,[2, 1]
171,[1, 2]
172,[2, 1]
173,[2, 1]
174,[1, 2]
175,[2, 1]
176,[1, 2]
177,[1, 2]
178,[2, 1]
179,[1, 2]
180,[2, 1]
181,[2, 1]
182,[1, 2]
183,[1, 2]
184,[2, 1]
185,[1, 2]
186,[2, 1]
187,[1, 2]
188,[2, 1]
189,[2, 1]
190,[2, 1]
191,[2, 1]
192,[2, 1]
193,[1, 2]
194,[2, 1]
195,[1, 2]
196,[2, 1]
197,[1, 2]
198,[2, 1]
199,[2, 1]
200,[2, 1]
201,[2, 1]
202,[2, 1]
203,[1, 2]

Answer 3

+1 给乔恩和伊兰。

如果你想让你的代码工作，不要每次循环都实例化Random，在循环之前创建一个实例并传入它。Random被设计成这样使用，而不是有每次调用前种子都会改变。

例如...

public class ShuffleList {
  public static void main(String[] args) {
    String [] file = {"1","2"};
    ArrayList<String> fileList = new ArrayList<String>(Arrays.asList(file));

    Random random = new Random(3);
    for (int i=0; i<200; i++) {
      Collections.shuffle(fileList, random);
      System.out.println(fileList);
    }
  }
}

Java 使用 Collections.shuffle 包含两个元素的随机洗牌列表

Java random shuffle list with two elements using Collections.shuffle

java

random

collections