Блог пользователя hari6988

Автор hari6988, 14 лет назад, По-английски
Hi, guys ... This is my first blog ... I am completely new to algorithms ... I have just taken it up and I really love it ... I love searching for puzzles each day and try solving them... right now, i am very bad at it ... I hope to improve ASAP and be good one day ... cheers... A problem for u all so that u dont get bored ;) 

You are given a set S of n numbers. You must pick a subset S' of k numbers from S such that the probability of each element of S occurring in S' is equal (i.e., each is selected with probability k/n). You may make only one pass over the numbers. What if n is unknown?
  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I assume the interface is the following. We repeatedly query the set to get the next element, and when the result (next element) is null, we should yield the subset immediately (i. e. in time O(k)).

Text in white:
If we are still allowed to use O(n) memory, we can use Knuth shuffle to randomly permute the elements of the set as we get them. Whenever we are asked to stop, the answer would be the first k elements of the permutation.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    In white:

    O(k) memory is sufficient -- keep first K elements, and then for i-th element put it into random position with probability k/i, and discard otherwise.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
at ith iteration, take the new one by 1/i probability.