Elenco casuale shuffle Java con due elementi utilizzando 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); 
    } 
    } 
} 

L'output è di 200 righe di [1,2], non casuale casuale shuffle. In realtà questo è vero per tutti i semi < 4000. Perché è così? Ho provato con un elenco di 3 elementi e semi da 1 a 100 rendono la lista apparentemente casuale. Ma cosa c'è di sbagliato in una lista di 2 elementi?

Answer 1

Il problema non è con shuffle - è con Random con semi piccoli. Ecco un programma che dimostra che:

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

Faresti aspettano una produzione di circa 2000 - circa le chiamate mezzo a nextInt dovrebbe restituire 0, e circa la metà dovrebbe restituire 1. Invece, è 4.000-ogni chiamata restituisce 1.

usando i semi [10000, 13999) si ottiene 240 - in modo molto più delle chiamate restituiscono 0 rispetto a 1.

usando i semi [100000, 103999) si ottiene 3226 - ottenere un po 'meglio ..

Utilizzando i semi [1000000, 1003999) ottieni 2105 - molto meglio.

Non conosco abbastanza bene la matematica degli RNG per dire perché questo accade, ma sembra che java.util.Random sia un po 'rotto per i piccoli semi.

Answer 2

Per un elenco di due elementi, ciò riordino fa è sostituire un elemento con una posizione casuale:

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

Qui l'istanza casuale viene utilizzato (formato è 2, quindi c'è solo un'iterazione):

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

Quindi tutto quello che dimostrato è che per i semi tra 3 e 203, la prima chiamata a rnd.nextInt(2) rendimenti 1. Had si è utilizzato un seme casuale o utilizzato la stessa istanza a caso in tutti i test, si otterrebbe un risultato diverso.

Ad esempio, cambiando new Random(seed) a new Random(3) (in realtà avrebbe più senso per creare l'istanza volta e passarlo al Collections.shuffle) genera:

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 per Jon e Eran.

Se si desidera far funzionare il proprio codice, non istanziare Casuale ogni volta attraverso il ciclo, creare un'istanza prima del ciclo e passarlo. Random è progettato per essere utilizzato in questo modo e per non avere il seme cambiato prima di ogni chiamata.

Per esempio ...

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