Заполнение случайных позиций в огромном 2D массиве

Question

Есть ли аккуратный алгоритм, который я могу использовать, чтобы заполнить случайные позиции в огромном двумерном массиве n x n с числом m целых чисел без заполнения занятой позиции? куда , а также

Вроде как этот псевдокод:

int n;
int m;

void init(int new_n, int new_m) {
    n = new_n;
    m = new_m;
}
void create_grid() {
    int grid[n][n];

    int x, y;
    for(x = 1; x <= n; x ++) {
        for(y = 1; y <= n; y ++) {
            grid[x][y] = 0;
        }
    }

    populate_grid(grid);
}

void populate_grid(int grid[][]) {
    int i = 1;
    int x, y;

    while(i <= m) {
        x = get_pos();
        y = get_pos();

        if(grid[x][y] == 0) {
            grid[x][y] = i;
            i ++;
        }
    }
}

int get_pos() {
    return random() % n + 1;
}

... но более эффективно для больших н и м. Особенно, если m больше и больше позиций занято, генерация случайной позиции, которая не занята, займет больше времени.

Answer 1

Если коэффициент заполнения действительно не становится большим, вам не стоит беспокоиться о попадании на занятые позиции.

Предполагая, например, что половина ячеек уже заполнена, у вас есть 50% шансов сначала попасть в заполненную ячейку; и 25%, чтобы поразить два заполненных подряд; 12,5% из трех... В среднем, требуется... две попытки найти пустое место! (В более общем случае, если имеется только доля 1/M свободных клеток, среднее число попыток увеличивается до M.)

Если вы абсолютно не хотите проверять ячейки, вы можете работать, инициализируя массив индексами свободных ячеек. Затем вместо выбора случайной ячейки вы выбираете случайную запись в массиве от 1 до L (длина списка, первоначально N²).

После выбора записи вы устанавливаете соответствующую ячейку, перемещаете последний элемент в списке в случайную позицию и устанавливаете L= L-1. Таким образом, список свободных позиций обновляется.

Обратите внимание, что этот процесс, вероятно, менее эффективен, чем слепые попытки.

Answer 2

Чтобы создать псевдослучайные позиции без повторов, вы можете сделать что-то вроде этого:

for (int y=0; y<n; ++y) {
    for(int x=0; x<n; ++x) {
        int u=x,v=y;
        u = (u+hash(v))%n;
        v = (v+hash(u))%n;
        u = (u+hash(v))%n;
        output(u,v);
    }
 }

для правильной работы hash(x) должна быть хорошей псевдослучайной хэш-функцией, которая генерирует положительные числа, которые не переполняются при добавлении числа от 0 до n.

Это версия структуры Фейстеля ( https://en.wikipedia.org/wiki/Feistel_cipher), которая обычно используется для создания криптографических шифров, таких как DES.

Хитрость в том, что каждый шаг похож u = (u+hash(v))%n; обратимый - вы можете получить свой оригинал u вернуться, делая u = (u-hash(v))%n (Я имею в виду, что вы могли бы, если % оператор работал с отрицательными числами так, как всем хотелось бы)

Поскольку вы можете инвертировать операции, чтобы получить оригинал x,y обратно от каждого u,v выход, каждый отдельный x,y ДОЛЖЕН производить u,v,