Заполнить сетку случайными пикселями

Question

У меня сетка пикселей 64х8. Цель состоит в том, чтобы случайным образом активировать пиксели в этой сетке, пока вся сетка не будет активирована.

Логически я могу генерировать случайные числа в диапазоне 0-63 и 0-7, а затем активировать этот пиксель. Предполагая, что я запускаю это достаточно долго, сетка должна быть полностью активирована.

Однако мне интересно, есть ли какой-нибудь алгоритм, который может минимизировать / избежать всего столкновения (возвращая уже активированную пиксельную координату) и гарантировать полную активацию сетки за конечное время?

Answer 1

Заполните массив длиной 512 числами, увеличивающимися с 0 до 511 (64x8 = 512), поэтому массив будет содержать {0,1,2,3, ..., 511}).

Затем перетасуйте этот массив, например, как описано здесь: Перемешайте массив в C.

Затем определите функцию, которая отображает число в координату, которая будет:

• y = n / 8
• x = n % 8

n, являющийся одним из чисел массива.

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

Answer 2

Вы можете реализовать псевдослучайный генератор ( PRG @ Wikipedia ) с периодом 64 * 8. Использовать 3 бита для оси с 8, а оставшиеся 6 бит для оси с 64.