Nested lists , check if one list has common elements with other and if so join

Question

I have a lists in list say [[1, 3, 5], [2, 4], [1,7,9]]

my requirement is i want to iterate through the list and reduce it to

[[1,3,5,7,9], [2,4]].

How would i do it??

Answer 1

It's quite inefficient, but this does the trick:

def combine_lists(lists):
    # Keep a set of processed items
    skip = set()

    for i, a in enumerate(lists):
        # If we already used this list, skip it
        if i in skip:
            continue

        for j, b in enumerate(lists[i + 1:], i + 1):
            # Use a set to check if there are common numbers
            if set(a) & set(b):
                skip.add(j)

                for x in b:
                    if x not in a:
                        a.append(x)

    # yield all lists that were not added to different lists
    for i, a in enumerate(lists):
        if i not in skip:
            yield a

[edit] Just noticed that the order doesn't matter anymore (your output suggests that it does), that makes things easier :)

This version should be fairly optimal:

def combine_lists(lists):
    # Keep a set of processed items
    skip = set()
    sets = map(set, lists)

    for i, a in enumerate(sets):
        # If we already returned this set, skip it
        if i in skip:
            continue

        for j, b in enumerate(sets[i + 1:], i + 1):
            # Use a set to check if there are common numbers
            if a & b:
                skip.add(j)
                a |= b

    # yield all sets that were not added to different sets
    for i, a in enumerate(sets):
        if i not in skip:
            yield a

Answer 2

Algo:

1. Get base element from the new method.
2. Remove First item from input list and create new variable for that.
3. Iterate on every item from the new list.
4. Check any element from item is present in the base set or not by set intersection method.
5. If present then do 6,7,8,9
6. Update base with current item by set update method.
7. Remove current item from the list.
8. Set flag to True.
9. break the for loop because need to check again from first item.
10. Create final result list add adding base and remaining list.

[Edit:]

Issue:

Previous code considering base item as first item from the given list, but when there is no matching of this item with other items and other items have matching then code will not work.

Updated:

Get base item from the given list which have matching with any one item from the list.

[Edit2]:

Inserted merged item into respective position

Demo:

import copy

a = [[13, 15, 17], [66,77], [1, 2, 4], [1,7,9]]

#- Get base
base = None
length_a = len(a)
base_flag = True
i = -1
while base_flag and i!=length_a-1:
    i += 1
    item = a[i]
    for j in xrange(i+1, length_a):
        tmp = set(item).intersection(set(a[j]))
        if tmp:
            base = set(item)
            base_flag = False
            break

print "Selected base:", base
if base:
    tmp_list = copy.copy(a)
    target_index = i
    tmp_list.pop(target_index)
    flag = True
    while flag:
        flag = False
        for i, item in enumerate(tmp_list):
            tmp = base.intersection(set(item))
            if tmp:
                base.update(set(item))
                tmp_list.pop(i)
                flag = True
                break

    print "base:", base
    print "tmp_list:", tmp_list
    result = tmp_list
    result.insert(target_index, list(base))

else:
    result = a

print "\nFinal result:", result

Output:

$ python task4.py 
Selected base: set([1, 2, 4])
base: set([1, 2, 4, 7, 9])
tmp_list: [[13, 15, 17], [66, 77]]

Final result: [[13, 15, 17], [66, 77], [1, 2, 4, 7, 9]]

Answer 3

a = [[1,2], [3,4 ], [1,5,3], [5]] # output: [set([1, 2, 3, 4, 5])]
# a = [[1, 3, 5], [2, 4], [1,7,9]] # output: [set([1, 3, 5, 7, 9]), set([2, 4])]

# convert them to sets
a = [set(x) for x in a]
go = True

while go:
    merged = False
    head = a[0]

    for idx, item in enumerate(a[1:]):
        if head.intersection(item):
            a[0] = head.union(item)
            a.pop(idx + 1)
            merged = True
            break

    if not merged:
        go = False

print a