Всем привет!
Есть следующая задача. Существует множество объектов, пронумерованных от 1 до n. Необходимо из него выбрать случайный объект такой, который не был выбран ранее (нужно выбрать не более n объектов). Сама задача заключается в том, чтобы сделать это с O(1) памяти и менее, чем за O(n) времени.
То есть, в идеале нужно написать функцию с параметрами вида next_object_id(n, current_id, seed), возвращающую идентификатор следующего ранее не выбранного случайного элемента.
Решаема ли задача с такими требованиями?
Если по этой теме уже есть наработки, дайте, пожалуйста, подсказку, по какому запросу искать.
Может быть я чего-то не понимаю, но нельзя ли выбрать сначала объект с номером 1, потом с номером 2, 3, 4 ...,n.
The following is a simple C++14 implementation using
std::vector< int >andstd::mt19937_64pseudo-random number generator. The code is self-documented, and the time-complexity of the classrandom_object_selection_tconstructor as well as to each call to its member functionnext()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), 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.