My Math Forum randomly choose 2 or more unique items from a given set

 Computer Science Computer Science Forum

 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 $\sum_{2\leq k\leq n}\binom{n}{k}=2^{n}-n-1$ Now here's my problem: How can I randomly choose a combination in such a way, that all $2^{n}-n-1$ 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 k-combinations in step 2. Anyone know a solution? PS: This is not homework or anything, it's part of a real-life 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 special-case 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:
 Originally Posted by CRGreathouse 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.
Thanks CRGreathouse, I wonder why I didn't think of that...

This solution can also be implemented quite efficiently.
If n is small enough (smaller than the bit-size 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:
1. Get a random integer between 1 and $2^n - 1$[/*:m:2pobyd5h]
2. Interpret the integer as a binary number. (Easy... the computer already stores it that way anyways )[/*:m:2pobyd5h]
3. Now the i'th bit from the right determines whether the i'th item is part of the selection (1) or not (0). (Getting a specific bit from a number is a pretty fast operation with common programming languages.)[/*:m:2pobyd5h]
As I said, this of course only works if there are at least n bits available, so with 32-bit integers it works for n smaller or equal to 32.

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:
 Originally Posted by archy2 As I said, this of course only works if there are at least n bits available, so with 32-bit integers it works for n smaller or equal to 32.
If you need more bits, just use several words. For b = 3000, generate 94 32-bit words and mask out or ignore the top 8 bits of the last word.

 Tags choose, items, randomly, set, unique

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Moy510 Advanced Statistics 1 October 14th, 2013 05:14 PM BioScientist Advanced Statistics 1 February 23rd, 2012 05:30 PM ozerdem Algebra 4 February 20th, 2012 11:17 PM erichpowell Advanced Statistics 3 December 29th, 2008 12:44 PM symmetry Advanced Statistics 0 June 20th, 2007 03:56 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top