
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
September 18th, 2011, 05:18 AM  #1 
Newbie Joined: Sep 2011 Posts: 2 Thanks: 0  randomly choose 2 or more unique items from a given set
Hi, here's a mathematical/algorithmic problem I can't seem to solve, maybe someone can help me? Given is a set of n unique items. A computer script is supposed to randomly choose a combination of 2 or more unique items from this set. So the total number of combinations from which the script can choose is Now here's my problem: How can I randomly choose a combination in such a way, that all possible combinations have the same probability of getting chosen? The easiest way to choose a random combination would be: STEP 1) Choose a random number k between 2 and n (using a fair random number generator) STEP 2) Randomly choose k unique items from the base set (this I can do) However, using this algorithm, not all combinations would have the same probability of being chosen, because for different k, there are different numbers of possible kcombinations in step 2. Anyone know a solution? PS: This is not homework or anything, it's part of a reallife computing problem I'm trying to solve. 
September 18th, 2011, 07:43 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: randomly choose 2 or more unique items from a given set
If n < 2, give an error. Otherwise, select each item with a 50% probability. Add up the number of items selected. If it is at least 2, return that collection; otherwise, start over. You may want to specialcase 2, 3, and 4 since they'll take a few attempts otherwise. For n > 9 the chance is about 99% (or better) that the process will take only one step. 
September 20th, 2011, 03:08 AM  #3 
Member Joined: Apr 2010 Posts: 65 Thanks: 0  Re: randomly choose 2 or more unique items from a given set 
September 21st, 2011, 09:49 AM  #4  
Newbie Joined: Sep 2011 Posts: 2 Thanks: 0  Re: randomly choose 2 or more unique items from a given set Quote:
This solution can also be implemented quite efficiently. If n is small enough (smaller than the bitsize of an integer variable), the "select each item with a 50% probability" step can be completed very efficiently with only a single random number needing to be generated, like this:
 
September 21st, 2011, 10:17 AM  #5  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: randomly choose 2 or more unique items from a given set Quote:
 

Tags 
choose, items, randomly, set, unique 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Randomly playing songs probability  Moy510  Advanced Statistics  1  October 14th, 2013 05:14 PM 
Randomly selecting N from N  BioScientist  Advanced Statistics  1  February 23rd, 2012 05:30 PM 
identical balls are thrown randomly into bins  ozerdem  Algebra  4  February 20th, 2012 11:17 PM 
3 computer processors randomly receive n jobs....  erichpowell  Advanced Statistics  3  December 29th, 2008 12:44 PM 
Randomly Selected People  symmetry  Advanced Statistics  0  June 20th, 2007 03:56 PM 