Генерация / размещение k случайных элементов в 2d массиве

Question

У меня есть 2d массив, матрица вида (mxn). Мне нужно сгенерировать '1' в k ячейках, но вероятность его должна быть равной для каждой ячейки .

, например, если k = 3, мы выбираем случайным образом , где разместить 3 '1:

[0, 0, 0, 0]

[0, 1, 1, 0]

[1, 0, 0, 0]

Сначала я занялся этим, сгенерировав Random из модуля m * n (строки * столбцы). Но это означает, что теоретически мы могли бы добраться до конца матрицы, не генерируя ни одного '1'.

Затем я прочитал о Yates Shuffle , но не был уверен, что это мудро и даже выполнимо реализовать это с помощью этого.

Как эффективный способ реализовать это?

Answer 1

По сути, это проблема «выборки без замены»: из mn ячеек выберите k из них без замены. Есть много подходов к этой проблеме, в зависимости от того, насколько велико mn по отношению к k . Если mn относительно мало, тогда хорошо подойдет тасовка Фишера-Йейтса; составьте список ячеек, перетасуйте их, затем возьмите первые k ячейки, чтобы установить 1.

Для получения дополнительной информации см. мои разделы о выборке без замены и перетасовки . (Часть моего комментария перенесена сюда :) Различные алгоритмы выборки имеют разные компромиссы с точки зрения времени и пространства. Например, тасование Фишера-Йейтса имеет временную и пространственную сложность O (mn), в то время как частичное тасование может иметь временную сложность O (k).