Register to reply 
Pick k (assume k < n) items from the list 
Share this thread: 
#1
Nov2610, 08:27 PM

P: 22

I have a list of n items. My goal is to pick k (assume k < n) items from the list such that each one of them as probability 1/n of being chosen. Would it be possible to accomplish this without knowing n, in one reading?
thanks 


#2
Nov2610, 10:47 PM

P: 115

Besides: Are you picking a subset from a set? Set from a list? List from a set? List from a list? I think there is a difference. 


#3
Nov2610, 11:04 PM

P: 22

Let's say there is a file composed of n lines. I do not know the number of lines in advance. I wish to pick k random lines from the file, with one read only (without storing the lines in memory and then doing the rest)...



#4
Nov2610, 11:19 PM

P: 115

Pick k (assume k < n) items from the list
During your one pass through, process the ith line if i is an element in L, skip the rest. Obviously you will not be able to read k lines if the actual value of n > m. But this is the best I can think of. 


#5
Nov2610, 11:35 PM

Sci Advisor
HW Helper
P: 3,684

I assume you mean k/n, not 1/n.



#6
Nov2610, 11:46 PM

P: 115




#7
Nov2610, 11:48 PM

Sci Advisor
HW Helper
P: 3,684




#8
Nov2710, 12:05 AM

P: 115

However this k<n assumption is still pretty suspicious. How can one claim not to know n yet make the claim that k<n? 


#9
Nov2710, 12:59 AM

Sci Advisor
HW Helper
P: 3,684




#10
Nov2710, 02:45 AM

P: 115




Register to reply 
Related Discussions  
Array shuffling in fortran  Programming & Computer Science  1  
More Staff Shuffling  Forum Feedback & Announcements  36 