
#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 listDuring 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,680

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,680





#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,680





#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 