eins's blog

Problem
By eins, history, 6 years ago, translation, In English

Hello to everybody!

There is the next task. There is a set of objects, numbered from 1 to n. It is necessary to choose from it a random object such that has not been selected before (need to select no more than n objects). The task itself to do this with O(1) memory and less, than O(n) time.

Perfectly, it needed a function with paremeters like next_object_id(n, current_id, seed), that returns id of the next previously unselected random item.

Is the problem solvable with such requirements?

If there are already developments on this topic, please give a hint on which query to search.

  • Vote: I like it
  • -20
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 4   Vote: I like it -8 Vote: I do not like it

The following is a simple C++14 implementation using std::vector< int > and std::mt19937_64 pseudo-random number generator. The code is self-documented, and the time-complexity of the class random_object_selection_t constructor as well as to each call to its member function next() should be O(n).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the answer. But it looks like that solution have more than constant memory consumption and O(n) time complexity per query, that does not satisfy the conditions of the problem.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      With pleasure.

      Please check this update to the suggested solution. The next() member function has been updated to use the vector::pop_back function whose time complexity is constant, and one local variable only is used to store the ID of the selected object. Therefore, the memory and time complexities per query are constant.

      Note that the memory and time complexities of the class constructor are O(n), as n integer items are needed to store the object IDs, and the time complexity of the std::random_shuffle function is O(n) as well.

      → Reply