Случайная выборка несмежных ячеек в пиксельной сетке

Предположим, что у нас есть сетка n*n. Мы хотели бы выбрать k << n случайные ячейки этой сетки, которые не являются смежными. Если мы смоделируем эту сетку с помощью двумерного массива Numpy, содержащего 0 и 1, каков наиболее эффективный способ сделать это в Numpy/Python?

Допустимый Пример:

Введите описание изображения здесь

Недопустимый пример:

Введите описание изображения здесь

2 3
python numpy random-sample

2 ответа:

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

import numpy as np
from scipy.spatial import cKDTree as kdtree

n = 100
k = 50

valid = False

while not valid:
    # generate k grid indices
    coords_flat = np.random.random_integers(0, n ** 2 - 1, size=k)
    coords = np.unravel_index(coords_flat, dims=(n, n))
    # test there are no adjacent cells
    transposed = np.transpose(coords)
    valid = len(kdtree(transposed).query_pairs(1.0)) == 0

print(coords)

Взглянув на результаты: 

import matplotlib.pyplot as plt
grid = np.zeros((n, n), dtype=np.bool)
grid[coords] = True
plt.imshow(grid)
plt.savefig('result.png')

Введите описание изображения здесь

4

Я видел, что это уже принятый ответ, но это была сложная задача, поэтому я решил следующим образом, и мне это нравится, поэтому я дал Ответ на вопрос :): 

import numpy as np

xy = []

x = np.random.randint(0,5)
y = np.random.randint(0,5)

xy.append((x,y))

while True:

    x = np.random.randint(0,5)
    y = np.random.randint(0,5)

    for ii,i in enumerate(xy):    
        if x in [i[0]-1, i[0], i[0]+1]:
            if x == i[0]:
                if y in [i[1]-1, i[1], i[1]+1]:
                    break    
                else:
                    if ii == len(xy) - 1:
                        xy.append((x,y))
                        break
            elif y == i[1]:
                break
        elif ii == len(xy) - 1:
            xy.append((x,y))
            break

    if len(xy) == 3:
        break

for cords in xy:
    print cords

sq =np.zeros((5,5))

for cords in xy:
    sq[cords] = 1

print sq

Вывод: 

(1, 0)
(4, 4)
(4, 1)
[[ 0.  0.  0.  0.  0.]
 [ 1.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.]
 [ 0.  1.  0.  0.  1.]]
Он всегда обеспечивает случайную комбинацию несмежных ячеек. Наслаждайтесь этим! :)
3