兩個列表的比較元素

Question

A = [a1, a2, a3...] #a1<a2<a3... 
B = [b1, b2...] #b1<b2<b3... 

A和B不相交。我是否預先知道A/B中元素的數量和它們的價值？我想比較這兩個列表中的元素的值並刪除IFF元素：

delete a[i+1] if there is no b[j] such that a[i]<b[j]<a[i+1] 
delete b[i+1] if there is no a[j] such that b[i]<a[j]<b[i+1] 

最後，我要分開列表，而不是A的組合B.

例如，如果A[0] < B[0]，A = [1,10,40]，B = [15,30]。首先比較A[1]和B[0]。刪除10，因爲B中沒有元素在1到15之間。 然後刪除15，因爲沒有元素存在了，因此15和30.輸出應該是：如果您嘗試排序新的2列表的元素，它應該是A[0]<B[0]<A[1]<B[1]<...

如果是A[0] > B[0]，反之亦然。

Answer 1

a = [1, 10, 40] 
b = [15, 30] 

srcs = [a, b] 
dsts = [[], []] 
prev_which = -1 
while all(srcs): 
    which = int(srcs[0][0] > srcs[1][0]) 
    elem = srcs[which].pop(0) 
    if prev_which != which: 
     dsts[which].append(elem) 
    prev_which = which 
for src, dst in zip(srcs,dsts): 
    if src: 
     dst.append(src.pop(0)) 
a, b = dsts 

回報：

a = [1, 40] 
b = [15] 

和

a = [3, 4, 6, 7, 8, 9] 
b = [1, 2, 5, 10] 

返回[3, 6]和[1, 5, 10]。

編輯：另一種可能性：

import itertools as it 
import operator as op 

a = [3, 4, 6, 7, 8, 9] 
b = [1, 2, 5, 10] 
srcs = [a, b] 
dsts = [[], []] 

for which, elems in it.groupby(sorted((x, i) for i in (0,1) for x in srcs[i]), key=op.itemgetter(1)): 
    dsts[which].append(next(elems)[0]) 
a, b = dsts 

Answer 2

我在編輯之前想出了這個。但看起來輸出結果並不符合你的期望。總之，它可以幫助你在正確的軌道上：

a = range(0, 30, 3) 
b = range(0, 20, 2) 

a.sort() 
b.sort() 

A = [a[i+1] for i in range(len(a)-1) if any(a[i]<b[j]<a[i+1] for j in range(len(b)-1))] 
B = [b[i+1] for i in range(len(b)-1) if any(b[i]<a[j]<b[i+1] for j in range(len(a)-1))] 

result = sorted(A+B) 

print a, b 
print result 

這是「字面意思是」你所表達的，但這裏的result是不是你所期望的。我會盡力改善這一點。

Answer 3

使用對開模塊可能是一個很好的解決方案，我知道：

>>> def sort_relative(L1, L2): 
    # Switch if needed 
    if L1[0] > L2[0]: 
     L1, L2 = L2, L1 
    i = 0 
    while i + 1 < max(len(L1), len(L2)): 
     try: 
      # We know that L1[i] < L2[i] 
      # Get indexes where L2[i] and L2[i + 1] should be inserted 
      i11 = bisect.bisect_left(L1, L2[i]) 
      i12 = bisect.bisect_left(L1, L2[i + 1]) 

      # This condition allows to know if one element of L1 
      # was found between L2[i] and L2[i + 1]: 
      # - if so, we have L1[i] < L2[i] < L1[i + 1] < L2[i + 1] 
      # - else we have L1[i] < L2[i] < L1[i + 1] but 
      # we don't know between L1[i + 1] and L2[i + 1] 
      if L1[i11] < L2[i + 1]: 
       L1 = L1[:i + 1] + [L1[i11]] + L1[i12:] 
       index1, index2 = i + 1, i + 2 
      else: 
       L1 = L1[:i + 1] + L1[i12:] 
       index1, index2 = i, i + 1 

      # Do the same kind of symetric search, 
      # with indexes computed above 
      i21 = bisect.bisect_left(L2, L1[index1]) 
      i22 = bisect.bisect_left(L2, L1[index2]) 
      if L2[i21] < L1[index2]: 
       L2 = L2[:index1] + [L2[i21]] + L2[i22:] 
      else: 
       L2 = L2[:index1] + L2[i22:] 
     # Little trick not to test indexes everywhere: 
     # lists are browsed at the same time 
     except IndexError: 
      pass 

     # Next index ! 
     i += 1 

    # Show result 
    print 'L1:', L1, '- L2:', L2 


>>> sort_relative([1, 10, 50], [15, 30]) 
L1: [1, 50] - L2: [15] 
>>> sort_relative([17, 18, 50], [15, 30]) 
L1: [15, 30] - L2: [17, 50] 
>>> sort_relative([1, 10, 12, 25, 27, 50], [15, 30, 70]) 
L1: [1, 25, 50] - L2: [15, 30, 70] 
>>> sort_relative([1, 10, 12, 25, 27, 50], [15, 30, 34, 70]) 
L1: [1, 25, 50] - L2: [15, 30, 70] 
>>> 

當一個數字是我沒有考慮到的情況下都在A和B。

Answer 4

所以，如果我正確閱讀，你的例子所需的輸出是[1,40]和[15]，是嗎？

如果是這樣，以下將得到正確的結果，但我確信有一個更緊密的方式來做到這一點。

a = [1, 10, 40] 
b = [15, 30] 
c = sorted([[e_a,'a'] for e_a in a] + [[e_b,'b'] for e_b in b]) 
indices = [] 

for i in range(len(c)-1): 
    if c[i][1] == c[i+1][1]: 
     indices.append(i+1) 

for e in sorted(indices, reverse=True): 
    del c[e] 

a,b = [e[0] for e in c if e[1]=='a'],[e[0] for e in c if e[1]=='b'] 

首先 - 合併列表並對它們進行排序，同時記錄它們來自哪個列表。

第二個 - 然後刪除合併列表中下一個項目來自同一個源列表的所有實例。

第三 - 更新a和b。