Фильтрация результатов случайного случайного выбора

Question

Я хочу отфильтровать результаты, полученные с помощью numpy.random.choice. Проблема, которую я хочу решить, не может быть решена путем применения условия сначала с помощью np.where, а затем путем случайного выбора. В общем, я хочу, чтобы какое-то свойство содержалось среди всех случайно выбранных элементов.

Конкретным примером этой проблемы является то, что я хочу выбрать n точек в плоскости наугад, чтобы любая заданная пара точек находилась на расстоянии не менее d друг от друга. Я не уверен, что это можно сделать за полиномиальное время, так как эта проблема выглядит как проблема клики для полной NP.

Если получить необходимое количество баллов невозможно, алгоритм следует повторить, используя меньшее значение d.

Answer 1

Прямой подход состоит в том, чтобы генерировать ваш массив по точкам и проверять, что каждая новая точка соответствует вашему состоянию. Вот как вы могли бы это сделать:

import math
import random

# We define a distance function
def distance(x1, y1, x2, y2):
    return math.sqrt((x2-x1)**2+(y2-1)**2)

# We define a function that checks if a new point respects the distance condition
def distance_respected(points, dist_max, new_x, new_y):
    distance_respected = True
    for point in points:
        if distance(point[0], point[1], new_x, new_y)>dist_max:
            distance_respected = False
    return distance_respected

# In the following example I decided to just consider part of a plane. More precisely
# [-10,10]*[-10,10]

number_of_points = 5
max_distance = 2
points = []
for point in range(number_of_points):
    # random.uniform() generates a random float between our two numbers
    new_x = random.uniform(-10,10)
    new_y = random.uniform(-10,10)
    while not distance_respected(points, max_distance, new_x, new_y):
        new_x = random.uniform(-10,10)
        new_y = random.uniform(-10,10)
    points.append((new_x, new_y))

---

Выход:

[(-3.425486982794177, -5.415726177177236),
 (-4.109629395121301, -0.8693732638893792),
 (-2.2778596980094257, 1.1101779439932162),
 (-3.0579069964130916, 1.2909258679375473),
 (-3.067639560760325, 1.1507562378468599)]

Answer 2

Выборка диска Пуассона хороша для этого. Время выполнения не похоже на NP-complete.

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

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