{"id":59,"date":"2008-04-13T17:38:23","date_gmt":"2008-04-13T16:38:23","guid":{"rendered":"http:\/\/jimblackler.com\/blog\/?p=59"},"modified":"2008-04-13T17:38:23","modified_gmt":"2008-04-13T16:38:23","slug":"selecting-a-number-of-random-elements-from-a-list-without-repeats-an-implementation-in-java","status":"publish","type":"post","link":"https:\/\/jimblackler.com\/?p=59","title":{"rendered":"Selecting a number of random elements from a list, without repeats. An implementation in Java."},"content":{"rendered":"

A project I’ve been working on required a random selection of postings to be shown to users. The entries were to be drawn from a larger list : a cache of references to posts held in memory.<\/p>\n

My first effort at the selection code simply copied the original list, shuffled it, then selected the first ‘n’ entries (where ‘n’ is the number of required postings). A colleague remarked that this was hardly an optimal use of time or memory. So I decided to write a a general-purpose function to select ‘n’ unique entries from a list of ‘m’ entries – using as little memory and processing time as possible.<\/p>\n

A naive solution<\/h2>\n

The most obvious solution to the problem is to repeatedly draw random entries from 0.. n of the list. To reduce the repeats, keep a record of the indices of the random entries already selected. Then, as each new item is selected, the existing list is checked to see if the entry was already taken.<\/p>\n

The problem with this is that as more entries are selected the likelihood of such a collision increases. The execution time of the function cannot therefore be predicted. In some cases where the number to select was very large this could make the function quite slow. You could speed it by using different containers and such, but a better approach seems to be avoid collisions in the first place.<\/p>\n

Consider a case of selecting five random entries from a list of ten. The first entry index can be found by picking a random number between zero and nine. When making the second selection however there are now only nine remaining unselected entries. So if we pick from zero to eight, then find a way of converting this number (the index of unused entries<\/em>) into a full source table index, we have avoided the possibility of collision altogether.<\/p>\n

The method<\/h2>\n

My solution calls for items chosen using a random number generated between 0 and m-c where ‘c’ is the number of already selected items. This represents the relative index of unchosen<\/em> entries, not the actual entries themselves. This number is then converted into the actual entry index by an algorithm.<\/p>\n

This algorithm involves iterating backwards through the list of already picked random numbers. The principal is at each iteration to convert the index from 0… m-c space to 0 .. 1+m-c space. In other words the space of the previously selected element. One single operation can do this, and at the same time avoid any potential collision with the last drawn entry in its target space. The operation says “if the already selected entry’s unchosen entry index is the same or less than the current index number then increment this index by one.”<\/p>\n

When all already selected entries have been processed in this way, the resulting index is guaranteed to be in 0.. n space and clear of any collisions with already selected entries.<\/p>\n

The method has an order of execution n*m \/ 2, and temporary storage requirements of n indices. This is stable and predictable however so it is a in improvement on collision avoidance methods that would mean repeating random selections.<\/p>\n

Code<\/h2>\n

Here is a ready-to-use implementation in Java.<\/p>\n

\n\n\t\n\t
\n\t\t
  1. import<\/span> java.util.List<\/span>;<\/span><\/div><\/li>\n
  2. import<\/span> java.util.Random<\/span>;<\/span><\/div><\/li>\n
  3. import<\/span> java.util.ArrayList<\/span>;<\/span><\/div><\/li>\n
  4.  <\/div><\/li>\n
  5. public<\/span> class<\/span> ListUtil {<\/span><\/div><\/li>\n
  6.  <\/div><\/li>\n
  7.     \/**<\/span><\/div><\/li>\n
  8.      * Create a new list which contains the specified number of elements from the source list, in a<\/span><\/div><\/li>\n
  9.      * random order but without repetitions.<\/span><\/div><\/li>\n
  10.      *<\/span><\/div><\/li>\n
  11.      * @param sourceList    the list from which to extract the elements.<\/span><\/div><\/li>\n
  12.      * @param itemsToSelect the number of items to select<\/span><\/div><\/li>\n
  13.      * @param random        the random number generator to use<\/span><\/div><\/li>\n
  14.      * @return a new list   containg the randomly selected elements<\/span><\/div><\/li>\n
  15.      *\/<\/span><\/div><\/li>\n
  16.     public<\/span> static<\/span> <<\/span>T><\/span> List<<\/span>T><\/span> chooseRandomly(<\/span>List<<\/span>T><\/span> sourceList, int<\/span> itemsToSelect, Random<\/span> random)<\/span> {<\/span><\/div><\/li>\n
  17.         int<\/span> sourceSize =<\/span> sourceList.size<\/span>(<\/span>)<\/span>;<\/span><\/div><\/li>\n
  18.  <\/div><\/li>\n
  19.         \/\/ Generate an array representing the element to select from 0... number of available<\/span><\/div><\/li>\n
  20.         \/\/ elements after previous elements have been selected.<\/span><\/div><\/li>\n
  21.         int<\/span>[<\/span>]<\/span> selections =<\/span> new<\/span> int<\/span>[<\/span>itemsToSelect]<\/span>;<\/span><\/div><\/li>\n
  22.  <\/div><\/li>\n
  23.         \/\/ Simultaneously use the select indices table to generate the new result array<\/span><\/div><\/li>\n
  24.         ArrayList<<\/span>T><\/span> resultArray =<\/span> new<\/span> ArrayList<<\/span>T><\/span>(<\/span>)<\/span>;<\/span><\/div><\/li>\n
  25.  <\/div><\/li>\n
  26.         for<\/span> (<\/span>int<\/span> count =<\/span> 0<\/span>;<\/span> count <<\/span> itemsToSelect;<\/span> count++<\/span>)<\/span> {<\/span><\/div><\/li>\n
  27.  <\/div><\/li>\n
  28.             \/\/ An element from the elements *not yet chosen* is selected<\/span><\/div><\/li>\n
  29.             int<\/span> selection =<\/span> random.nextInt<\/span>(<\/span>sourceSize -<\/span> count)<\/span>;<\/span><\/div><\/li>\n
  30.             selections&<\/span>#91<\/span>;<\/span>count&<\/span>#93<\/span>;<\/span> =<\/span> selection;<\/span><\/div><\/li>\n
  31.             \/\/ Store original selection in the original range 0.. number of available elements<\/span><\/div><\/li>\n
  32.  <\/div><\/li>\n
  33.             \/\/ This selection is converted into actual array space by iterating through the elements<\/span><\/div><\/li>\n
  34.             \/\/ already chosen.<\/span><\/div><\/li>\n
  35.             for<\/span> (<\/span>int<\/span> scanIdx =<\/span> count -<\/span> 1<\/span>;<\/span> scanIdx >=<\/span> 0<\/span>;<\/span> scanIdx--<\/span>)<\/span> {<\/span><\/div><\/li>\n
  36.                 if<\/span> (<\/span>selection >=<\/span> selections[<\/span>scanIdx]<\/span>)<\/span> {<\/span><\/div><\/li>\n
  37.                     selection++;<\/span><\/div><\/li>\n
  38.                 }<\/span><\/div><\/li>\n
  39.             }<\/span><\/div><\/li>\n
  40.             \/\/ When the first selected element record is reached all selections are in the range<\/span><\/div><\/li>\n
  41.             \/\/ 0.. number of available elements, and free of collisions with previous entries.<\/span><\/div><\/li>\n
  42.  <\/div><\/li>\n
  43.             \/\/ Write the actual array entry to the results<\/span><\/div><\/li>\n
  44.             resultArray.add<\/span>(<\/span>sourceList.get<\/span>(<\/span>selection)<\/span>)<\/span>;<\/span><\/div><\/li>\n
  45.         }<\/span><\/div><\/li>\n
  46.         return<\/span> resultArray;<\/span><\/div><\/li>\n
  47.     }<\/span><\/div><\/li>\n<\/ol>\t<\/div>\n\n<\/div>\n\n","protected":false},"excerpt":{"rendered":"

    A project I’ve been working on required a random selection of postings to be shown to users. The entries were to be drawn from a larger list : a cache of references to posts held in memory. My first effort at the selection code simply copied the original list, shuffled it, then selected the first […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-59","post","type-post","status-publish","format-standard","hentry","category-general-programming"],"_links":{"self":[{"href":"https:\/\/jimblackler.com\/index.php?rest_route=\/wp\/v2\/posts\/59","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jimblackler.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jimblackler.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jimblackler.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/jimblackler.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=59"}],"version-history":[{"count":0,"href":"https:\/\/jimblackler.com\/index.php?rest_route=\/wp\/v2\/posts\/59\/revisions"}],"wp:attachment":[{"href":"https:\/\/jimblackler.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=59"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jimblackler.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=59"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jimblackler.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=59"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}