寻找一种更智能的方法来随机分割1D范围的值

Question

我需要一种方法来将1维值范围(即连续整数)随机分成k个部分.只需使用伪随机生成器来挑选分裂点,技术上就可以完成工作.然而,它允许范围的可能性非常小(相反非常大).我一直在寻找一种方法来解决这个问题,而不需要采用硬编码范围限制.

我找到了这篇文章.它涉及2d地形生成.但它面临同样的问题并提出了解决方案.你可以看到多边形部分,作者在那里提到劳埃德放松.整个事物的来源是Voronoi图,它适用于2d范围.此外,如果你看一下构建劳埃德放松需要的Voronoi图的算法,它开始于:

令*(z)为变换*(z)=(zx,zy + d(z)),其中d(z)是抛物线,最小值为z

当然,我在1d没有抛物线.

在我的1d范围的情况下,我不清楚如何获得相同的结果.或者可能有一个不同/更好的方法来解决这个问题？

Answer 1

我没有深入了解他的代码细节,但是他在2d中用Voronoi图做了什么,然后选择多边形的中心作为新点并重新制作Voronoi图给了我这个想法:

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

现在让我们看看Voronoi系列的新点如何:

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 Voronoi多边形应用于1d范围的文章中所做的.

(对不起任何可能的计算错误)