Anonymous user
Talk:One of n lines in a file: Difference between revisions
→Rename?: algorithm S
(→Rename?: Highlight previous comment.) |
(→Rename?: algorithm S) |
||
Line 27:
::''My original reference talked about choosing lines from a file, hence the title. The algorithm may be of use elsewhere (thanks for your suggestion Ledrug), but unless this algorithm has another name by which it is more commonly known, then I would like to leave the name as it is, rather than thinking up a new name that may only be used on RC (rather than RC and StackOverflow :-)''
:--[[User:Paddy3118|Paddy3118]] 04:21, 29 September 2011 (UTC)
:: This is a special case of Knuth's Algorithm S (running backwards though). Note that I'm not suggesting we should rename this task "Alghrithm S", it's not quite the same thing. The reverse Algorithm S is for selecting n items out of N total where N may be unknown, and I'll describe it out of idle interest:
::# Select first n items;
::# For the m-th item where m > n, have a random chance of n/m of keeping it. If failing this chance, go to next item. If not, have it randomly (1/n) replace one of the previously selected n items.
::# Repeat until all N items exhausted.
::It's easy to see that if n = 1, it reduces to current task. --[[User:Ledrug|Ledrug]] 18:54, 20 October 2011 (UTC)
| |||