以排序順序生成隨機數

-1

我想按排序順序生成隨機數。我寫以下代碼：以排序順序生成隨機數

void CreateSortedNode(pNode head) 
{ 
    int size = 10, last = 0; 
    pNode temp; 
    while(size-- > 0) { 
     temp = (pnode)malloc(sizeof(struct node)); 
     last += (rand()%10); 
     temp->data = last;//randomly generate number in sorted order 
     list_add(temp); 
    } 
}

[編輯：] 期待數量將增加生成或減少的順序：即{2,5，9，23，45，68}

int main() 
{ 
int size = 10, last = 0; 
     while(size-- > 0) { 
      last += (rand()%10); 
      printf("%4d",last); 
     } 
return 0; 
}

有什麼更好的想法

來源

2014-10-20 iDebD_gh

不會拋出'malloc（）'的返回，並且您知道這不是完全隨機的，您將下一個數字限制在最後一個的'+ 10'內。 – Haris 2014-10-20 13:57:45

「按排序順序生成隨機數」是什麼意思？你期望輸出什麼？ – interjay 2014-10-20 13:59:18

首先生成隨機數然後對其進行排序。隨機意味着隨機:) – user1336087 2014-10-20 13:59:34

假設你想使他們在有序x <= y <= z產生只有三個隨機數，x，y和z。你會把它們放在一些C++容器中，我將其表示爲D = [x, y, z]這樣的列表，所以我們也可以說x是D的組件0或D_0等等。

對於任何順序算法，它先獲得一個隨機值x，比方說，談到了2.5，那麼這告訴我們什麼y必須，也就是說，y >= 2.5一些信息。

因此，有條件的值爲x，您所需的隨機數算法必須滿足p(y >= x | x) = 1的屬性。如果你正在繪製的分佈類似於普通分佈，如統一分佈或高斯分佈，那麼很明顯看到通常p(y >= x)將是涉及該分佈的密度的其他表達式。（事實上，只有一種病態的分佈就像一個狄拉克在「無限」可能是獨立的，並會爲您的應用廢話。）

所以，我們可以很有信心地推測是p(y >= t | x)爲t各種值不等於p(y >= t)。這是依賴於隨機變量的定義。所以現在你知道隨機變量y（最終列表中的第二個）在統計上不獨立於x。

陳述它的另一種方式是，在您的輸出數據D中，D的組件不是統計獨立的觀測值。事實上，他們必須是正相關的，因爲如果我們知道x比我們想象的大，我們也會自動得知y大於或等於我們的想法。

從這個意義上說，提供這種輸出的順序算法就是馬爾可夫鏈的一個例子。序列中給定數字的概率分佈有條件地依賴於前一個數字。

如果你真的想要一個這樣的馬爾可夫鏈（我懷疑你沒有），那麼你可以隨機抽取第一個數字（對於x），然後繪製積極的變化量，你將添加到每個連續的號，這樣的：

畫出x的值，比方說2.5
畫出y-x嚴格爲正的值，即13.7，所以y是2.5 + 13.7 = 16.2
畫出嚴格爲正值z-y，比如說0。001，所以z是16.201
等等...

你必須承認你的結果的成分在統計上不獨立的，所以你不能在依賴於統計的應用程序中使用它們獨立性假設。

來源

2014-10-20 14:21:02 ely

這聽起來很合理，但它不正確，除非你相信沒有樣本包含統計獨立的值。否則，我可以使用算法：「選擇一個樣本，然後對它進行排序並按順序呈現」，您的論點會突然應用於排序後的樣本;如果它不適用於預先排序的樣本，那將非常奇怪。無論如何，生成一個無偏的有序樣本並不困難;要做到這一點很困難。 – rici 2014-10-21 03:39:35

它不適用於獨立的隨機變量，它們是值列表的組成部分，它們是獨立的。它會*在你排序後應用*，因爲那麼你將值的*集合*看作* *隨機變量。 OP的問題不清楚。你想從一堆獨立的東西中抽取樣本，然後按順序呈現它們（但不要將那些有序列表本身看作是隨機事物的一個實現）？或者，你是否想將矢量作爲一個隨機事物來處理，其分佈部分由這個排序屬性定義？他們是不同的東西！ – ely 2014-10-21 04:06:01

這是這裏的巫師時刻，我的眼睛不準備繼續這個有趣的討論。你可以閱讀我的答案（和鏈接的論文），看看你是否相信它提供了一個獨立的樣本。 – rici 2014-10-21 04:35:05

沒有任何有關樣本量或樣本宇宙的信息，要知道以下內容是否有趣但無關緊要或者解決方案並不容易，但是由於它在任何情況下都很有趣，所以這裏就是了。

問題：

在O(1)空間，產生一個無偏從有序有序大小n的隨機樣本集大小N的S：<S₁,S₂,…S_N>，使得樣品中的元素以相同的順序如有序集合中的元素。

解決方案是：

以概率n/|S|，執行以下操作：
- 添加S₁至樣品。
- 遞減n
從S
重複步驟1和2，用S新的第一元件（和大小），直到n每個時間爲0，刪除S₁在該點樣本將具有所需數量的元素。

該解決方案在python：

from random import randrange 

# select n random integers in order from range(N) 
def sample(n, N): 
    # insist that 0 <= n <= N 
    for i in range(N): 
    if randrange(N - i) < n: 
     yield i 
     n -= 1 
     if n <= 0: 
     break

與解決方案的問題：

這需要O(N)時間。我們真的很樂意接受O(n)時間，因爲n很可能比N小得多。另一方面，我們想保留O(1)的空間，以防n也相當大。

更好的解決方案（輪廓只）

（傑弗裏·斯科特·維瑟，「爲順序隨機抽樣的高效算法」，從1987年的紙張適應下面這得益於維瑟博士的慷慨可從ACM數字圖書館免費獲取，詳見Dr. Visser's publications page.，詳情請閱讀論文。）

而不是增加i並選擇一個隨機數，如上面的python代碼，如果我們可以根據一些分佈生成一個隨機數，這將是很酷，這將是i將被遞增的次數任何元素都被放棄。我們需要的是分佈（這顯然取決於當前值n和N）。

當然，我們可以從算法的檢查中精確地推導出分佈。然而，這並沒有多大幫助，因爲生成的公式需要大量時間才能準確計算，最終結果仍然是O(N)。

但是，我們並不總是要準確計算它。假設我們有一些容易計算的相當好的近似值，它總是低估概率（結果有時不會進行預測）。如果這個近似有效，我們可以使用它;如果不是，我們需要回退到準確的計算。如果這種情況發生得很少，我們平均可以達到O(n)。事實上，Visser博士的論文展示瞭如何做到這一點。（帶有代碼）

來源

2014-10-21 04:32:51 rici

以排序順序生成隨機數

回答

相關問題