mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-03-19, 13:51   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13·491 Posts
Default Basic optimisation question

What's an efficient way to choose samples uniformly at random from the set of, say, 'sets of N different integers less than M' ? I'd prefer not to use N^2 time (pick an element, check that it's different from all the ones picked to date) or M memory (flag each integer as not-picked-yet).

This seems to be a fairly key component of all the puzzles
fivemack is offline   Reply With Quote
Old 2008-03-19, 14:18   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22·5·307 Posts
Default

Quote:
Originally Posted by fivemack View Post
What's an efficient way to choose samples uniformly at random from the set of, say, 'sets of N different integers less than M' ? I'd prefer not to use N^2 time (pick an element, check that it's different from all the ones picked to date) or M memory (flag each integer as not-picked-yet).

This seems to be a fairly key component of all the puzzles
Isn't this kind of like the card dealing algorithm.

1. Select a card at random from the pack.
2. Remove that card from the pack.
3. Repeat 1 & 2 until you have the required number of cards.

If you use something like a linked list you can remove each element in constant time, but finding the selected the element is linear time.

If you don't mind breaking your "flag each integer as not-picked-yet" criteria, you can use a bitmap for the flags if memory is a concern, but may require multiple tries of random numbers until you 'hit' an unselected element.
retina is offline   Reply With Quote
Old 2008-03-19, 16:13   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101011011012 Posts
Default

Quote:
Originally Posted by fivemack View Post
I'd prefer not to use N^2 time (pick an element, check that it's different from all the ones picked to date)
Does this have to be N^2?

How about:

pick all the elements (O(N))
sort (N log N)
remove X duplicates (O(N))
N = X
repeat until X = 0

X is probably much less than N every iteration, so I think the overall complexity is closer to N log N than N^2
bsquared is offline   Reply With Quote
Old 2008-03-19, 16:22   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by fivemack View Post
What's an efficient way to choose samples uniformly at random from the set of, say, 'sets of N different integers less than M' ? I'd prefer not to use N^2 time (pick an element, check that it's different from all the ones picked to date) or M memory (flag each integer as not-picked-yet).

This seems to be a fairly key component of all the puzzles
Checking that an element has not yet been selected is not 'uniformly
at random' because your event space is not constant.

What you seem to be looking for is a shuffling algorithm. Knuth Vol I
has examples.
R.D. Silverman is offline   Reply With Quote
Old 2008-04-06, 07:24   #5
robo_mojo
 
robo_mojo's Avatar
 
Mar 2008

25 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
What you seem to be looking for is a shuffling algorithm.
Shuffling the set only makes sense if M is small. If M is 1,000,000,000, for example, that approach wouldn't be practical, especially if N is very small.
robo_mojo is offline   Reply With Quote
Old 2008-04-06, 07:51   #6
drew
 
drew's Avatar
 
Jun 2005

38210 Posts
Default

Quote:
Originally Posted by fivemack View Post
What's an efficient way to choose samples uniformly at random from the set of, say, 'sets of N different integers less than M' ? I'd prefer not to use N^2 time (pick an element, check that it's different from all the ones picked to date) or M memory (flag each integer as not-picked-yet).

This seems to be a fairly key component of all the puzzles
I don't believe shuffling algorithms are appropriate, as most assume M=N and operate in an M-sized memory space. And I don't think you care about the order of the N-sized set, right?

I think the 'pick and check' approach you described is appropriate, but the 'check' step doesn't need to have N complexity...it can be constant complexity.

A hash table would be my choice for N much smaller than M. You can create a hash function ( mod N, for instance) that is roughly N-sized, your collisions would be fairly infrequent. Your worst case performance would still be N^2, but it's extremely unlikely. Typically, it will have order 'N' complexity. By choosing random integers, you've implicitly optimized against any clustering problems.

A common coding technique is to use a bit-mask as an efficient modulus operator if your table length is a power of 2. For instance, if your hash table has 64 elements, and your selection is 'n', then your key = n & 0x3f. For your table length, pick the next power of 2 greater than 2N, then you can use open addressing in an array to effectively handle collisions.

Drew

Last fiddled with by drew on 2008-04-06 at 08:17
drew is offline   Reply With Quote
Old 2008-04-08, 13:50   #7
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

I think the appropriate algorithm depends on the relative size of M/N.

"sparse" case:
If M is very large (i.e. N/M small), it is best to use random values add them to a set (implemented as sorted list ignoring duplicates) until the set has desired cardinality.

"dense" case:
If N is very large (comparable to M) then eventually you will need O(M) memory (not bytes or worse int's, but at least bits) anyway. Here I'd suggest to chose random values in 1..M to set (or delete, if N>M/2) bits in a bitmap, if {1..M } is too large to shuffle and take the first N values.

I wonder whether there coud be an approach using a random generator directly creating M-bit numbers (and doing something efficient to get such a random number having N bits),
maybe "or"-ing if there are not enough and some intelligent thing to clear a few bits if there are too many bits set)

Last fiddled with by m_f_h on 2008-04-08 at 14:01
m_f_h is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Question regarding basic routines being used in Yafu. storflyt32 YAFU 2 2015-06-29 23:25
basic question for assignment wong8888 Information & Answers 5 2015-03-22 12:15
A basic math question iconized Prime Sierpinski Project 2 2012-02-03 00:01
Very basic question about Wiedemann methods fivemack Math 0 2008-06-16 10:57
Basic Question about ECM factoring? drake2 Math 1 2006-01-12 07:40

All times are UTC. The time now is 11:54.

Tue May 11 11:54:38 UTC 2021 up 33 days, 6:35, 1 user, load averages: 2.36, 2.32, 2.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.