如何確定性地交織N個不同長度的異構列表？

這裏是我的目標：我有ñ名單（假設N = 3）大小不同，每一個包含不同類型的項目和我需要生成一個包含所有他們的一個列表，最小化相同類型的相鄰商品的數量。如何確定性地交織N個不同長度的異構列表？

我個人使用Python，但任何僞代碼解決方案將被接受。

實施例：

A = [a1, a2, a3] 
B = [b1, b2] 
C = [c1, c2, c3, c4] 

OUT = f(A, B, C) 
> [a1, b1, c1, a2, b2, c2, a3, c3, c4]

在上面的例子我在同一時間被簡單地重複所述3所列出並從挑選每一個項目，直到每一個項目被取。這非常簡單，快速和確定性。（注：鄰近的類似項目的數量不是最佳最小化，但讓我們說這是可容忍的多數用例）

但

我寧願避免A，B，C， a，b，c，...模式，並使其看起來更「自然」，但仍然確定性（閱讀：相同的輸入，相同的輸出）。

實施例：

OUT = [a1, b1, c1, b2, a2, c2, a3, c3, c4]

任何建議？

P.s.對於一個真實世界的例子，讓我們對這3個列表進行映像，其中包含3種不同類型的文章（新聞，教程和評論），我們正在爲我們的博客生成建議/推薦文章列表。

來源

2015-02-12 alexcasalboni

你可以選擇下一個元素使用僞隨機a附加到結果列表中總是使用相同種子的算法。 – 2015-02-12 00:27:43

您被迫擁有同一類別的相鄰元素的唯一方法是，如果該類別至少有2個元素比所有其他元素放在一起。因此，通過組合從最小到最大的列表，可以很容易地將鄰接關係歸納爲最小值。但是，我懷疑你有其他標準，你沒有說明。 – 2015-02-12 14:35:25

import random 

def interleave(*lists): 
    random.seed("OWA TAGOO SIAM") #ensures deterministic behaviour 
    lists = list(lists) # so its mutable 
    for i in range(max(map(len,lists))): 
     random.shuffle(lists) #randomize the order of the lists 
     for j in lists: 
      if i < len(j): 
       yield j[i] 

A = [a1, a2, a3] 
B = [b1, b2] 
C = [c1, c2, c3, c4]  

print list(interleave(A,B,C))

來源

2015-02-12 00:35:27

這不會是確定性的，除非您先設置種子。另外，'shuffle'是來自'random'模塊的函數，而不是列表方法。 – L3viathan 2015-02-12 00:43:22

啊好點...（我不使用shuffle，並添加它作爲事後考慮） – 2015-02-12 00:50:47

這裏是我的建議：

import random 

def mix(ls): 
    random.seed(0) 

    final_length = sum([len(l) for l in ls]) 
    r = [] 
    while len(r) < final_length: 
     l = ls[random.randint(0, len(ls) - 1)] 
     if len(l) > 0: 
      r.append(l.pop())  
    return r

然後，你可以使用它：

a = ['a1', 'a2', 'a3'] 
b = ['b1', 'b2'] 
c = ['c1', 'c2', 'c3', 'c4'] 

r = mix([a, b, c])

而結果將是：

['c4', 'c3', 'b2', 'a3', 'b1', 'c2', 'a2', 'c1', 'a1']

來源

2015-02-12 00:38:54

如何確定性地交織N個不同長度的異構列表？

回答

相關問題