Предположим, что вы хотите перебирать последовательность [0 по n] в случайном порядке, посещая каждый элемент ровно один раз. Есть ли способ сделать это в O (1) памяти, то есть без создания последовательности [1..n] с std::iota и запускать ее через std::random_shuffle?
Какой-то итератор, выплевывающий последовательность в случайном порядке, был бы оптимальным.
Требование состоит в том, чтобы можно было получить другой случайный порядок, выбрав другое семя.
В теории, если вы построили генератор случайных чисел, период которого был ровно n, и покрыл все значения в 0..n, то выполнение этого один раз даст вам то, что вам нравится.
Конечно, это может быть не общее решение, по крайней мере, если вы ищете что-то динамическое, так как вам придется предварительно создать PRNG, и как вы это сделаете, это зависит от n.
Если вы можете изменить последовательность на месте, вы можете просто нарисовать случайное число из 0-N, а затем удалить элемент, который вы посетили, или поменять его до конца или на такие схемы.
Ну... подумай об этом на секунду. Как бы вы "знали", какие элементы были посещены раньше?
Короткий ответ: вы не можете. ( Изменить. Ну, если вы не считаете псевдослучайные генераторы без состояния, но, как вы заявили себя в команде, это не представляется возможным для общего случая)
В зависимости от фактической последовательности, однако, возможно, что возможно "отметить" элементы как посещенные _in-place _, тем самым технически требуя хранения O (n), но без дополнительной памяти для алгоритма
Пример:
const int VISITED_BIT = 0x8000; // arbitrary example
bool extract(int i) { return (i & ~VISITED_BIT); }
bool visited(int i) { return (i & VISITED_BIT); }
bool markvisited(int& i) { i |= VISITED_BIT); }
int main()
{
std::vector<int> v = {2,3,4,5,6};
int remain = v.size();
while (remain>0)
{
size_t idx = rand(); // or something
if (visited(v[idx]))
continue;
std::cout << "processing item #" << idx << ": " << extract(v[idx]) << "\n";
markvisited(v[idx]);
remain--;
}
}
Как и в случае с большинством алгоритмических проблем, существует компромисс между временным пространством; это можно решить в O (1) пространстве, если вы с удовольствием используете O (n ^ 2) время для создания всех перестановок. Помимо пары временных переменных, единственное требуемое хранилище - это семя случайного числа (или, в данном случае, объект PRNG), поскольку этого достаточно для восстановления последовательности псевдослучайных чисел.
Обратите внимание, что вы должны дать этой функции тот же PRNG для каждого вызова, и вы не можете использовать его для каких-либо других целей.
#include <random>
template<typename PRNG, typename INT>
INT random_permutation_element(INT k, INT n, PRNG prng) {
typedef std::uniform_int_distribution<INT> dis;
INT i = 0;
for (; i < k; ++i) dis(0, i)(prng);
INT result = dis(0, i)(prng);
for (++i; i < n; ++i) if (dis(0, i)(prng) <= result) ++result;
return result;
}
Вот быстрая и грязная упряжь. ./test 1000 3 генерирует 1000 полных перестановок длины три; ./test 10 1000000 0 5 генерирует первые пять элементов каждой из 10 перестановок длиной один миллион.
#include <iostream>
int main(int argc, char** argv) {
std::random_device rd;
std::mt19937 seed_gen(rd());
int count = std::stoi(argv[1]);
int size = std::stoi(argv[2]);
int seglow = 0;
int seglim = size;
if (argc > 3) seglow = std::stoi(argv[3]);
if (argc > 4) seglim = std::stoi(argv[4]);
while (count-- > 0) {
std::mt19937 prng(seed_gen());
for (int i = seglow; i < seglim; ++i)
std::cout << random_permutation_element(i, size, prng)
<< (i < seglim - 1 ? ' ' : '\n');
}
return 0;
}
Существует более быстрый способ сделать это, если вы вряд ли закончите какую-либо перестановку, но этот способ написания выглядит лучше, и, возможно, легче понять. (Другой способ состоит в том, чтобы сгенерировать числа в обратном порядке, что означает, что вы можете остановиться после того, как вы сгенерировали k из них, но вам нужно сделать это дважды, сначала получить результат, а затем отрегулировать его.)
Нет, нет, подумайте об этом, где-то программа должна помнить места, которые она посетила. Если есть итератор, который может случайно получить к ним доступ, внутренним итераторам придется это отслеживать, и вы все равно будете использовать память.
Я только что построил структуру для такого рода вещей - я генерирую структуру кучи (мин или максимум, не имеет значения). Но для сравнения, вместо использования значения ключа, я использую случайное число. Элементы, вставленные в кучу, помещаются в случайном порядке. Затем вы можете либо вернуть массив, который формирует базовую структуру кучи (которая будет произвольно упорядочена), либо вы можете вытаскивать элементы один за другим и возвращать их в случайном порядке. Если этот тип вашего контейнера используется в качестве основного хранилища (вместо того, чтобы иметь отдельный массив из кучи), нет дополнительной сложности памяти, так как это просто массив. Сложность времени - O (log N) для вставки, O (log N) для высказывания верхнего элемента. Перетасовка так же просто, как всплытие и повторное вставку каждого элемента O (N log N).
Я даже создал причудливый Enumerator (это С#, но вы можете сделать то же самое с С++ Iterator), который автоматически перетасовывается после того, как вы выполнили итерацию до конца. Это означает, что каждый раз, когда вы можете перебирать список (без всплывающих) несколько раз и каждый раз получать разные порядки за счет перетасовки O (N log N) после каждой полной итерации. (Подумайте, как колода карт. После того, как каждая карта переместилась в кучу сбрасывания, вы перетасовываете колоду, чтобы в следующий раз не получить их в том же порядке.)