從列表中獲取受限列表中的獨特元素

Question

我必須使用Python解決這個優化問題。我有一個列表，每個列表包含元素。例如：

l = [ 
     ['elem1'], 
     ['elem2'], 
     ['elem3','elem4'], 
     ['elem4','elem5'] 
    ] 

我需要的，以獲得是一個列表r使得：

1）這兩個列表應當具有相同的長度

>>> len(r)==len(l) 
True 

2）每個所選擇的元素應該對應到相同索引列表的元素

>>> correct=True 
>>> for r_element in r: 
...  if r_element not in l[r.index(r_element)]: 
...   correct=False 
...   break 
...   
>>> correct 
True 

3）元素應該是u NIQUE

>>> len(r) > len(set(r)) 
False 

一個可能的結果，這裏將是例如：

r = ['elem1','elem2','elem3','elem4'] 

有沒有做到這一點最好方法是什麼？或者可能不使用列表，但一些其他數據結構或一些特定的Python包？

感謝

Answer 1

下面是一個使用遞歸回溯進行選擇，如果他們不工作回溯的方法。如果沒有列表可以滿足約束條件，函數將以字符串的形式返回失敗。

l = [ 
     ['elem1', 'elem5'], 
     ['elem2'], 
     ['elem3','elem4'], 
     ['elem1','elem2'] 
    ] 

def constrained_list(l): 
    r = []    # final list 
    used = set()   # values used 
    if recurse(r, used, l): return r  # if successul in finding contrained list, return it 
    return "No valid list" 

def recurse(r, used, l): 
    if not l: return True  # base case, l has been completely processed 
    line = l[0]     # look at first line in l 
    for word in line: 
     if word not in used: 
      used.add(word)  
      r.append(word)  # try adding this word 
      if recurse(r, used, l[1:]): return True  # recurse on the rest of l, from 1 to end 
      used.remove(word) # if this choice didnt work, backtrack. 
      r.pop() 
    return False     

此輸出：

['elem5', 'elem2', 'elem3', 'elem1']