Creating random numbers with no duplicates

Question

In this case  the MAX is only 5  so I could check the duplicates one by one  but how could I do this in a simpler way  For example  what if the MAX has a value of 20  Thanks   int MAX   5   for  i   1   i  lt   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

User · Answer

Following code create a sequence random number between  1 m  that was not generated before   public class NewClass        public List lt Integer gt  keys   new ArrayList lt Integer gt          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  lt  4  i                  System out println ne rand m                      System out println  list      ne keys

User · Answer

There is a more efficient and less cumbersome solution for integers than a Collections shuffle   The problem is the same as successively picking items from only the un-picked items in a set and setting them in order somewhere else  This is exactly like randomly dealing cards or drawing winning raffle tickets from a hat or bin    This algorithm works for loading any array and achieving a random order at the end of the load  It also works for adding into a List collection  or any other indexed collection  and achieving a random sequence in the collection at the end of the adds    It can be done with a single array  created once  or a numerically ordered collectio  such as a List  in place  For an array  the initial array size needs to be the exact size to contain all the intended values  If you don t know how many values might occur in advance  using a numerically orderred collection  such as an ArrayList or List  where the size is not immutable  will also work  It will work universally for an array of any size up to Integer MAX VALUE which is just over 2 000 000 000  List objects will have the same index limits  Your machine may run out of memory before you get to an array of that size  It may be more efficient to load an array typed to the object types and convert it to some collection  after loading the array  This is especially true if the target collection is not numerically indexed    This algorithm  exactly as written  will create a very even distribution where there are no duplicates  One aspect that is VERY IMPORTANT is that it has to be possible for the insertion of the next item to occur up to the current size   1  Thus  for the second item  it could be possible to store it in location 0 or location 1  For the 20th item  it could be possible to store it in any location  0 through 19  It is just as possible the first item to stay in location 0 as it is for it to end up in any other location  It is just as possible for the next new item to go anywhere  including the next new location    The randomness of the sequence will be as random as the randomness of the random number generator   This algorithm can also be used to load reference types into random locations in an array  Since this works with an array  it can also work with collections  That means you don t have to create the collection and then shuffle it or have it ordered on whatever orders the objects being inserted  The collection need only have the ability to insert an item anywhere in the collection or append it      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  lt  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  amp  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

User · Answer

The most efficient  basic way to have non-repeating random numbers is explained by this pseudo-code   There is no need to have nested loops or hashed lookups      get 5 unique random numbers  possible values 0 - 19     assume desired number of selections  lt  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 lt POOL SIZE  i         mapping i    i     max rand   POOL SIZE-1      start loop searching for maximum value  19   for  i 0  i lt 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 first iteration generated random number 3 to start  from 0 - 19    This would make results 0    mapping 3   i e   the value 3   We d then assign mapping 3  to 19   In the next iteration  the random number was 5  from 0 - 18    This would make results 1    mapping 5   i e   the value 5   We d then assign mapping 5  to 18   Now suppose the next iteration chose 3 again  from 0 - 17    results 2  would be assigned the value of mapping 3   but now  this value is not 3  but 19     This same protection persists for all numbers  even if you got the same number 5 times in a row   E g   if the random number generator gave you 0 five times in a row  the results would be    0  19  18  17  16     You would never get the same number twice

User · Answer

I created a snippet that generates no duplicate random integer  the advantage of this snippet is that you can assign the list of an array to it and generate the random item  too   No duplication random generator class

User · Answer

You could use one of the classes implementing the Set interface  API   and then each number you generate  use Set add   to insert it   If the return value is false  you know the number has already been generated before

User · Answer

Here s how I d do it  import java util ArrayList  import java util Random   public class Test       public static void main String   args            int size   20           ArrayList lt Integer gt  list   new ArrayList lt Integer gt  size           for int i   1  i  lt   size  i                  list add i                      Random rand   new Random            while list size    gt  0                int index   rand nextInt list size                 System out println  Selected    list remove index                        As the esteemed Mr Skeet has pointed out  If n is the number of randomly selected numbers you wish to choose and N is the total sample space of numbers available for selection      If n  lt  lt  N  you should just store the numbers that you have picked and check a list to see if the number selected is in it  If n    N  you should probably use my method  by populating a list containing the entire sample space and then removing numbers from it as you select them

User · Answer

The simplest way would be to create a list of the possible numbers  1  20 or whatever  and then shuffle them with Collections shuffle  Then just take however many elements you want  This is great if your range is equal to the number of elements you need in the end  e g  for shuffling a deck of cards    That doesn t work so well if you want  say  10 random elements in the range 1  10 000 - you d end up doing a lot of work unnecessarily  At that point  it s probably better to keep a set of values you ve generated so far  and just keep generating numbers in a loop until the next one isn t already present   if  max  lt  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 lt Integer gt  generated   new LinkedHashSet lt Integer gt     while  generated size    lt  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 set choice though - I ve very deliberately used LinkedHashSet as it maintains insertion order  which we care about here   Yet another option is to always make progress  by reducing the range each time and compensating for existing values  So for example  suppose you wanted 3 values in the range 0  9  On the first iteration you d generate any number in the range 0  9 - let s say you generate a 4   On the second iteration you d then generate a number in the range 0  8  If the generated number is less than 4  you d keep it as is    otherwise you add one to it  That gets you a result range of 0  9 without 4  Suppose we get 7 that way   On the third iteration you d generate a number in the range 0  7  If the generated number is less than 4  you d keep it as is  If it s 4 or 5  you d add one  If it s 6 or 7  you d add two  That way the result range is 0  9 without 4 or 6

User · Answer

It really all depends on exactly WHAT you need the random generation for  but here s my take   First  create a standalone method for generating the random number  Be sure to allow for limits   public static int newRandom int limit       return generatedRandom nextInt limit        Next  you will want 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 amount of numbers to verify  a simple IF statement will suffice   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 to int2 through int5  as well as making sure that there are no zeroes in the randoms   With these two methods in place  we can do the following       num1   newRandom limit1       num2   newRandom limit1       num3   newRandom limit1       num4   newRandom limit1       num5   newRandom limit1     Followed By           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 verify  then a more complex method will yield better results both in clarity of code and in processing resources   Hope this helps   This site has helped me so much  I felt obliged to at least TRY to help as well

User · Answer

Another approach which allows you to specify how many numbers you want with size and the 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 lt Integer gt  getRandomNonRepeatingIntegers int size  int min          int max        ArrayList lt Integer gt  numbers   new ArrayList lt Integer gt          while  numbers size    lt  size            int random   getRandomInt min  max            if   numbers contains random                 numbers add random                        return numbers      To use it returning 7 numbers between 0 and 25       ArrayList lt Integer gt  list   getRandomNonRepeatingIntegers 7  0  25       for  int i   0  i  lt  list size    i              System out println      list get i

User · Answer

There is another way of doing  random  ordered numbers with LFSR  take a look at    http   en wikipedia org wiki Linear feedback shift register  with this technique you can achieve the ordered random number by index and making sure the values are not duplicated   But these are not TRUE random numbers because the random generation is deterministic   But depending your case you can use this technique reducing the amount of processing on random number generation when using shuffling   Here a LFSR algorithm in java   I took it somewhere I don t remeber    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  lt  M  i                  bits i       1  lt  lt  i   amp  seed   gt  gt  gt  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  lt  M  i                  next     bits i    1   0   lt  lt  i                        allow for zero without allowing for -2 31         if  next  lt  0  next                calculate the last register from all the preceding         bits M    false          for int i   0  i  lt  TAPS length  i                  bits M     bits M - TAPS i                          shift all the registers         for int i   0  i  lt  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    gt   0             public void printBits             System out print bits M    1   0           System out print   - gt              for int i   M - 1  i  gt   0  i--                System out print bits i    1   0                     System out println                public static void main String   args            LFSR rng   new LFSR            Vector lt Short gt  vec   new Vector lt Short gt             for int i   0  i  lt   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

User · Answer

Here is an efficient solution for fast creation of a randomized array  After randomization you can simply pick the n-th element e of the array  increment n and return e  This solution has O 1  for getting a random number and O n  for initialization  but as a tradeoff requires a good amount of memory if n gets large enough

User · Answer

Generating all the indices of a sequence is generally a bad idea  as it might take a lot of time  especially if the ratio of the numbers to be chosen to MAX is low  the complexity becomes dominated by O MAX    This gets worse if the ratio of the numbers to be chosen to MAX approaches one  as then removing the chosen indices from the sequence of all also becomes expensive  we approach O MAX 2 2    But for small numbers  this generally works well and is not particularly error-prone   Filtering the generated indices by using a collection is also a bad idea  as some time is spent in inserting the indices into the sequence  and progress is not guaranteed as the same random number can be drawn several times  but for large enough MAX it is unlikely   This could be close to complexity O k n log 2 n  2   ignoring the duplicates and assuming the collection uses a tree for efficient lookup  but with a significant constant cost k of allocating the tree nodes and possibly having to rebalance    Another option is to generate the random values uniquely from the beginning  guaranteeing progress is being made  That means in the first round  a random index in  0  MAX  is generated   items i0 i1 i2 i3 i4 i5 i6  total 7 items  idx 0                       index 2    In the second round  only  0  MAX - 1  is generated  as one item was 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    The values of the indices then need to be adjusted  if the second index falls in the second half of the sequence  after the first index   it needs to be incremented to account for the gap  We can implement this as a loop  allowing us to select arbitrary number of unique items   For short sequences  this is quite fast O n 2 2  algorithm     void RandomUniqueSequence std  vector lt int gt   amp rand num      const size t n select num  const size t n item num        assert n select num  lt   n item num        rand num clear                  b1  3187 000 msec  the fastest         b2  3734 000 msec     for size t i   0  i  lt  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  lt  i     j                if n   j  lt  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  The n Rand x  returns random integers in  0  x   inclusive   This can be made a bit faster if selecting a lot of items  e g  not 5 but 500  by using binary search to find the insertion point  To do that  we need to make sure that we meet the requirements   We will do binary search with the comparison n   j  lt  rand num j  which is the same as n  lt  rand num j  - j  We need to show that rand num j  - j is still a sorted sequence for a sorted sequence rand num j   This is fortunately easily shown  as the lowest distance between two elements of the original rand num is one  the generated numbers are unique  so there is always difference of at least 1   At the same time  if we subtract the indices j from all the elements rand num j   the differences in index are exactly 1  So in the  worst  case  we get a constant sequence - but never decreasing  The binary search can therefore be used  yielding 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  lt  rand num j  - j  protected      std  vector lt int gt   iterator m p begin it   public      CCompareWithOffset std  vector lt int gt   iterator p begin it           m p begin it p begin it              bool operator    const int  amp r value  TNeedle n  const               size t n index    amp r value -  amp  m p begin it             calculate index in the array          return r value  lt  n n   n index     or r value - n index  lt  n n            bool operator    TNeedle n  const int  amp r value  const               size t n index    amp r value -  amp  m p begin it             calculate index in the array          return n n   n index  lt  r value     or n n  lt  r value - n index            And finally   void RandomUniqueSequence std  vector lt int gt   amp rand num      const size t n select num  const size t n item num        assert n select num  lt   n item num        rand num clear                  b1  3578 000 msec        b2  1703 000 msec  the fastest      for size t i   0  i  lt  n select num     i            int n   n Rand n item num - i - 1              get a random number          std  vector lt int gt   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 have tested this on three benchmarks  First  3 numbers were chosen out of 7 items  and a histogram of the items chosen was accumulated over 10 000 runs   4265 4229 4351 4267 4267 4364 4257   This shows that each of the 7 items was chosen approximately the same number of times  and there is no apparent bias caused by the algorithm  All the sequences were also checked for correctness  uniqueness of contents    The second benchmark involved choosing 7 numbers out of 5000 items  The time of several versions of the algorithm was accumulated over 10 000 000 runs  The results are denoted in comments in the code as b1  The simple version of the algorithm is slightly faster   The third benchmark involved choosing 700 numbers out of 5000 items  The time of several versions of the algorithm was again accumulated  this time over 10 000 runs  The results are denoted in comments in the code as b2  The binary search version of the algorithm is now more than two times faster than the simple one   The second method starts being faster for choosing more than cca 75 items on my machine  note that the complexity of either algorithm does not depend on the number of items  MAX    It is worth mentioning that the above algorithms generate the random numbers in ascending order  But it would be simple to add another array to which the numbers would be saved in the order in which they were generated  and returning that instead  at negligible additional cost O n    It is not necessary to shuffle the output  that would be much slower   Note that the sources are in C    I don t have Java on my machine  but the concept should be clear   EDIT   For amusement  I have also implemented the approach that generates a list with all the indices 0    MAX  chooses them randomly and removes them from the list to guarantee uniqueness  Since I ve chosen quite high MAX  5000   the performance is catastrophic      b1  519515 000 msec    b2  20312 000 msec std  vector lt int gt  all numbers n item num   std  iota all numbers begin    all numbers end    0      generate all the numbers  for size t i   0  i  lt  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 have also implemented the approach with a set  a C   collection   which actually comes second on benchmark b2  being only about 50  slower than the approach with the binary search  That is understandable  as the set uses a binary tree  where the insertion cost is similar to binary search  The only difference is the chance of getting duplicate items  which slows down the progress      b1  20250 000 msec    b2  2296 000 msec std  set lt int gt  numbers  while numbers size    lt  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 is here

User · Answer

There is algorithm of card batch  you create ordered array of numbers  the  card batch   and in every iteration you select a number at random position from it  removing the selected number from the  card batch  of course

User · Answer

This would be a lot simpler in java-8   Stream generate new Random    ints               distinct                limit 16     whatever limit you might need              toArray Integer    new

User · Answer

Instead of doing all this create a LinkedHashSet object and random numbers to it by Math random   function      if any duplicated entry occurs the LinkedHashSet object won t add that number to its List     Since in this Collection Class no duplicate values are allowed    in the end u get a list of random numbers having no duplicated values       D

User · Answer

Your problem seems to reduce to choose k elements at random from a collection of n elements   The Collections shuffle answer is thus correct  but as pointed out inefficient  its O n      Wikipedia  Fisher   Yates shuffle has a O k  version when the array already exists   In your case  there is no array of elements and creating the array of elements could be very expensive  say if max were 10000000 instead of 20     The shuffle algorithm involves initializing an array of size n where every element is equal to its index  picking k random numbers each number in a range with the max one less than the previous range  then swapping elements towards the end of the array     You can do the same operation in O k  time with a hashmap although I admit its kind of a pain   Note that this is only worthwhile if k is much less than n    ie k   lg n  or so   otherwise you should use the shuffle directly     You will use your hashmap as an efficient representation of the backing array in the shuffle algorithm   Any element of the array that is equal to its index need not appear in the map   This allows you to represent an array of size n in constant time  there is no time spent initializing it      Pick k random numbers  the first is in the range 0 to n-1  the second 0 to n-2  the third 0 to n-3 and so on  thru n-k    Treat your random numbers as a set of swaps   The first random index swaps to the final position   The second random index swaps to the second to last position   However  instead of working against a backing array  work against your hashmap   Your hashmap will store every item that is 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  lt  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  lt  k  i                  output i     getValue n-i-1               return output

User · Answer

random numbers are 0 1 2 3  ArrayList lt Integer gt  numbers   new ArrayList lt Integer gt        Random randomGenerator   new Random    while  numbers size    lt  4         int random   randomGenerator  nextInt 4       if   numbers contains random             numbers add random

User · Answer

The most easy way is use nano DateTime as long format  System nanoTime

[java] Creating random numbers with no duplicates

Examples related to java

Examples related to random