隨機交織多個迭代，同時保留它們在python中的順序

Question

受this earlier stack overflow question的啓發我一直在考慮如何在保留每個迭代內元素順序的同時在python中隨機交錯迭代。例如：

>>> def interleave(*iterables): 
...  "Return the source iterables randomly interleaved" 
...  <insert magic here> 
>>> interleave(xrange(1, 5), xrange(5, 10), xrange(10, 15)) 
[1, 5, 10, 11, 2, 6, 3, 12, 4, 13, 7, 14, 8, 9] 

原來的問題問隨機交錯兩個列表，a和b，以及接受的解決方案是：

>>> c = [x.pop(0) for x in random.sample([a]*len(a) + [b]*len(b), len(a)+len(b))] 

然而，這種解決方案適用於只有兩個列表（儘管它可以很容易被擴展）並且依賴於a和b是列表這樣的事實，因此pop()和len()可以被調用，這意味着它不能用於迭代。它也有清空源列表a和b的不幸副作用。

爲原始問題提供的備選答案需要獲取源列表副本以避免修改它們，但這樣做會降低效率，尤其是源列表很大時。備用答案也使用len()，因此不能僅用於迭代。

我寫我自己的解決方案，爲任意數量的輸入列表的工作，不對其進行修改：

def interleave(*args): 
    iters = [i for i, b in ((iter(a), a) for a in args) for _ in xrange(len(b))] 
    random.shuffle(iters) 
    return map(next, iters) 

但這種解決方案還依賴於源參數是列表，以便len()可以對它們使用。

那麼，有沒有一種有效的方法來在python中隨機交錯迭代，保留元素的原始順序，而不需要提前知道迭代的長度，並且不需要複製迭代？

編輯：請注意，與原始問題一樣，我不需要隨機化是公平的。

Answer 1

這裏是一種使用發電機的方法：

import random 

def interleave(*args): 
    iters = map(iter, args) 
    while iters: 
    it = random.choice(iters) 
    try: 
     yield next(it) 
    except StopIteration: 
     iters.remove(it) 

print list(interleave(xrange(1, 5), xrange(5, 10), xrange(10, 15))) 

Answer 2

不是如果你想適合「公平」。

想象一下，您有一個包含一百萬個項目的列表，另一個包含兩個項目。一個「公平」的隨機化會使短名單中的第一個元素出現在300000左右的指數左右。

a,a,a,a,a,a,a,...,a,a,a,b,a,a,a,.... 
         ^

但是，除非您知道列表的長度，否則無法預先知道。

如果你只是從每個列表採取與50％（1/n）的概率則是可以做到在不知道列表的長度，但你會得到更多的東西是這樣的：

a,a,b,a,b,a,a,a,a,a,a,a,a,a,a,a,... 
    ^^

Answer 3

我很滿意由aix提供的解決方案滿足問題的要求。但是，在閱讀comments by Mark Byers之後，我想看看解決方案有多「不公平」。

此外，在我寫這個問題之後的一段時間，堆棧溢出用戶EOL將another solution發佈到original question，這產生了「公平的」結果。EOL的解決方案是：

>>> a.reverse() 
>>> b.reverse() 
>>> [(a if random.randrange(0, len(a)+len(b)) < len(a) else b).pop() 
...  for _ in xrange(len(a)+len(b))] 

我也進一步增強了我自己的解決方案，以便它不依賴於它的論據支持len()但它使源iterables的副本：

def interleave(*args): 
    iters = sum(([iter(list_arg)]*len(list_arg) for list_arg in map(list, args)), []) 
    random.shuffle(iters) 
    return map(next, iters) 

，或者有不同的寫法：

def interleave(*args): 
    iters = [i for i, j in ((iter(k), k) for k in map(list, args)) for _ in j] 
    random.shuffle(iters) 
    return map(next, iters) 

我然後測試接受的解決方案，以原來的問題，由FJ書面及以上我的問題複製到AIX，EOL的解決方案和 我自己的。測試涉及將30000個元素的列表與單個元素列表（標記）交錯。我重複了1000次測試，下表顯示了每種算法的交叉後最小值，最大值和平均值以及總時間。我們期望一個「公平的」算法產生一個約的平均值。 15000：

algo min    max    mean   total_seconds 
---- ---    ---    ----   ------------- 
F.J: 5    29952   14626.3   152.1 
aix: 0    8    0.9    27.5 
EOL: 45    29972   15091.0   61.2 
srgerg: 23    29978   14961.6   18.6 

如可從結果中可以看出，每個F.J，EOL的算法和srgerg產生表面上的「公平」的結果（至少在給定的測試條件下）。然而，aix算法總是將哨兵放置在結果的前10個元素內。我重複了幾次實驗，獲得了類似的結果。

所以馬克·拜爾斯被證明是正確的。如果需要真正的隨機交織，則需要提前知道源迭代的長度，否則需要創建副本以確定長度。