在这种情况下，MAX只有5，所以我可以逐个检查重复，但我怎么能以更简单的方式做到这一点？例如，如果MAX的值为20，该怎么办？谢谢。
int MAX = 5;
for (i = 1 , i <= MAX; i++)
{
drawNum[1] = (int)(Math.random()*MAX)+1;
while (drawNum[2] == drawNum[1])
{
drawNum[2] = (int)(Math.random()*MAX)+1;
}
while ((drawNum[3] == drawNum[1]) || (drawNum[3] == drawNum[2]) )
{
drawNum[3] = (int)(Math.random()*MAX)+1;
}
while ((drawNum[4] == drawNum[1]) || (drawNum[4] == drawNum[2]) || (drawNum[4] == drawNum[3]) )
{
drawNum[4] = (int)(Math.random()*MAX)+1;
}
while ((drawNum[5] == drawNum[1]) ||
(drawNum[5] == drawNum[2]) ||
(drawNum[5] == drawNum[3]) ||
(drawNum[5] == drawNum[4]) )
{
drawNum[5] = (int)(Math.random()*MAX)+1;
}
}
最简单的方法是创建一个可能的数字列表（1..20或其他），然后用Collections.shuffle将它们洗牌。然后只需要你想要的许多元素。如果您的范围等于最终所需的元素数量（例如，用于洗牌一副牌），这是很好的。
如果你想要（比方说）1个10,000范围内的10个随机元素，那么效果不会很好 - 你最终会不必要地做很多工作。此时，保留到目前为止生成的一组值可能更好，并且只是在循环中生成数字，直到下一个尚未存在：
if (max < numbersNeeded)
{
throw new IllegalArgumentException("Can't ask for more numbers than are available");
}
Random rng = new Random(); // Ideally just create one instance globally
// Note: use LinkedHashSet to maintain insertion order
Set<Integer> generated = new LinkedHashSet<Integer>();
while (generated.size() < numbersNeeded)
{
Integer next = rng.nextInt(max) + 1;
// As we're adding to a set, this will automatically do a containment check
generated.add(next);
}
但要小心设置选项 - 我非常谨慎地使用LinkedHashSet，因为它维护了插入顺序，我们在这里关心。
另一种选择是通过每次缩小范围并补偿现有值来始终取得进展。因此，例如，假设您想要0到9范围内的3个值。在第一次迭代中，您将生成0..9范围内的任何数字 - 假设您生成4。
在第二次迭代中，您将生成0..8范围内的数字。如果生成的数字小于4，则按原样保留...否则添加一个。这样你得到的结果范围是0..9没有4.假设我们得到7那样的方式。
在第三次迭代中，您将生成0..7范围内的数字。如果生成的数字小于4，则保持原样。如果它是4或5，你就加一个。如果它是6或7，你将添加两个。这样结果范围是0..9，没有4或6。
你的问题似乎减少了从n个元素的集合中随机选择k个元素。因此，Collections.shuffle答案是正确的，但指出效率低：它的O（n）。
当阵列已经存在时，Wikipedia: Fisher–Yates shuffle有一个O（k）版本。在你的情况下，没有元素数组，创建元素数组可能非常昂贵，比如说max是10000000而不是20。
混洗算法涉及初始化大小为n的数组，其中每个元素等于其索引，在最大值小于前一个范围的范围内选取k个随机数，然后将元素交换到数组的末尾。
您可以在O（k）时间使用hashmap执行相同的操作，尽管我承认它有点痛苦。请注意，如果k远小于n，这是值得的。 （即k~lg（n）左右），否则你应该直接使用shuffle。
您将使用hashmap作为shuffle算法中支持数组的有效表示。数组中与其索引相等的任何元素都不需要出现在地图中。这允许您在恒定时间内表示大小为n的数组，没有时间用于初始化它。
int getValue(i)
{
if (map.contains(i))
return map[i];
return i;
}
void setValue(i, val)
{
if (i == val)
map.remove(i);
else
map[i] = val;
}
int[] chooseK(int n, int k)
{
for (int i = 0; i < k; i++)
{
int randomIndex = nextRandom(0, n - i); //(n - i is exclusive)
int desiredIndex = n-i-1;
int valAtRandom = getValue(randomIndex);
int valAtDesired = getValue(desiredIndex);
setValue(desiredIndex, valAtRandom);
setValue(randomIndex, valAtDesired);
}
int[] output = new int[k];
for (int i = 0; i < k; i++)
{
output[i] = (getValue(n-i-1));
}
return output;
}
这在java-8会更简单：
Stream.generate(new Random()::ints)
.distinct()
.limit(16) // whatever limit you might need
.toArray(Integer[]::new);
有卡批处理的算法：你创建有序的数字数组（“卡批处理”），并在每次迭代中从它随机位置选择一个数字（当然从“卡批处理”中删除所选的数字）。
Here是快速创建随机数组的有效解决方案。随机化后你可以简单地选择数组的n-th元素e，增加n并返回e。该解决方案具有用于获得随机数的O（1）和用于初始化的O（n），但是如果n足够大则作为权衡需要大量存储器。
与Collections.shuffle相比，整数解决方案更有效，更简单。
问题与从一组中未挑选的项目连续挑选项目并按其他地方顺序设置项目相同。这就像随机发牌或从帽子或箱子中抽取胜利的抽奖券。
此算法适用于加载任何数组并在加载结束时实现随机顺序。它还可用于添加到List集合（或任何其他索引集合），并在添加结束时在集合中实现随机序列。
它可以使用单个数组（一次创建）或数字排序的集合（例如List）来完成。对于数组，初始数组大小必须是包含所有预期值的确切大小。如果您不知道可能提前发生了多少个值，那么使用数字顺序集合（例如ArrayList或List，其中大小不是不可变的）也将起作用。它将普遍适用于任何大小的数组，最大为Integer.MAX_VALUE，刚刚超过2,000,000,000。列表对象将具有相同的索引限制。在到达那个大小的数组之前，您的机器可能会耗尽内存。在加载数组后，将类型化的数组加载到对象类型并将其转换为某个集合可能更有效。如果目标集合没有数字索引，则尤其如此。
完全按照书面编写的算法将创建一个非常均匀的分布，其中没有重复。非常重要的一个方面是必须能够插入下一个项目直到当前大小+ 1.因此，对于第二个项目，可以将其存储在位置0或位置1中对于第20项，可以将它存储在任何位置，0到19.尽可能第一项保留在位置0，因为它最终会在任何其他位置。下一个新项目也可以随处去，包括下一个新位置。
序列的随机性将与随机数发生器的随机性一样随机。
此算法还可用于将引用类型加载到数组中的随机位置。由于这适用于数组，因此它也可以用于集合。这意味着您不必创建集合，然后随机播放或按插入对象的任何顺序对其进行排序。集合只需要能够在集合中的任何位置插入项目或附加它。
// RandomSequence.java
import java.util.Random;
public class RandomSequence {
public static void main(String[] args) {
// create an array of the size and type for which
// you want a random sequence
int[] randomSequence = new int[20];
Random randomNumbers = new Random();
for (int i = 0; i < randomSequence.length; i++ ) {
if (i == 0) { // seed first entry in array with item 0
randomSequence[i] = 0;
} else { // for all other items...
// choose a random pointer to the segment of the
// array already containing items
int pointer = randomNumbers.nextInt(i + 1);
randomSequence[i] = randomSequence[pointer];
randomSequence[pointer] = i;
// note that if pointer & i are equal
// the new value will just go into location i and possibly stay there
// this is VERY IMPORTANT to ensure the sequence is really random
// and not biased
} // end if...else
} // end for
for (int number: randomSequence) {
System.out.printf("%2d ", number);
} // end for
} // end main
} // end class RandomSequence
它真的完全取决于你需要随机生成什么，但这是我的看法。
首先，创建一个生成随机数的独立方法。一定要考虑限制。
public static int newRandom(int limit){
return generatedRandom.nextInt(limit); }
接下来，您将需要创建一个非常简单的比较值的决策结构。这可以通过两种方式之一完成。如果您要验证的数字非常有限，那么简单的IF语句就足够了：
public static int testDuplicates(int int1, int int2, int int3, int int4, int int5){
boolean loopFlag = true;
while(loopFlag == true){
if(int1 == int2 || int1 == int3 || int1 == int4 || int1 == int5 || int1 == 0){
int1 = newRandom(75);
loopFlag = true; }
else{
loopFlag = false; }}
return int1; }
上面比较了int1到int2到int5，并确保了randoms中没有零。
有了这两种方法，我们可以做到以下几点：
num1 = newRandom(limit1);
num2 = newRandom(limit1);
num3 = newRandom(limit1);
num4 = newRandom(limit1);
num5 = newRandom(limit1);
其次是：
num1 = testDuplicates(num1, num2, num3, num4, num5);
num2 = testDuplicates(num2, num1, num3, num4, num5);
num3 = testDuplicates(num3, num1, num2, num4, num5);
num4 = testDuplicates(num4, num1, num2, num3, num5);
num5 = testDuplicates(num5, num1, num2, num3, num5);
如果您有更长的列表要验证，那么更复杂的方法将在代码清晰度和处理资源方面产生更好的结果。
希望这可以帮助。这个网站给了我很多帮助，我觉得有必要至少尝试帮助我。
下面的代码创建一个之前未生成的[1，m]之间的序列随机数。
public class NewClass {
public List<Integer> keys = new ArrayList<Integer>();
public int rand(int m) {
int n = (int) (Math.random() * m + 1);
if (!keys.contains(n)) {
keys.add(n);
return n;
} else {
return rand(m);
}
}
public static void main(String[] args) {
int m = 4;
NewClass ne = new NewClass();
for (int i = 0; i < 4; i++) {
System.out.println(ne.rand(m));
}
System.out.println("list: " + ne.keys);
}
}
这是我怎么做的
import java.util.ArrayList;
import java.util.Random;
public class Test {
public static void main(String[] args) {
int size = 20;
ArrayList<Integer> list = new ArrayList<Integer>(size);
for(int i = 1; i <= size; i++) {
list.add(i);
}
Random rand = new Random();
while(list.size() > 0) {
int index = rand.nextInt(list.size());
System.out.println("Selected: "+list.remove(index));
}
}
}
正如受人尊敬的斯基特先生指出的那样： 如果n是您要选择的随机选择数字的数量，N是可供选择的数字的总样本空间：
//random numbers are 0,1,2,3
ArrayList<Integer> numbers = new ArrayList<Integer>();
Random randomGenerator = new Random();
while (numbers.size() < 4) {
int random = randomGenerator .nextInt(4);
if (!numbers.contains(random)) {
numbers.add(random);
}
}
另一种方法，允许您使用size以及返回数字的min和max值指定所需的数量
public static int getRandomInt(int min, int max) {
Random random = new Random();
return random.nextInt((max - min) + 1) + min;
}
public static ArrayList<Integer> getRandomNonRepeatingIntegers(int size, int min,
int max) {
ArrayList<Integer> numbers = new ArrayList<Integer>();
while (numbers.size() < size) {
int random = getRandomInt(min, max);
if (!numbers.contains(random)) {
numbers.add(random);
}
}
return numbers;
}
使用它返回0到25之间的7个数字。
ArrayList<Integer> list = getRandomNonRepeatingIntegers(7, 0, 25);
for (int i = 0; i < list.size(); i++) {
System.out.println("" + list.get(i));
}
还有另一种使用LFSR做“随机”有序数字的方法，看看：
http://en.wikipedia.org/wiki/Linear_feedback_shift_register
使用此技术，您可以按索引实现有序随机数，并确保不重复这些值。
但这些不是真正的随机数，因为随机生成是确定性的。
但根据您的情况，您可以使用此技术减少使用改组时随机数生成的处理量。
这里是java中的LFSR算法，（我把它带到了我不记得的地方）：
public final class LFSR {
private static final int M = 15;
// hard-coded for 15-bits
private static final int[] TAPS = {14, 15};
private final boolean[] bits = new boolean[M + 1];
public LFSR() {
this((int)System.currentTimeMillis());
}
public LFSR(int seed) {
for(int i = 0; i < M; i++) {
bits[i] = (((1 << i) & seed) >>> i) == 1;
}
}
/* generate a random int uniformly on the interval [-2^31 + 1, 2^31 - 1] */
public short nextShort() {
//printBits();
// calculate the integer value from the registers
short next = 0;
for(int i = 0; i < M; i++) {
next |= (bits[i] ? 1 : 0) << i;
}
// allow for zero without allowing for -2^31
if (next < 0) next++;
// calculate the last register from all the preceding
bits[M] = false;
for(int i = 0; i < TAPS.length; i++) {
bits[M] ^= bits[M - TAPS[i]];
}
// shift all the registers
for(int i = 0; i < M; i++) {
bits[i] = bits[i + 1];
}
return next;
}
/** returns random double uniformly over [0, 1) */
public double nextDouble() {
return ((nextShort() / (Integer.MAX_VALUE + 1.0)) + 1.0) / 2.0;
}
/** returns random boolean */
public boolean nextBoolean() {
return nextShort() >= 0;
}
public void printBits() {
System.out.print(bits[M] ? 1 : 0);
System.out.print(" -> ");
for(int i = M - 1; i >= 0; i--) {
System.out.print(bits[i] ? 1 : 0);
}
System.out.println();
}
public static void main(String[] args) {
LFSR rng = new LFSR();
Vector<Short> vec = new Vector<Short>();
for(int i = 0; i <= 32766; i++) {
short next = rng.nextShort();
// just testing/asserting to make
// sure the number doesn't repeat on a given list
if (vec.contains(next))
throw new RuntimeException("Index repeat: " + i);
vec.add(next);
System.out.println(next);
}
}
}
具有非重复随机数的最有效，最基本的方法由该伪代码解释。无需嵌套循环或散列查找：
// get 5 unique random numbers, possible values 0 - 19
// (assume desired number of selections < number of choices)
const int POOL_SIZE = 20;
const int VAL_COUNT = 5;
declare Array mapping[POOL_SIZE];
declare Array results[VAL_COUNT];
declare i int;
declare r int;
declare max_rand int;
// create mapping array
for (i=0; i<POOL_SIZE; i++) {
mapping[i] = i;
}
max_rand = POOL_SIZE-1; // start loop searching for maximum value (19)
for (i=0; i<VAL_COUNT; i++) {
r = Random(0, max_rand); // get random number
results[i] = mapping[r]; // grab number from map array
mapping[r] = max_rand; // place item past range at selected location
max_rand = max_rand - 1; // reduce random scope by 1
}
假设第一次迭代生成随机数3以开始（从0到19）。这将使结果[0] =映射[3]，即值3.然后我们将映射[3]分配给19。
在下一次迭代中，随机数为5（从0到18）。这将使结果[1] =映射[5]，即值5.然后我们将映射[5]分配给18。
现在假设下一次迭代再次选择3（从0到17）。结果[2]将被赋予映射[3]的值，但现在，这个值不是3，而是19。
即使您连续5次获得相同的数字，所有数字仍然保持相同的保护。例如，如果随机数发生器连续五次给你0，结果将是：[0,19,18,17,16]。
你永远不会得到两次相同的数字。
生成序列的所有索引通常是一个坏主意，因为它可能需要花费很多时间，特别是如果要选择的数字与MAX的比率较低（复杂性由O(MAX)主导）。如果要选择的数字与MAX的比率接近1，则会变得更糟，因为从所有序列中移除所选择的指数也变得昂贵（我们接近O(MAX^2/2)）。但对于小数字，这通常效果很好，并不是特别容易出错。
使用集合过滤生成的索引也是一个坏主意，因为花费一些时间将索引插入到序列中，并且无法保证进度，因为可以多次绘制相同的随机数（但是对于足够大的MAX，它是不太可能）。这可能接近复杂性
O(k n log^2(n)/2)，忽略重复项并假设集合使用树进行有效查找（但是使用分配树节点并且可能必须使用k的显着恒定成本rebalance）。
另一种选择是从一开始就唯一地生成随机值，保证正在取得进展。这意味着在第一轮中，生成[0, MAX]中的随机索引：
items i0 i1 i2 i3 i4 i5 i6 (total 7 items)
idx 0 ^^ (index 2)
在第二轮中，仅生成[0, MAX - 1]（已选择一个项目）：
items i0 i1 i3 i4 i5 i6 (total 6 items)
idx 1 ^^ (index 2 out of these 6, but 3 out of the original 7)
然后需要调整指数的值：如果第二个指数落在序列的后半部分（在第一个指数之后），则需要递增以考虑差距。我们可以将其实现为循环，允许我们选择任意数量的唯一项。
对于短序列，这是相当快的O(n^2/2)算法：
void RandomUniqueSequence(std::vector<int> &rand_num,
const size_t n_select_num, const size_t n_item_num)
{
assert(n_select_num <= n_item_num);
rand_num.clear(); // !!
// b1: 3187.000 msec (the fastest)
// b2: 3734.000 msec
for(size_t i = 0; i < n_select_num; ++ i) {
int n = n_Rand(n_item_num - i - 1);
// get a random number
size_t n_where = i;
for(size_t j = 0; j < i; ++ j) {
if(n + j < rand_num[j]) {
n_where = j;
break;
}
}
// see where it should be inserted
rand_num.insert(rand_num.begin() + n_where, 1, n + n_where);
// insert it in the list, maintain a sorted sequence
}
// tier 1 - use comparison with offset instead of increment
}
n_select_num是你的5和n_number_num是你的MAX。 n_Rand(x)返回[0, x]（包括）中的随机整数。如果通过使用二分搜索来找到插入点来选择许多项（例如，不是5而不是500），则可以使这更快一些。为此，我们需要确保满足要求。
我们将使用与n + j < rand_num[j]相同的比较进行二分查找
n < rand_num[j] - j。我们需要证明rand_num[j] - j仍然是排序序列rand_num[j]的排序序列。幸运的是，这很容易显示，因为原始rand_num的两个元素之间的最小距离是1（生成的数字是唯一的，因此总是存在至少1的差异）。同时，如果我们从所有元素中减去指数j
rand_num[j]，指数的差异恰好是1.所以在“最坏”的情况下，我们得到一个恒定的序列 - 但从不减少。因此可以使用二进制搜索，产生O(n log(n))算法：
struct TNeedle { // in the comparison operator we need to make clear which argument is the needle and which is already in the list; we do that using the type system.
int n;
TNeedle(int _n)
:n(_n)
{}
};
class CCompareWithOffset { // custom comparison "n < rand_num[j] - j"
protected:
std::vector<int>::iterator m_p_begin_it;
public:
CCompareWithOffset(std::vector<int>::iterator p_begin_it)
:m_p_begin_it(p_begin_it)
{}
bool operator ()(const int &r_value, TNeedle n) const
{
size_t n_index = &r_value - &*m_p_begin_it;
// calculate index in the array
return r_value < n.n + n_index; // or r_value - n_index < n.n
}
bool operator ()(TNeedle n, const int &r_value) const
{
size_t n_index = &r_value - &*m_p_begin_it;
// calculate index in the array
return n.n + n_index < r_value; // or n.n < r_value - n_index
}
};
最后：
void RandomUniqueSequence(std::vector<int> &rand_num,
const size_t n_select_num, const size_t n_item_num)
{
assert(n_select_num <= n_item_num);
rand_num.clear(); // !!
// b1: 3578.000 msec
// b2: 1703.000 msec (the fastest)
for(size_t i = 0; i < n_select_num; ++ i) {
int n = n_Rand(n_item_num - i - 1);
// get a random number
std::vector<int>::iterator p_where_it = std::upper_bound(rand_num.begin(), rand_num.end(),
TNeedle(n), CCompareWithOffset(rand_num.begin()));
// see where it should be inserted
rand_num.insert(p_where_it, 1, n + p_where_it - rand_num.begin());
// insert it in the list, maintain a sorted sequence
}
// tier 4 - use binary search
}
我在三个基准测试中对此进行了测试。首先，从7个项目中选择3个数字，所选项目的直方图累计超过10,000次：
4265 4229 4351 4267 4267 4364 4257
这表明7个项目中的每一个被选择大致相同的次数，并且没有由算法引起的明显偏差。还检查所有序列的正确性（内容的唯一性）。
第二个基准涉及从5000个项目中选择7个数字。算法的几个版本的时间累计超过10,000,000次运行。结果在代码中的注释中表示为b1。该算法的简单版本稍快一些。
第三个基准涉及从5000个项目中选择700个数字。再次积累了几个版本的算法的时间，这次超过10,000次运行。结果在代码中的注释中表示为b2。该算法的二进制搜索版本现在比简单版本快两倍以上。
第二种方法开始在我的机器上选择超过cca 75项目的速度更快（注意，任一算法的复杂性都不依赖于项目的数量，MAX）。
值得一提的是，上述算法按升序生成随机数。但是添加另一个数组会很简单，数字将按生成顺序保存，然后返回（以可忽略的额外成本O(n)）。没有必要改变输出：这会慢得多。
请注意，源代码是用C ++编写的，我的机器上没有Java，但概念应该很清楚。
编辑：
为了娱乐，我还实现了生成包含所有索引的列表的方法
0 .. MAX，随机选择它们并从列表中删除它们以保证唯一性。由于我选择了相当高的MAX（5000），性能是灾难性的：
// b1: 519515.000 msec
// b2: 20312.000 msec
std::vector<int> all_numbers(n_item_num);
std::iota(all_numbers.begin(), all_numbers.end(), 0);
// generate all the numbers
for(size_t i = 0; i < n_number_num; ++ i) {
assert(all_numbers.size() == n_item_num - i);
int n = n_Rand(n_item_num - i - 1);
// get a random number
rand_num.push_back(all_numbers[n]); // put it in the output list
all_numbers.erase(all_numbers.begin() + n); // erase it from the input
}
// generate random numbers
我还用set（一个C ++集合）实现了这个方法，它实际上在基准b2上排名第二，比二进制搜索的方法慢了大约50％。这是可以理解的，因为set使用二叉树，其中插入成本类似于二进制搜索。唯一的区别是获得重复项目的机会，这会减慢进度。
// b1: 20250.000 msec
// b2: 2296.000 msec
std::set<int> numbers;
while(numbers.size() < n_number_num)
numbers.insert(n_Rand(n_item_num - 1)); // might have duplicates here
// generate unique random numbers
rand_num.resize(numbers.size());
std::copy(numbers.begin(), numbers.end(), rand_num.begin());
// copy the numbers from a set to a vector
完整的源代码是here。
您可以使用其中一个实现Set接口（API）的类，然后使用Set.add（）插入它。
如果返回值为false，则表示之前已生成该数字。
而不是通过LinkedHashSet函数创建一个Math.random()对象和随机数....如果任何重复的条目发生，LinkedHashSet对象将不会将该数字添加到其List ...因为在此Collection类中没有重复的值是允许..最后你得到一个没有重复值的随机数列表....：D