Случайное равномерное распределение точек по квадрату (с уловом) - PullRequest
Новая
       25

Случайное равномерное распределение точек по квадрату (с уловом)

2 голосов
/ 19 октября 2011

Итак, проблема равномерного распределения точек решается с помощью некоторых хорошо известных алгоритмов (Хаммерсли, Монте-Карло и т. Д.). Однако моя ситуация немного отличается: допустим, у меня есть набор a значений (2, 8, 1, 5, 4, 7, 3, 6). Эти значения доступны последовательно по индексу (начиная с 2). Если они отображаются на оси x (по схеме доступа, т. Е. В 0 - 2, в 1 - 8), я должен найти соответствующее значение y, такое, что:

  • весь набор точек (рассматриваемые координаты x и y) не последовательность с низким расхождением;
  • любая пара значений x (входной набор) должна иметь соответствующие значения y с максимальным расстоянием между ними;

Результатом является другой набор b со смешанными целыми [1..8] в качестве первого, поэтому каждый кортеж (ai, bi) следует двум приведенным выше правилам.

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

Пример дела

Учитывая входной набор из 4 элементов (3,1,4,2), хорошим набором результатов является (слияние xy): ((3,1), (1,4), (4,2), ( 2,3)) и это хорошо, потому что когда вы получаете доступ к точкам (от 3,1 до конца), с каждой новой точкой вы делаете большой скачок по обеим осям, что является целью с общим равным распределением. Плохой результат для того же входного набора: ((3,1), (1,2), (4,3), (2,4)), так как теперь мы получаем доступ к значениям y последовательно (хотя значения x в порядке) .

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

Спасибо

1 Ответ

0 голосов
/ 07 января 2012

Вы можете использовать стратегию «разделяй и властвуй» для достижения этой цели. По сути, если вы хотите перестановку 1: n, создайте перестановку 1: n / 2 и (n / 2 + 1): n и распределите их случайно.

Вот как вы можете их случайно распределить: 

function permute(x,y):
    L1 = permute(x, (x+y)/2)
    L2 = permute((x+y)/2+1, y)
    spin = randomlyselectfrom(-1,1)
    L = []
    while L1 and L2 are not empty:
        if spin<0:
            L.enqueue(L1.dequeue)
        else:
            L.enqueue(L2.dequeue)
        if random()<0.9:
            spin = -spin
    return L

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

Как только вы получите две случайные последовательности описанным выше способом, поменяйте местами одну из них и объедините их в пару, и вы получите необходимую последовательность пар.

...