python - Random sampling of non-adjacent cells in a pixel grid -

suppose have n*n grid. choose k << n random cells of grid not adjacent. if simulate grid 2d numpy array containing 0 , 1, efficient way in numpy/python?

valid example:

non-valid example:

here's straightforward implementation of rejection sampling. there may faster way adjacency check query_pairs thing (which in case check collisions), since want test if there @ least 1 pair within distance threshold.

import numpy np scipy.spatial import ckdtree 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 no adjacent cells     valid = len(kdtree(coords).query_pairs(1.0)) == 0  print(coords) 

taking @ results:

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