从列表列表中获取唯一元素的受约束列表

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）元素应是唯一的

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