adefabritiis adefabritiis - 2 months ago 8
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

Answer

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:
            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                

This outputs:

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