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.

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).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.

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), asninteger items are needed to store the object IDs, and the time complexity of the std::random_shuffle function is O(n) as well.