用Fisher-Yates shuffle從鏈接列表中獲取k個隨機值

我有一個巨大的整數鏈表（假設它的大小爲N，但N對我來說是未知的），並且想要從中獲得k個隨機值可能的時間/空間。用Fisher-Yates shuffle從鏈接列表中獲取k個隨機值

我認爲必須寫出一個從內到外的Fisher-Yates混洗的變體，它將在O（N）時間和O（k）額外空間中解決這個問題。

任何人都可以幫助我獲得統計正確的解決方案與指定的時間/空間範圍？

我覺得我當前的代碼是接近正確的解決方案：

public class Node 
{ 
    public int Data; 

    public Node Next; 

    // O(N) time, O(k) additional space 
    public int[] GetRandomData(int k) 
    { 
     var a = new int[k]; 
     var rand = new Random(); 

     int n = 0; 
     Node cur = this; 
     while (cur != null) 
     { 
      int r = rand.Next(0, n); 

      if (r < k) 
      { 
       a[r] = cur.Data; 
      } 

      cur = cur.Next;   
     } 

     if (n < k) throw new ArgumentException("k is bigger than N");   
     return a; 
    } 
}

來源

2014-01-23 lonelyass

爲什麼不只是獲得[0..N-1]之間的k個不同的隨機值？ – Shmoopy

[C＃中的隨機列表]（http://stackoverflow.com/questions/273313/randomize-a-listt-in-c-sharp） – weston

這是一個鏈接列表，夥計們。我想只用O（k）的額外空間來做到這一點。 – lonelyass

這將從未知長度的序列中返回k個項目的均勻分佈的隨機樣本。該算法被稱爲reservoir sampling。

def sample(seq, k): 
    seq = iter(seq) 
    result = [seq.next() for _ in xrange(k)] 
    for i, s in enumerate(seq): 
     r = random.randrange(i + k + 1) 
     if r < k: result[r] = s 
    return result

來源

2014-01-23 14:05:13

非常感謝！非常有用 https://en.wikipedia.org/wiki/Reservoir_sampling – lonelyass

-1

這是sattolo算法

from random import randrange 
def sattoloCycle(items): 
    i = len(items) 
    while i > 1: 
     i = i - 1 
     j = randrange(i) # 0 <= j <= i-1 
     items[j], items[i] = items[i], items[j] 
    return

來源

2014-01-23 13:25:20

這樣找到循環和不記得我有鏈接列表，所以它與問題無關。 – lonelyass

我結束了與此版本（C＃）的執行情況和我很確定這是正確的。告訴我，如果我錯了。

public class Node 
{ 
    public int Data; 

    public Node Next; 

    // O(N) time, O(k) additional space 
    public int[] GetRandomData(int k) 
    { 
     var a = new int[k]; 
     var rand = new Random(); 

     a[0] = this.Data; 
     int i = 1; 

     for (Node cur = this.Next; cur != null; cur = cur.Next, i = i + 1) 
     { 
      int r = rand.Next(0, i + 1); 

      if (r < k) 
      { 
       if (i < k) 
       { 
        a[i] = a[r]; 
       } 

       a[r] = cur.Data; 
      } 
     } 

     if (i < k) throw new ArgumentException("k is bigger than N"); 
     return a; 
    } 
}

UPD：好了，我的代碼是相同的怎麼在這裏寫在wikipedia，所以它必須是正確的統計。

來源

2014-01-23 13:47:03 lonelyass

用Fisher-Yates shuffle從鏈接列表中獲取k個隨機值

回答

相關問題