Create random numbers without duplicates

Question

In this case, MAX is only 5, so I can check for duplicates one by one, but how could I make it easier? For example, what if MAX has a value of 20? Thank.

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

Answer 1

The easiest way is to create a list of possible numbers (1..20 or something else) and then shuffle them using Collections.shuffle . Then just take whatever you want. This is great if your range is equal to the number of elements you need at the end (for example, to shuffle a deck of cards).

This does not work so well if you want (say) 10 random elements in the range of 1.10,000 - you end up doing a lot of work unnecessarily. At this point, it is probably best to keep the set of values ​​that you have created so far, and just keep generating numbers in the loop until the next one is present:

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

Be careful with the selection of the kit, though - I used the LinkedHashSet very deliberately, as it maintains the insertion order that we care about here.

Another option is to always make progress by reducing the range each time and compensating for existing values. For example, suppose you need 3 values ​​in the range 0..9. At the first iteration, you should generate any number in the range 0..9 - let's say you create 4.

In the second iteration, you should generate a number in the range 0..8. If the generated number is less than 4, you save it as it is ... otherwise you add it to it. This gives you a range of results from 0..9 without 4. Suppose we get 7.

In the third iteration, you should generate a number in the range 0..7. If the generated number is less than 4, you save it as is. If it's 4 or 5, you must add one. If it is 6 or 7, you would add two. Thus, the range of results is 0..9 without 4 or 6.

Answer 2

Here is how I would do it

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

As dear Mr. Skeet pointed out:
If n is the number of randomly selected numbers that you want to select, and N is the total sample space of the numbers available for selection:

• If n <N, you should simply save the numbers you have selected and check the list to see if the number is in it.
• If n ~ = N, you should probably use my method by filling out a list containing the entire sample space, and then remove the numbers from it as you select them.

Answer 3

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

Answer 4

There is another way to do “random” ordered numbers with LFSR, take a look at:

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

Using this technique, you can get an ordered random number by index and make sure that the values ​​are not duplicated.

But these are NOT TRUE random numbers, because random generation is deterministic.

But depending on your case, you can use this method, reducing the amount of processing when generating random numbers when using shuffling.

Here is the LFSR algorithm in java, (I took it somewhere, I don’t remember):

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

Answer 5

Another approach that allows you to specify how many numbers you want with the size and min and max values ​​of the returned numbers

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

To use it, returning 7 numbers from 0 to 25.

  ArrayList<Integer> list = getRandomNonRepeatingIntegers(7, 0, 25); for (int i = 0; i < list.size(); i++) { System.out.println("" + list.get(i)); } 

Answer 6

The most efficient, basic way to have non-repeating random numbers is explained by this pseudo-code. No need for nested loops or hashed queries:

 // 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 } 

Suppose that the first iteration generated a random number 3 (starting from 0 - 19). This would give the results [0] = mapping [3], ie The value is 3. Then we assigned the map [3] to 19.

In the next iteration, the random number was 5 (from 0 to 18). This would give the results [1] = mapping [5], ie The value is 5. Then we assigned the map [5] to 18.

Now suppose the next iteration again selects 3 (from 0 to 17). the results of [2] are assigned the value of the mapping [3], but now this value is not equal to 3, but 19.

The same protection is maintained for all numbers, even if you received the same number 5 times in a row. For example, if a random number generator gave you 0 five times in a row, the results would be: [0, 19, 18, 17, 16].

You will never get the same number twice.

Answer 7

Generating all sequence indices is usually a bad idea, as this can take a lot of time, especially if the ratio of the numbers to be selected to MAX is small ( O(MAX) prevails in complexity). This gets worse if the ratio of the number to be selected to MAX approaches one, since then removing the selected indices from the sequence of all also becomes expensive (we approach O(MAX^2/2) ). But for small numbers, this usually works well and is not particularly error prone.

Filtering the generated indexes using the collection is also a bad idea, as it takes some time to insert the indexes in the sequence, and progress is not guaranteed, because the same random number can be drawn several times (but for large enough MAX it is unlikely). This may be close to O(kn log^2(n)/2) complexity, ignoring duplicates and assuming that the collection uses the tree to efficiently search (but with a significant constant cost k select tree nodes and, possibly, to balance ).

Another option is to generate random values ​​uniquely from the start, guaranteeing progress. This means that in the first round a random index is generated at [0, MAX] :

 items i0 i1 i2 i3 i4 i5 i6 (total 7 items) idx 0 ^^ (index 2) 

In the second round, only [0, MAX - 1] generated (since one element is already selected):

 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) 

Then the index values ​​need to be adjusted: if the second index falls into the second half of the sequence (after the first index), it must be increased to take into account the gap. We can implement this as a loop, allowing us to choose an arbitrary number of unique elements.

For short sequences, this is a pretty fast O(n^2/2) 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 } 

Where n_select_num is your 5 and n_number_num is your MAX . n_Rand(x) returns random integers in [0, x] (inclusive). This can be done a little faster if you select a lot of elements (for example, not 5, but 500), using binary search to find the insertion point. To do this, we need to make sure that we meet the requirements.

We will perform a binary search by comparing n + j < rand_num[j] , which is the same as n < rand_num[j] - j . We need to show that rand_num[j] - j is still an ordered sequence for the ordered sequence rand_num[j] . This, fortunately, is easily shown, since the smallest distance between two elements of the original rand_num is equal to one (the generated numbers are unique, so there is always a difference of at least 1). At the same time, if we subtract the indices j from all the elements of rand_num[j] , the differences in the index are equal to 1. Thus, in the “worst” case, we get a constant sequence, but never decrease. Therefore, you can use the binary search, leading to the 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 } }; 

And finally:

 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 } 

I tested it on three criteria. Firstly, 3 numbers were selected from 7 points, and a histogram of selected items was accumulated over 10,000 runs:

 4265 4229 4351 4267 4267 4364 4257 

This shows that each of the 7 elements was selected approximately the same number of times, and there is no explicit bias caused by the algorithm. All sequences were also checked for correctness (uniqueness of the content).

The second test included the selection of 7 numbers from 5000 items. The execution time of several versions of the algorithm was accumulated over 10,000,000 runs. Results are indicated in the comments in the code as b1 . A simple version of the algorithm is a little faster.

In the third standard, 700 numbers from 5000 objects took part. The time of several versions of the algorithm has accumulated again, this time over 10,000 starts. Results are indicated in the comments in the code as b2 . The binary version of the algorithm search is now more than twice as fast as the simple one.

The second method starts faster to select more than 75 positions on my machine (note that the complexity of any algorithm does not depend on the number of elements, MAX ).

It is worth noting that the above algorithms generate random numbers in ascending order. But it would be simple to add another array to which the numbers will be stored in the order in which they were generated, and will be returned instead (at a slight additional cost O(n) ). No need to shuffle the conclusion: it will be much slower.

Please note that the sources are in C ++, I do not have Java on my machine, but the concept should be clear.

EDIT

For fun, I also implemented an approach that generates a list with all 0 .. MAX indices, selects them randomly and removes them from the list to guarantee uniqueness. Since I chose a fairly high MAX (5000), performance is disastrous:

 // 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 

I also implemented the set approach (C ++ collection), which ranks second in the b2 test, which is about 50% slower than the binary search approach. This is understandable, since set uses a binary tree, where the insertion cost is similar to a binary search. The only difference is the chance to get duplicate items, which slows down progress.

 // 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 

Full source code here .

Answer 8

This would be much simpler in java-8 :

 Stream.generate(new Random()::ints) .distinct() .limit(16) // whatever limit you might need .toArray(Integer[]::new); 

Answer 9

You can use one of the classes that implement the Set interface ( API ), and then each number you create, use Set.add () to insert it.

If the return value is false, you know that the number has already been created before.

Answer 10

Instead of doing all this, create a LinkedHashSet object and random numbers for it with the Math.random() function .... if any duplicate entry occurs, the LinkedHashSet object LinkedHashSet not add this number to its list ... Since in this class collection duplicate values ​​are not allowed. At the end you will get a list of random numbers that do not have duplicate values ​​....: D

Answer 11

It seems your problem comes down to choosing k elements randomly from a set of n elements. So the Collections.shuffle query is correct, but as indicated, is inefficient: its O (n).

Wikipedia: Fisher-Yates shuffle has version O (k) when an array already exists. In your case, there is no array of elements, and creating an array of elements can be very expensive, say if max was 10,000,000 instead of 20.

The shuffle algorithm includes initializing an array of size n, where each element is equal to its index, selecting k random numbers each number in the range with a maximum smaller than the previous range, then replacing the elements with the end of the array,

You can do the same operation at O ​​(k) time using hashmap, although I acknowledge its kind of pain. Note that this is worth it if k is much less than n. (i.e. k ~ lg (n) or so), otherwise you should use shuffle directly.

You use your hashmap as an efficient representation of the support array in the shuffle algorithm. Any element of the array that is equal to its index should not appear on the map. This allows you to represent an array of size n in constant time, there is no time taken to initialize it.

• Choose k random numbers: the first is in the range from 0 to n-1, the second is from 0 to n-2, the third is from 0 to n-3, etc., through nk.

• Treat your random numbers as a set of swaps. The first random index goes to the end position. The second random index will swap to the second and last position. However, instead of working with an array of support, work against your hashmap. Your hash file will save all positions that are out of position.

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

Answer 12

There is a packet card algorithm: you create an ordered array of numbers (a “card packet”), and at each iteration you select a number from a random position (excluding the selected number from the “card lot”, of course).

Answer 13

Here is an effective solution for quickly creating a randomized array. After randomization, you can simply select the n element e for the array, increment n and return e . This solution has O (1) for getting a random number and O (n) for initializing, but since the trade-off requires a good amount of memory if n gets big enough.

Answer 14

There is a more efficient and less cumbersome solution for integers than Collections.shuffle.

The problem is the same as sequentially selecting items from only selected items in a set and setting them up elsewhere. This is just like randomly handling cards or drawing a lottery won from a hat or bin.

This algorithm works to load any array and achieve random order at the end of the load. It also works to add to the collection List (or any other indexed collection) and achieve a random sequence in the collection at the end of the additions.

This can be done using a single array created once, or a numerically ordered collection, such as a List, in place. , . , , , 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 

Answer 15

, , .

. .

 public static int newRandom(int limit){ return generatedRandom.nextInt(limit); } 

Next, you need to create a very simple decision structure that compares values. This can be done in one of two ways. If you have a very limited number of numbers to check, a simple IF statement is enough:

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

The above compares int1 with int2 through int5, and also ensures that randoms have no zeros.

Using these two methods, we can do the following:

  num1 = newRandom(limit1); num2 = newRandom(limit1); num3 = newRandom(limit1); num4 = newRandom(limit1); num5 = newRandom(limit1); 

Further:

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

If you have a longer list to check, then a more complex method will give better results both in code clarity and in resource processing.

Hope this helps. This site helped me a lot, I felt obligated to at least TRY to help.