Случайная последовательность итераций в O (1) памяти?

Если бы вы могли изменить последовательность на месте, вы могли бы просто многократно нарисовать случайное число от 0 до N, а затем стереть элемент, который вы посетили, или поменять его местами до конца, или такие схемы.

Ну … подумай на секунду. Как бы вы «узнали», какие элементы посещались раньше?

Краткий ответ: вы не можете. (редактировать Ну, если только вы не учитываете псевдослучайные генераторы без состояния, но, как вы заявили в команде, это не представляется возможным в общем случае)

В зависимости от фактической последовательности, однако, возможно пометить элементы как посетил _на месте_ таким образом, технически требуя хранения 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 из них, но вам придется сделать это дважды, сначала для получения результата, а затем для его корректировки.)

Нет, не думайте об этом, где-то программа должна помнить места, которые она посетила. Если существует итератор, который может произвольно обращаться к ним всем, внутренним компонентам итераторов придется каким-то образом отслеживать это, и вы все равно будете использовать память.

Я только что построил структуру для такого рода вещей — я генерирую структуру Heap (min или max, не имеет значения). Но для сравнения вместо значения ключа я использую случайное число. Элементы, вставленные в кучу, размещаются в случайном порядке. Затем вы можете либо вернуть массив, который формирует базовую структуру кучи (которая будет случайным образом упорядочена), либо вы можете вытолкнуть элементы один за другим и вернуть их в случайном порядке. Если этот тип вашего контейнера используется в качестве основного хранилища (вместо массива, отдельного от кучи), дополнительная сложность памяти не возникает, так как в любом случае это просто массив. Временная сложность составляет O (log N) для вставки, O (log N) для выталкивания верхнего элемента. Перемешивание так же просто, как вставка и вставка каждого элемента, O (N log N).

Я даже создал модный Enumerator (это C #, но вы можете сделать то же самое с итератором C ++), который автоматически перемешивает после того, как вы прошли до конца. Это означает, что каждый раз, когда вы можете выполнять итерацию по списку (без прерывания) несколько раз и каждый раз получать новый порядок, за счет перетасовки O (N log N) после каждой полной итерации. (Думайте как колода карт. После того, как каждая карта ушла в колоду сброса, вы перетасовываете колоду, чтобы в следующий раз не получить их в том же порядке.)