Get a constrained list of unique elements from a list of lists
<p>I have to solve this optimization problem using Python. I have a list of lists, each one containing elements. For instance:</p>

<pre><code>l = [
       ['elem1'],
       ['elem2'],
       ['elem3','elem4'],
       ['elem4','elem5']
    ]
</code></pre>

<p>What I need to obtain is a list <code>r</code> such that: </p>

<p>1) Both the lists should have the same length</p>

<pre><code>&gt;&gt;&gt; len(r)==len(l)
True
</code></pre>

<p>2) Each selected element should correspond to the elements of the same index list </p>

<pre><code>&gt;&gt;&gt; correct=True
&gt;&gt;&gt; for r_element in r:
...     if r_element not in l[r.index(r_element)]:
...         correct=False
...         break
...         
&gt;&gt;&gt; correct
True
</code></pre>

<p>3) Elements should be unique</p>

<pre><code>&gt;&gt;&gt; len(r) &gt; len(set(r))
False
</code></pre>

<p>A possible result here will be for example:</p>

<pre><code>r = ['elem1','elem2','elem3','elem4']
</code></pre>

<p>Is there a best way to do this? Or maybe not using lists but some other data structures or some specific Python packages?</p>

<p>Thanks</p>

<p>Here's an approach that uses recursive backtracking to make selections and backtracks if they don't work. The function returns a failure in the form of a string if no list can meet the constraints.</p>

<pre><code>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                
</code></pre>

<p>This outputs:</p>

<pre><code>['elem5', 'elem2', 'elem3', 'elem1']
</code></pre>

python list data-structures