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

Thanks!

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!

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.

Terribly sorry, I meant Knuth 3.4.2 Algorithm S

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.

QuoteOriginally posted by: outrun [..] I love these 3 line algorithms!These are by definition recursive?

Same as?

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?

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!