adefabritiis - 1 year ago 72
Python Question

# Get a constrained list of unique elements from a list of lists

I have to solve this optimization problem using Python. I have a list of lists, each one containing elements. For instance:

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

What I need to obtain is a list
`r`
such that:

1) Both the lists should have the same length

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

2) Each selected element should correspond to the elements of the same index list

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

3) Elements should be unique

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

A possible result here will be for example:

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

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

Thanks

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.

``````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:
``````['elem5', 'elem2', 'elem3', 'elem1']