创build没有重复的随机数字
在这种情况下，最大只有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; } } 最简单的方法是创build一个可能的数字列表（1..20或其他），然后用Collections.shuffle对其进行洗牌。 然后，只要采取你想要的许多元素。 如果你的范围等于你最终需要的元素的数量（例如洗牌一副牌），这是非常好的。
如果你想要（比如）10个随机元素在1..10,000的范围内，那么效果不好 – 你最终会做很多不必要的工作。 在这一点上，保留一组迄今为止生成的值可能会更好，并且只是在循环中继续生成数字，直到下一个数字还没有出现为止：
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); }
尽pipe如此，请谨慎使用设置选项 – 我非常有意使用LinkedHashSet因为它保持了我们在这里关心的插入顺序。
还有一种select是始终取得进展，每次减less范围并补偿现有的价值。 所以例如，假设你想要0到9范围内的3个值。 在第一次迭代中，您将生成范围为0..9的任意数字 – 假设您生成一个4。
在第二次迭代中，您将生成范围为0..8的数字。 如果生成的数字小于4，则保持原样;否则，添加一个。 这会得到0..9的结果范围，而不是4.假设我们得到7这样。
在第三次迭代中，您将生成范围为0..7的数字。 如果生成的数字小于4，则保持原样。 如果它是4或5，你会添加一个。 如果是6或7，你可以加两个。 这样的结果范围是0..9没有4或6。
这是我该怎么做的
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)); } } }
正如Skeet先生所指出的那样：
如果n是您希望select的随机select的数字的数量， N是可供select的数字的总样本空间：
- 如果n << N ，您应该只存储您select的数字并检查一个列表，看看所选的数字是否在其中。
- 如果n〜 = N ，你可能应该使用我的方法，通过填充一个包含整个样本空间的列表，然后在select它的时候删除数字。
//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); } }
这个伪代码解释了非重复随机数的最有效的基本方法。 不需要嵌套循环或哈希查找：
// 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。
现在假设下一次迭代再次select3（从0到17）。 结果[2]将被分配映射值[3]，但是现在，这个值不是3，而是19。
即使您连续5次获得相同的号码，所有号码仍然保持相同的保护。 例如，如果随机数发生器连续五次给你五次，结果将是：[0,19,18,17,16]。
你永远不会得到相同的号码两次。
生成一个序列的所有索引通常是一个坏主意，因为它可能要花费很多时间，特别是如果要select的数目的比例是低的（复杂性由O(MAX) ）。 如果要select的数字的比率接近1，那么这会变得更糟，因为从所有序列中删除选定的索引也变得昂贵（我们接近O(MAX^2/2) ）。 但对于less数人来说，这一般运作良好，并不是特别容易出错。
通过使用集合来过滤生成的索引也是一个坏主意，因为在将索引插入序列中花费了一些时间，并且不能保证进度，因为可以多次绘制相同的随机数（但是对于足够大的MAX ，不太可能）。 这可能接近于复杂性
O(kn log^2(n)/2) ，忽略重复项，并假设集合使用树进行高效查找（但是具有分配树节点并且可能不得不重新平衡的显着的恒定成本k ）。
另一个select是从头开始唯一地生成随机值，保证正在取得进展。 这意味着在第一轮中，会生成[0, MAX]的随机索引：
items i0 i1 i2 i3 i4 i5 i6 (total 7 items) idx 0 ^^ (index 2)
在第二轮中，仅生成[0, MAX - 1] （因为已经select了一个项目）：
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)
那么需要调整指数的值：如果第二个指数落在序列的后半部分（第一个指数之后），则需要增加以弥补差距。 我们可以将其实现为一个循环，使我们可以select任意数量的唯一项目。
对于短序列，这是相当快的O(n^2/2)algorithm：
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] （含）中的随机整数。 如果通过使用二进制search来查找插入点来select很多项目（例如，不是5但是500），则可以使其更快一些。 要做到这一点，我们需要确保我们符合要求。
我们将用比较结果n + j < rand_num[j]进行二分法search
n < rand_num[j] - j 。 我们需要certificaterand_num[j] - j仍然是一个sorting序列rand_num[j]的sorting序列。 幸运的是，由于原始rand_num两个元素之间的最小距离是1（所生成的数字是唯一的，所以总是至less有1的差异）。 同时，如果我们从所有元素中减去指数j
rand_num[j] ，索引的差异恰好是1.所以在“最差”的情况下，我们得到一个不变的序列 – 但从来没有减less。 因此可以使用二进制search，产生O(n log(n))algorithm：
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 < nn + n_index; // or r_value - n_index < nn } 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 nn + n_index < r_value; // or nn < 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 }
我已经在三个基准testing了这个。 首先，从7个项目中select3个数字，并且所选项目的直方图累计超过10,000次运行：
4265 4229 4351 4267 4267 4364 4257
这显示7个项目中的每一个被select了近似相同的次数，并且没有由该algorithm引起的明显偏差。 所有的序列也被检查是否正确（内容的唯一性）。
第二个基准涉及从5000个项目中select7个数字。 该algorithm的几个版本的时间累计超过10,000,000次运行。 结果在代码中注释为b1 。 该algorithm的简单版本稍快。
第三个基准涉及从5000个项目中select700个数字。 algorithm的几个版本的时间再次积累，这次超过10,000次运行。 结果在代码中注释为b2 。 algorithm的二进制search版本现在比简单版本快两倍以上。
第二种方法在我的机器上select超过cca 75的项目开始更快（请注意，任一algorithm的复杂性不取决于项目的数量， MAX ）。
值得一提的是，上述algorithm以升序生成随机数。 但是，添加另一个数组可以很简单，按照生成的顺序将这些数字保存起来，然后返回（以可忽略的附加成本O(n) ）。 没有必要洗牌输出：这会慢很多。
请注意，源代码是用C ++编写的，我的机器上没有Java，但概念应该清楚。
编辑 ：
为了娱乐，我还实施了生成所有指标清单的方法
0 .. MAX ，随机select它们并从列表中删除它们以保证唯一性。 由于我select了相当高的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 ++集合）实现了这个方法，这个set在基准b2上实际上仅次于二进制search的方法，速度只有大约50％。 这是可以理解的，因为该set使用二叉树，其中插入成本类似于二分search。 唯一的区别是获得重复项目的机会，这减慢了进度。
// 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
完整的源代码在这里 。
另一种方法可以让你指定你想要的数字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)); }
您可以使用其中一个实现Set接口（ API ）的类，然后使用Set.add（）插入它。
如果返回值为false，则知道该号码之前已经生成。
而不是所有这些创build一个LinkedHashSet对象和随机数Math.random()函数….如果任何重复的条目发生LinkedHashSet对象将不会将该数字添加到其列表…由于在此集合类没有重复的值是允许的..最后你得到一个没有重复值的随机数列表….：D
还有一种方法可以用LFSR来做“随机”的有序号码，看看：
http://en.wikipedia.org/wiki/Linear_feedback_shift_register
使用这种技术，您可以通过索引实现有序的随机数，并确保值不重复。
但是这些并不是真随机数，因为随机生成是确定性的。
但是， 根据您的情况，您可以使用这种技术来减less使用混洗时随机数生成的处理量。
这里是java中的LFSRalgorithm，（我把它放在了我不记得的地方）：
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); } } }
你的问题似乎减less了从n个元素的集合中随机selectk个元素。 Collections.shuffle答案是正确的，但正如低效率指出的那样：O（n）。
Wikipedia：当数组已经存在时， Fisher-Yates shuffle有一个O（k）版本。 在你的情况下，没有元素的数组和创build元素的数组可能是非常昂贵的，如果最大是10000000而不是20。
随机algorithm包括初始化一个大小为n的数组，每个元素等于它的索引，在一个范围内每个数字selectk个随机数，最大值小于前一个范围，然后将元素交换到数组的末尾。
你可以在O（K）时间用HashMap做同样的操作，虽然我承认它是一种痛苦。 请注意，这只有在k比n小得多时才值得。 （即k〜lg（n）左右），否则应该直接使用shuffle。
您将使用hashmap作为shufflealgorithm中backing数组的有效表示。 与其索引相等的任何数组元素都不需要出现在地图中。 这允许您在常量时间内表示一个大小为n的数组，不需要花费时间来初始化它。
-
选取k个随机数：第一个在0到n-1的范围内，第二个从0到n-2，第三个从0到n-3，依此类推。
-
把你的随机数当作一组掉期。 第一个随机指数交换到最后的位置。 第二个随机指数交换倒数第二个位置。 但是，而不是对付支持arrays，对付你的散列表。 你的hashmap将存储每个不在位的项目。
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 = ni-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(ni-1)); } return output; }
有批量卡片的algorithm：您创build有序的数字序列（“卡片批次”），并在每次迭代中从中随机select一个数字（当然从“卡片批次”中删除选定的数字）。
这是快速创build随机数组的有效解决scheme。 随机化后，您可以简单地select数组的第n个元素e ，递增n并返回e 。 这个解决scheme有O（1）获得一个随机数和O（n）初始化，但作为折衷需要大量的内存，如果n足够大。
对于整数，比Collections.shuffle更有效率，更简单。
这个问题是相同的，先后从一组中未挑选的项目中挑选项目，并将其设置在其他地方。 这就像随机发牌或从帽子或垃圾桶抽奖彩票。
此algorithm适用于加载任何数组，并在加载结束时实现随机顺序。 它也适用于添加到List集合（或任何其他索引集合），并在添加结束时在集合中实现随机序列。
它可以用一个单一的数组来创build，或者创build一个数字顺序的集合，比如List。 对于数组，初始数组大小需要是包含所有预期值的确切大小。 如果您不知道有多less值可能会提前发生，那么使用数值有序的集合（如大小不可变的ArrayList或List）也可以工作。 它将普遍适用于Integer.MAX_VALUE大小超过20亿的数组。 列表对象将具有相同的索引限制。 您的计算机可能会耗尽内存，然后再获取该大小的数组。 加载数组后，将数组加载到对象types并将其转换为某个集合可能更有效。 如果目标集合不是按数字索引的，则尤其如此。
这个algorithm与写成一样，将会在没有重复的情况下创build一个非常均匀的分布。 一个非常重要的方面是，必须能够插入下一个项目直到当前尺寸+1。因此，对于第二个项目，可以将其存储在位置0或位置1 。对于第20个项目，可以将其存储在0到19的任何位置。尽可能使第一个项目停留在位置0，因为它最终位于任何其他位置。 下一个新项目就可以到任何地方，包括下一个新的位置。
序列的随机性与随机数发生器的随机性一样随机。
该algorithm也可以用来将参考types加载到数组中的随机位置。 既然这可以和数组一起工作，它也可以用于集合。 这意味着您不必创build集合，然后将其拖动或按照插入对象的任何顺序进行sorting。 集合只需要能够在集合中的任何地方插入项目或追加它。
// 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
我的初步代码，只使用基本面。
这个类给你一个没有重复数字的数组，范围从1到数组的大小。
唯一的外部帮助是生成一个随机数字。
while循环中的条件index == count是棘手的部分，什么使得这个方法的工作。
本质上，它的要求是：随机数不等于数组的元素，但是这个数组元素是下一行的数字吗？
public class Numbers { private int MAX; // the amount of numbers private int count = 0; // counter for the array's elements private int[] nums; // the array for the numbers public Numbers(int x) { MAX = x; // MAX equal to constructor's parameter nums = new int[MAX]; // creates array object while (count < MAX) // call to drawNum() until the array is full drawNum(); } public void drawNum() { int num = (int)(Math.random()*MAX) + 1; // random number, from 1 to MAX int index = 0; // counter for while loop boolean loop = true; // conditional for while loop while (loop) { if (num == nums[index]) // if random number is equal to the array's element, end loop loop = false; if (num != nums[index] && index == count) // index == count! { nums[count] = num; // random number's added to the array, count++; // ++ to the array's counter loop = false; // end loop } index++; // ++ to the while loop counter } } }
这一切都完全取决于你需要什么随机代，但这是我的。
首先，创build一个独立的方法来生成随机数。 一定要考虑到限制。
public static int newRandom(int limit){ return generatedRandom.nextInt(limit); }
接下来，您将需要创build一个比较值的非常简单的决策结构。 这可以通过两种方式之一来完成。 如果你有一个非常有限的数字来validation，一个简单的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; }
上面通过int5比较int1和int2，以及确保random中没有零。
有了这两种方法，我们可以做到以下几点：
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);
如果你有一个更长的列表来validation，那么一个更复杂的方法将在代码的清晰度和处理资源方面产生更好的结果。
希望这可以帮助。 这个网站给了我很大的帮助，我觉得至less应该帮助我。
