В поисках более разумного способа случайного разделения одномерного диапазона значений

Question

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

Я нашел эту статью . Это касается 2-го поколения местности. Но он сталкивается с той же проблемой и представляет решение. Вы можете увидеть раздел «Полигоны», где автор упоминает релаксацию Ллойда. То, из чего все это вытекает, это диаграммы Вороного, и оно работает с двумерными диапазонами. Кроме того, если вы посмотрите на алгоритм построения диаграммы Вороного, в котором нуждается релаксация Ллойда, он начинается с:

пусть * (z) - преобразование * (z) = (zx, zy + d (z)), где d (z) - парабола с минимумом при z

Естественно, у меня нет парабол в 1d.

Мне не ясно, как добиться таких же результатов в моем случае 1d диапазона. Или, может быть, есть другой / лучший подход к проблеме?

Answer 1

Я не стал вдаваться в детали его кода, но то, что он сделал с диаграммами Вороного в 2d, затем выбрав центр многоугольников в качестве новых точек и переделав диаграммы Вороного, дает мне такую ​​идею:

1. Randomly select your points
2. Compute midways between your points
    -> The two midways on the two sides of each point, is like
       its Voronoi polygon in the Voronoi diagram
    -> So let's call the range between these two "midways" a Voronoi range!
3. Replace each point by the center of its Voronoi range
4. If you want the values to be less random, loop back to step 2
5. The ranges you are looking for are the Voronoi ranges of the last results.

Давайте рассмотрим это на примере.Для простоты предположим, что мы работаем с непрерывными диапазонами.

Итак, вы начинаете с диапазона [0, 80] и хотите разделить его на 15 диапазонов.

Допустим, ваши 15 случайных чиселпосле сортировки (генерируются программой на C:)

1 5 12 17 19 21 26 31 38 47 52 54 56 67 71

Средние точки:

1   5   12   17   19   21   26   31   38   47   52   54   56   67   71
  ^   ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^
  |   |    |    |    |    |    |    |    |    |    |    |    |    |
  3  8.5 14.5  18   20  23.5 28.5 34.5 42.5 49.5  51   55  61.5  69

Таким образом, ваши диапазоны становятся:

[0, 3], [3, 8.5], [8.5, 14.5], [14.5, 18], [18, 20], 
[20, 23.5], [23.5, 28.5], [28.5, 34.5], [34.5, 42.5], [42.5, 49.5],
[49.5, 51], [51, 55], [55, 61.5], [61.5, 69], [69, 80]

Если выхочу визуализировать это, это выглядит так (как я лучше могу показать это в тексте):

+..+.....+.....+..+.+...+....+.....+.......+......++...+......+......+.........+

Где . показывает числа от 0 до 80 и + показывают края диапазонов Вороного.

Теперь давайте применим шаг 3.

1   5   12   17   19   21   26   31   38   47   52   54   56   67   71
  ^   ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^    ^
  |   |    |    |    |    |    |    |    |    |    |    |    |    |
0 3  8.5 14.5  18   20  23.5 28.5 34.5 42.5 49.5  51   55  61.5  69 80
 ^  ^   ^     ^   ^    ^    ^    ^    ^    ^    ^    ^    ^     ^  ^
 |  |   |     |   |    |    |    |    |    |    |    |    |     |  |
1.5 | 11.5  16.25 19 21.75 26  31.5 38.5  46  50.25 53  58.25 65.25|
   5.75                                                          74.5

Итак, давайте теперь посмотрим, как выглядят диапазоны Вороного с новыми точками:

1.5  5.75 11.5  16.25  19  21.75 26  31.5 38.5  46  50.25 53  58.25 65.25 74.5
   ^     ^    ^       ^   ^     ^   ^    ^    ^    ^     ^    ^    ^     ^
   |     |    |       |   |     |   |    |    |    |     |    |    |     |
 3.625 8.625 13.875 17.625|  23.875 |   35  42.25 48.125 | 55.625 61.75 69.875
                        20.375    28.75               51.625

Теперь вашдиапазоны (это начинает выглядеть уродливо, но терпите меня)

[0, 3.625], [3.625, 8.625], [8.625, 13.875],
[13.875, 17.625], [17.625, 20.375], [20.375, 23.875],
[23.875, 28.75], [28.75, 35], [35, 42.25],
[42.25, 48.125], [48.125, 51.625], [51.625, 55.625],
[55.625, 61.75], [61.75, 69.875], [69.875, 80]

Итак, теперь давайте посмотрим, как выглядит это распределение точек:

+...+....+....+...+..+..+....+.....+.......+....+...+...+.....+.......+........+

Теперь давайте сравнимдва дистрибутива:

First one 
  |
  V
+..+.....+.....+..+.+...+....+.....+.......+......++...+......+......+.........+
+...+....+....+...+..+..+....+.....+.......+....+...+...+.....+.......+........+
  ^
  |
Second one

выглядит лучше, не так ли?Именно это он и сделал в статье, которую вы нашли с 2d полигонами Вороного, примененными к 1d диапазонам.

(Простите за любые возможные ошибки в вычислениях)