Exhaustive combinations of lists in python

问题:

I have a long list of lists in Python that looks something like this:

myList=[

('a',[1,2,3,4,5]),
('b',[6,7,8,9,10]),
('c',[1,3,5,7,9]),
('d',[2,4,6,8,10]),
('e',[4,5,6,7,8])

]

And I would like to enumerate the common values exhaustively

('a:b', ),
('a:c', [1,3,5]),
('a:d', [2,4]),
('a:e', [4,5]),
('b:c', [7,9]),
('b:d', [6,8,10]),

('a:c:e', [5]),
('b:c:e', [7]),
('b:d:e', [6,8]),

and the same for groups of four, five, six until all common values have been identified (assuming the lists were longer)

Is this possible using the itertools library or sets or a combination of the above?

I have been trying to write a function that loops over the original list for every new list I generate but It hasn't been going well!

Here is what I have:

def findCommonElements(MyList):

    def sets(items):
        for name, tuple in items:
            yield name, set(tuple)

    def matches(sets):
       for a, b in combinations(sets, 2):
           yield ':'.join([a[0], b[0]]), a[1] & b[1]

    combinationsSet=list(matches(sets(keywordCount)))

    combinationsList=[]
    for pair,tup in combinationsSet:
        setList=list(tup)
        combinationsList.append((pair, len(setList), setList))
    combinationsList=sorted(combinationsList,key=lambda x: x[1], reverse=True) #this just sorts the list by the number of common elements

    return combinationsList

回答1:

I think You can try to use itertools.combinations with itertools.chain

nit very good example but It should work. I will use itertools and generators here:

lengthes = xrange(2, len(myList)+1)
combinations_list = (itertools.combinations(myList, i) for i in lengthes)
combinations = itertools.chain.from_iterable(combinations_list)
def find_intersection(lists):
    res = set(lists[0])
    for data in lists:
        res &= set(data)
    return res
result = [(':'.join(i), list(find_intersection(v))) for i, v in (zip(*x) for x in combinations)]

or just itertools.combinations

def findCommonElements(MyList):

    combinationsList=[]

    for seq_len in xrange(2, len(MyList)+1):
        for combination in combinations:
            for indexes, values in zip(*combination):
                intersection = reduce(lambda x, y: x & set(y[1]), 
                                      values, set(values[0]))
                if intersection:
                    combinationsList.appen(':'.join(indexes), intersection)
        return combinationsList

回答2:

Here is a solution using dictionaries I just whipped up:

def iter_recursive_common_elements(lists, max_depth=None):
    data = [{k:set(v) for k,v in lists.iteritems()}] # guarantee unique
    depth = 0

    def get_common_elements(lists, base):
        d = {}
        for k, v in lists.iteritems():
            merged = k.split(':')
            potential = set(base).difference(merged)
            for target in potential:
                d[':'.join(sorted(merged+[target]))] = v.intersection(base[target])
        return d if d else None

    while True:
        ret = get_common_elements(data[depth], data[0])
        if not ret:
            break
        data.append(ret)
        depth += 1
        yield data[depth]
        if max_depth and depth > max_depth:
            break

---

Using it is simple enough:

lists = {'a':[1,2,3,4,5],
        'b':[6,7,8,9,10],
        'c':[1,3,5,7,9],
        'd':[2,4,6,8,10],
        'e':[4,5,6,7,8]}

for x in iter_recursive_common_elements(lists):
    print x

>>> 
{'d:e': set([8, 4, 6]), 'a:b': set([]), 'a:c': set([1, 3, 5]), 'a:d': set([2, 4]), 'a:e': set([4, 5]), 'b:e': set([8, 6, 7]), 'b:d': set([8, 10, 6]), 'b:c': set([9, 7]), 'c:d': set([]), 'c:e': set([5, 7])}
{'a:b:d': set([]), 'a:b:e': set([]), 'a:b:c': set([]), 'a:c:e': set([5]), 'c:d:e': set([]), 'a:c:d': set([]), 'b:c:d': set([]), 'b:c:e': set([7]), 'b:d:e': set([8, 6]), 'a:d:e': set([4])}
{'b:c:d:e': set([]), 'a:b:c:e': set([]), 'a:b:c:d': set([]), 'a:c:d:e': set([]), 'a:b:d:e': set([])}
{'a:b:c:d:e': set([])}

---

Can also clean up the output to match more what you wanted:

for x in iter_recursive_common_elements(lists):
    for k, v in sorted(x.items()):
        if v:
            print '(%s) : %s' % (k.replace(':', ', '), list(v))

>>> 
(a, c) : [1, 3, 5]
(a, d) : [2, 4]
(a, e) : [4, 5]
(b, c) : [9, 7]
(b, d) : [8, 10, 6]
(b, e) : [8, 6, 7]
(c, e) : [5, 7]
(d, e) : [8, 4, 6]
(a, c, e) : [5]
(a, d, e) : [4]
(b, c, e) : [7]
(b, d, e) : [8, 6]

回答3:

How about something like this ?

from itertools import combinations

myList = [
    ('a', [1, 2, 3, 4, 5]),
    ('b', [6, 7, 8, 9, 10]),
    ('c', [1, 3, 5, 7, 9]),
    ('d', [2, 4, 6, 8, 10]),
    ('e', [4, 5, 6, 7, 8]),
]


def print_commons(mList):

    letters = map(lambda l: l[0], mList)
    mdict = dict(mList)

    for i in range(2, len(letters) + 1):
        for comb in combinations(letters, i):  # generate all possible combinations
            sequence = [mdict[letter] for letter in comb]  # get the corresponding lists 
            uniques = reduce(lambda x, y: set(x).intersection(y), sequence)  # reduce the lists until only the common elements remain
            print('{} : {}'.format(comb, list(uniques)))

print_commons(myList)

('a', 'b') : []
('a', 'c') : [1, 3, 5]
('a', 'd') : [2, 4]
('a', 'e') : [4, 5]
('b', 'c') : [9, 7]
('b', 'd') : [8, 10, 6]
('b', 'e') : [8, 6, 7]
('c', 'd') : []
('c', 'e') : [5, 7]
('d', 'e') : [8, 4, 6]
('a', 'b', 'c') : []
('a', 'b', 'd') : []
('a', 'b', 'e') : []
('a', 'c', 'd') : []
('a', 'c', 'e') : [5]
('a', 'd', 'e') : [4]
('b', 'c', 'd') : []
('b', 'c', 'e') : [7]
('b', 'd', 'e') : [8, 6]
('c', 'd', 'e') : []
('a', 'b', 'c', 'd') : []
('a', 'b', 'c', 'e') : []
('a', 'b', 'd', 'e') : []
('a', 'c', 'd', 'e') : []
('b', 'c', 'd', 'e') : []
('a', 'b', 'c', 'd', 'e') : []

回答4:

I'd split it into three parts. One, your list in unwieldy, it'd be better to store it as a dictionary with the letter as key, and a set of values as the value:

def make_dict(myList):
    return dict((letter, set(values)) for letter, values in myList)

Second, all the possible combinations. I think combinations of length 1 (the letters by themselves) aren't interesting, so you want the combinations of length 2 to the maximum:

from itertools import combinations
def all_combinations(letters):
   for length in range(2, len(letters) + 1):
       for combination in combinations(letters, length):
           yield combination

And third, a function that given that created dictionary, and a combination, yields the numbers that are common to all the letters:

def common_values(the_dict, combination):
    # This can be made shorter with reduce(), but I hate it
    values_so_far = the_dict[combination[0]]
    for letter in combination[1:]:
        value_so_far = values_so_far & the_dict[letter]
    return values_so_far

And then all three can be easily combined:

the_dict = make_dict(myList)
for combination in all_combinations(the_dict):
    print combination, common_values(the_dict, combination)