你需要一个Fisher-Yates shuffle.
这是一个非常有效的"选择从m×n个"的解决方案,向你值的子集与零可能性重复的(并且没有不必要的前期排序).执行此操作的伪代码如下:
dim n[N] // gives n[0] through n[N-1]
for each i in 0..N-1:
n[i] = i // initialise them to their indexes
nsize = N // starting pool size
do N times:
i = rnd(nsize) // give a number between 0 and nsize-1
print n[i]
nsize = nsize - 1 // these two lines effectively remove the used number
n[i] = n[nsize]
通过简单地从池中选择一个随机数(基于当前池大小),将其替换为该池中的顶部数字,然后减小池的大小,您可以获得一个shuffle而不必担心大量的交换在前面.
如果数量很高,这很重要,因为它不会引入不必要的启动延迟.
例如,检查以下基准检查,选择10比10:
<------ n[] ------> 0 1 2 3 4 5 6 7 8 9 nsize rnd(nsize) output ------------------- ----- ---------- ------ 0 1 2 3 4 5 6 7 8 9 10 4 4 0 1 2 3 9 5 6 7 8 9 7 7 0 1 2 3 9 5 6 8 8 2 2 0 1 8 3 9 5 6 7 6 6 0 1 8 3 9 5 6 0 0 5 1 8 3 9 5 2 8 5 1 9 3 4 1 1 5 3 9 3 0 5 9 3 2 1 3 9 1 0 9
您可以随时查看游泳池的减少情况,因为您总是将未使用的游泳池替换为未使用的游泳池,因此您永远不会重复游戏.
这是一个小程序,它显示了这个:
import java.util.Random;
public class testprog {
private int[] pool; // The pool of numbers.
private int size; // The current "size".
private Random rnd; // A random number generator.
// Constructor: just initilise the pool.
public testprog (int sz) {
pool = new int[sz];
size = sz;
rnd = new Random();
for (int i = 0; i < size; i++) pool[i] = i;
}
// Get next random number in pool (or -1 if exhausted).
public int next() {
if (size < 1) return -1;
int idx = rnd.nextInt(size--);
int rval = pool[idx];
pool[idx] = pool[size];
return rval;
}
// Test program for the pool.
public static void main(String[] args) {
testprog tp = new testprog (10);
for (int i = 0; i < 11; i++) System.out.println (tp.next());
}
}
输出是(对于一个特定的运行):
3 5 1 0 6 4 9 2 8 7 -1
该-1是那里只是为了告诉你,当你该名单会发生什么.由于您已明确声明您不需要重复项,因此它会返回一个标记值.您还可以选择其他选项,例如抛出异常或只是重新启动池.
你需要一个Fisher-Yates shuffle.
这是一个非常有效的"选择从m×n个"的解决方案,向你值的子集与零可能性重复的(并且没有不必要的前期排序).执行此操作的伪代码如下:
dim n[N] // gives n[0] through n[N-1]
for each i in 0..N-1:
n[i] = i // initialise them to their indexes
nsize = N // starting pool size
do N times:
i = rnd(nsize) // give a number between 0 and nsize-1
print n[i]
nsize = nsize - 1 // these two lines effectively remove the used number
n[i] = n[nsize]
通过简单地从池中选择一个随机数(基于当前池大小),将其替换为该池中的顶部数字,然后减小池的大小,您可以获得一个shuffle而不必担心大量的交换在前面.
如果数量很高,这很重要,因为它不会引入不必要的启动延迟.
例如,检查以下基准检查,选择10比10:
<------ n[] ------> 0 1 2 3 4 5 6 7 8 9 nsize rnd(nsize) output ------------------- ----- ---------- ------ 0 1 2 3 4 5 6 7 8 9 10 4 4 0 1 2 3 9 5 6 7 8 9 7 7 0 1 2 3 9 5 6 8 8 2 2 0 1 8 3 9 5 6 7 6 6 0 1 8 3 9 5 6 0 0 5 1 8 3 9 5 2 8 5 1 9 3 4 1 1 5 3 9 3 0 5 9 3 2 1 3 9 1 0 9
您可以随时查看游泳池的减少情况,因为您总是将未使用的游泳池替换为未使用的游泳池,因此您永远不会重复游戏.
这是一个小程序,它显示了这个:
import java.util.Random;
public class testprog {
private int[] pool; // The pool of numbers.
private int size; // The current "size".
private Random rnd; // A random number generator.
// Constructor: just initilise the pool.
public testprog (int sz) {
pool = new int[sz];
size = sz;
rnd = new Random();
for (int i = 0; i < size; i++) pool[i] = i;
}
// Get next random number in pool (or -1 if exhausted).
public int next() {
if (size < 1) return -1;
int idx = rnd.nextInt(size--);
int rval = pool[idx];
pool[idx] = pool[size];
return rval;
}
// Test program for the pool.
public static void main(String[] args) {
testprog tp = new testprog (10);
for (int i = 0; i < 11; i++) System.out.println (tp.next());
}
}
输出是(对于一个特定的运行):
3 5 1 0 6 4 9 2 8 7 -1
该-1是那里只是为了告诉你,当你该名单会发生什么.由于您已明确声明您不需要重复项,因此它会返回一个标记值.您还可以选择其他选项,例如抛出异常或只是重新启动池.
京公网安备 11010802040832号 | 京ICP备19059560号-6 