My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
September 18th, 2011, 06: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 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.
archy2 is offline  
 
September 18th, 2011, 08:43 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
September 20th, 2011, 04:08 AM   #3
Member
 
Joined: Apr 2010

Posts: 65
Thanks: 0

Re: randomly choose 2 or more unique items from a given set

http://en.wikipedia.org/wiki/Reservoir_sampling
Xitami is offline  
September 21st, 2011, 10: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 [/*: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.
archy2 is offline  
September 21st, 2011, 11:17 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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 06:14 PM
Randomly selecting N from N BioScientist Advanced Statistics 1 February 23rd, 2012 06:30 PM
identical balls are thrown randomly into bins ozerdem Algebra 4 February 21st, 2012 12:17 AM
3 computer processors randomly receive n jobs.... erichpowell Advanced Statistics 3 December 29th, 2008 01:44 PM
Randomly Selected People symmetry Advanced Statistics 0 June 20th, 2007 04:56 PM





Copyright © 2019 My Math Forum. All rights reserved.