0votos

Secuencia aleatoria no repetida en Java

por josejuan hace 2 años

Aunque el enunciado no lo indica explícitamente, se asume distribución uniforme así, el algoritmo que se use debe generar mezclas con probabilidad uniforme. Cambiar dos posiciones (por ejemplo) n veces hace que la probabilidad de que un elemento quede en su posición sea mayor que otras por lo que lo mejor es usar (por ejemplo) el algoritmo de Fisher-Yates. Aquí se comparan los dos algoritmos comentados para ver que uno genera distribución uniforme y el otro no.

Crear una secuencia de números en un rango fijo de manera aleatoria y mostrar en pantalla cada número uno a uno sin repetir.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package com.company; 
 
import java.util.Random; 
import java.util.concurrent.ThreadLocalRandom; 
 
interface Shuffler { 
    void shuffle(int[] v); 
 
public class Main { 
 
    public static Random rnd = ThreadLocalRandom.current(); 
 
    // Implementing Fisher–Yates shuffle 
    static void fisher_yates_shuffle(int[] ar) { 
        for (int i = ar.length - 1; i > 0; i--) { 
            int index = rnd.nextInt(i + 1); 
            int a = ar[index]; 
            ar[index] = ar[i]; 
            ar[i] = a; 
 
    // bad shuffle strategy 
    public static void bad_shuffle(int[] v) { 
        for (int k = 0; k < v.length; k++) { 
            int i = rnd.nextInt(v.length); 
            int j = rnd.nextInt(v.length); 
            int w = v[i]; 
            v[i] = v[j]; 
            v[j] = w; 
 
    // testea la distribución de acumular shuffles m veces 
    public static void ShuffleDistribution(int size, int m, Shuffler s) { 
        int[] v = new int[size]; 
        int[] d = new int[size]; 
 
        for (int k = 0; k < size; k++) { 
            d[k] = 0; 
            v[k] = 0; 
 
        do { 
            // mientras acumulamos reseteamos 
            for (int k = 0; k < size; k++) { 
                d[k] += v[k]; 
                v[k] = k; 
            s.shuffle(v); 
        } while (m-- > 0); 
 
        for (int k = 0; k < d.length; k++) 
            System.out.printf("#%02d: %d\n", k, d[k]); 
 
    public static void main(String[] args) { 
 
        int n = 20, m = 1000000; 
 
        System.out.printf("fisher_yates_shuffle:\n"); 
        ShuffleDistribution(n, m, new Shuffler() { public void shuffle(int[] v) { fisher_yates_shuffle(v); } }); 
 
        System.out.printf("bad_shuffle:\n"); 
        ShuffleDistribution(n, m, new Shuffler() { public void shuffle(int[] v) { bad_shuffle(v); } }); 
 
 
/* 
 
fisher_yates_shuffle: 
#00: 9498948 
#01: 9500577 
#02: 9501327 
#03: 9498415 
#04: 9510876 
#05: 9507738 
#06: 9511011 
#07: 9504376 
#08: 9499390 
#09: 9504850 
#10: 9490978 
#11: 9506886 
#12: 9490189 
#13: 9495498 
#14: 9479832 
#15: 9505690 
#16: 9493285 
#17: 9495034 
#18: 9505486 
#19: 9499614 
 
bad_shuffle: 
#00: 8343261 
#01: 8470347 
#02: 8590195 
#03: 8706221 
#04: 8831814 
#05: 8942141 
#06: 9078936 
#07: 9190357 
#08: 9313471 
#09: 9449448 
#10: 9565537 
#11: 9685035 
#12: 9804996 
#13: 9921286 
#14: 10056275 
#15: 10166415 
#16: 10283855 
#17: 10410255 
#18: 10532843 
#19: 10657312 
 
 */ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.