尋找一種更明智的方法來隨機分割一維值範圍

Question

我需要一種方法將一維值範圍（即連續整數）隨機分割爲k個部分。只需使用僞隨機生成器來選擇分割點就可以在技術上完成工作。但是它允許範圍可能非常小（相反非常大）。我一直在尋找一種通常解決這個問題的方法，而不需要使用硬編碼的範圍限制。我已經找到article。它關心的是2D地形的產生。但它面臨同樣的問題並提出解決方案。你可以看到多邊形部分，作者提到勞埃德放鬆。那整個事情是從Voronoi圖表中得來的，它可以在2d範圍內工作。此外，如果您查看構建Lloyd弛豫所需的Voronoi圖的算法，它將從以下位置開始：

let *（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個範圍。

假設進行排序是（由C程序:)生成後您的15張隨機數

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 Voronoi多邊形應用到1d範圍的文章中所做的。

（請原諒我的任何可能的計算誤差）