插入基於條件的嵌套列表缺少的元素 - Python的

Question

我有嵌套列表，

a = [(2,0),(3,0),(4,2),(10,3),(11,5)] 

我想要做的是在位置n，加上內部元組(0,n)其中n是丟失元素的位置在a。每個內部列表中的第二個元素應該以1爲增量增加，如果有差距，則應該在該差距處插入(0,n)。

所以對於列表a預期的結果是：

a_out = [(2,0),(3,0),(0,1),(4,2),(10,3),(0,4),(11,5)] 

即自a第一和第二個元素是(3,0)和(4,2)的所以(0,1)插入它們之間。

我的解決方案有效，但我想知道是否有更多的pythonic方式去實現它？我一直在查找Python的itertools庫，但我找不到一個簡潔的解決方案。

到目前爲止我的代碼是：

l1 = [n[1] for n in a] 
l2 = range(max(l1)+1) 
l3 = [n for n in l2 if not in l1] 


zeros = [0]*len(l3) 
inserts = zip(zeros,l3) 
a_full = a + inserts 

a_out = sorted(a_full, key = itemgetter(1)) 

任何人都可以提出一個更好的解決這個？

編輯：

一般可以有許多的元素用相同的第二內部元件（例如(2,0)和(3,0)發生的歷史中a）。但是，我可以將它們組合在一起而不會失去一般性。

嵌套列表然後a可以表示爲，

a_sum = [(5,0),(4,2),(10,3),(11,5)] 

通過使用代碼，

a_group = [sum([x for x, y in group]) for key, group in groupby(a, key=itemgetter(1))] 

a_sum = zip(output,list(set(l1))) 

EDIT II：

的a長度總是600，但是根據研究如何進行，可能會增加到10 ** 3。

Answer 1

您可以在O（n）的嵌套列表理解中做到這一點。只需在嵌套部分添加任何缺失的條目即可。

>>> a = [(2,0),(3,0),(4,2),(10,3),(11,5)] 
>>> [k for i,j in enumerate(a, 1) for k in [j] + [(0,n) for n in range(j[1]+1, a[min(i, len(a)-1)][1])]] 
[(2, 0), (3, 0), (0, 1), (4, 2), (10, 3), (0, 4), (11, 5)] 

或

>>> [k for i,j in zip(a, a[1:]) for k in [i] + [(0,n) for n in range(i[1]+1, j[1])]] + a[-1:] 
[(2, 0), (3, 0), (0, 1), (4, 2), (10, 3), (0, 4), (11, 5)] 

如果a很大，你可以使用一個額外的迭代器就可以了

>>> a_iter = iter(a); next(a_iter) 
(2, 0) 
>>> [k for i,j in zip(a, a_iter) for k in [i] + [(0,n) for n in range(i[1]+1, j[1])]] + a[-1:] 
[(2, 0), (3, 0), (0, 1), (4, 2), (10, 3), (0, 4), (11, 5)] 

Answer 2

a = [(2,0),(3,0),(4,2),(10,3),(11,5)] 
i = 1 
while i < len(a): 
    if a[i-1][1] + 1 < a[i][1]: 
    a.insert(i, (0, a[i-1][1]+1)) 
    i += 1 

但你可能要考慮一般使用不同的數據類型，也許defaultdict這似乎有在那裏沒有什麼存儲所有地方的默認值（在你的情況下爲0）。

Answer 3

import operator 
a = [(2,0),(3,0),(4,2),(10,3),(11,5)] 
seen = set([item[1] for item in a]) 
inserts = [(0, item) for item in range(max(seen)) if item not in seen] 
a_out = sorted(a + inserts, key=operator.itemgetter(1)) 
print(a_out) 

產生

[(2, 0), (3, 0), (0, 1), (4, 2), (10, 3), (0, 4), (11, 5)] 

以上O(n log n)解決方案保留您發佈的代碼的行爲。如果我們還可以假設，在a元組的第二個項目是總是非遞減，然後有更好的O(n)（單程）解決方案，如：

a = [(2,0),(3,0),(4,2),(10,3),(11,5)] 
result = a[:1] 
for item in a[1:]: 
    result.extend(
     [(0,i) for i in range(result[-1][1]+1, item[1])] + [item]) 

Answer 4

爲什麼不直接用小和可讀功能：

def fill(seq): 
    """ 
    >>> list(fill([(2, 0), (3, 0), (4, 2), (10, 3), (11, 5)])) 
    [(2, 0), (3, 0), (0, 1), (4, 2), (10, 3), (0, 4), (11, 5)] 
    """ 
    prev = None 
    for value, key in seq: 
     if prev != None: 
      while key > prev + 1: 
       prev += 1 
       yield (0, prev) 
     yield (value, key) 
     prev = key 

if __name__ == '__main__': 
    import doctest 
    doctest.testmod() 

Answer 5

這個版本結合了（2,0）避免a[1:]片和（3,0）轉換爲（5,0），如評論中允許的那樣

>>> from collections import defaultdict 
>>> D = defaultdict(int) 
>>> a = [(2,0),(3,0),(4,2),(10,3),(11,5)] 
>>> for i,j in a: 
...  D[j]+=i 
... 
>>> [(D[n], n) for n in range(a[0][1], a[-1][1]+1)] 
[(5, 0), (0, 1), (4, 2), (10, 3), (0, 4), (11, 5)] 

Answer 6

>>> from collections import defaultdict 
>>> D = defaultdict(list) 
>>> a = [(2,0),(3,0),(4,2),(10,3),(11,5)] 
>>> for i,j in a: 
...  D[j].append(i) 
... 
>>> [(z, n) for n in range(a[0][1], a[-1][1]+1) for z in D[n] or [0]] 
[(2, 0), (3, 0), (0, 1), (4, 2), (10, 3), (0, 4), (11, 5)]