Page 1 of 3
Efficient choosing algorithm
Posted: September 29th, 2013, 3:17 pm
by chewwy
This seems like it should be very easy, but my mind is temporarily drawing a blank...I have some code that in its basic form chooses m (unique) items out of a collection of n items, following the algorithm described in pseudocode below.This algorithm seems very inefficient though, particularly when n is large and/or m is close to n. how could it be done better?FUNCTION CHOOSE(n, m) For i =1 To m TryAgain: Generate random integer x between 1 and n If x Not in AnswerCollection Then AnswerCollection.add x Else GOTO TryAgain End if Next i RETURN AnswerCollectionEND FUNCTION
Efficient choosing algorithm
Posted: September 30th, 2013, 9:35 am
by chewwy
Thanks!
Efficient choosing algorithm
Posted: September 30th, 2013, 12:14 pm
by acastaldo
My favorite was Algorithm S from Section 4.3.2 of Knuth, but I have to admit Floyd's algorithm looks even more clever. Thanks for mentioning it!
Efficient choosing algorithm
Posted: October 2nd, 2013, 9:29 am
by Cuchulainn
QuoteOriginally posted by: acastaldoMy favorite was Algorithm S from Section 4.3.2 of Knuth, but I have to admit Floyd's algorithm looks even more clever. Thanks for mentioning it!Do you mean Knuth 3.4.2?STL C++ has the random_shuffle() algorithm.
Efficient choosing algorithm
Posted: October 2nd, 2013, 11:55 am
by acastaldo
Terribly sorry, I meant Knuth 3.4.2 Algorithm S
Efficient choosing algorithm
Posted: October 2nd, 2013, 11:58 am
by Cuchulainn
QuoteOriginally posted by: acastaldoTerribly sorry, I meant Knuth 3.4.2 Algorithm SThanks for the link. Knuth's book just came to life for me.
Efficient choosing algorithm
Posted: October 5th, 2013, 9:15 am
by Cuchulainn
QuoteOriginally posted by: outrun [..] I love these 3 line algorithms!These are by definition recursive?
Efficient choosing algorithm
Posted: October 5th, 2013, 1:55 pm
by Cuchulainn
Same as?
Efficient choosing algorithm
Posted: October 5th, 2013, 3:18 pm
by Cuchulainn
QuoteOriginally posted by: outrunYes on a functional level, but I can't look inside those calls. If these are precisely documented, what else do you need to know? O(n) Analogy: in the olde mainframe days you had to pre-estimate:a. the number of operationsb. the number of words in memory.If you know a. and b. for shuffle() then finito, yes?
Efficient choosing algorithm
Posted: October 5th, 2013, 3:48 pm
by Traden4Alpha
QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: outrunYes on a functional level, but I can't look inside those calls. If these are precisely documented, what else do you need to know? O(n) Analogy: in the olde mainframe days you had to pre-estimate:a. the number of operationsb. the number of words in memory.If you know a. and b. for shuffle() then finito, yes?Assuming one trusts the documentation!