Получите ограниченный список уникальных элементов из списка списков

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']