how to merge two sublists sharing any number in common?(2)

Question

Given that:

list=[[1,2,3],[3,4,5],[5,6],[6,7],[9,10],[10,11]]

I have asked a similar question before, I have tried the code on how to merge two sublists sharing any number in common? but I am stuck in my code now. I want to merge the sublists that share a common number, e.g. [1,2,3] and [3,4,5] can merge to give [1,2,3,4,5] as they share a common number, 3. In [[1,2,3],[3,4,5],[5,6]], although [1,2,3] and [3,4,5] share a common number, 3, [3,4,5] and [5,6] also share a common number, 5, so I want all three of them to merge then gives [1,2,3,4,5,6].

So for list, my expected result is:

[[1,2,3,4,5,6,7],[9,10,11]]

I have tried the following code but don't know what is wrong, can anyone help?

    s = map(set, list)
    for i, si in enumerate(s):
        for j, sj in enumerate(s):
            if i != j and si & sj:
                s[i] = si | sj
                s[j] = set()
    list=[list(el) for el in s if el]
    print list
>>>[[5, 6, 7], [9, 10, 11]]

Answer 1

def merge_containing(input_list):
    merged_list = [set(input_list[0])]
    i = 0
    for sub_list in input_list:
        if not set(sub_list).intersection(set(merged_list[i])):  # 1
            merged_list.append(set())  # 2
            i += 1  # 2
        merged_list[i].update(set(sub_list))  # 3

    return [sorted(sub_list) for sub_list in merged_list]  # 4

mylist=[[1,2,3],[3,4,5],[5,6],[6,7],[9,10],[10,11]]
print merge_containing(mylist)

Output:

[[1, 2, 3, 4, 5, 6, 7], [9, 10, 11]]

How does it work:

1. Check if the sub_list set shares any common member with the current index set of the merged_list.
2. If it doesn't, add a new empty set to the merged_list and increment the index.
3. Adds the sub_list set to the set at index in the merged_list.
4. Converts from set to list and return

Answer 2

    def merge(list_of_lists):
        number_set = set()
        for l in list_of_lists:
            for item in l:
                number_set.add(item)    
        return sorted(number_set)  

    if __name__ == '__main__':
        list_of_lists = [[1,2,3],[3,4,5],[5,6],[6,7],[9,10],[10,11]]
        merged = merge(list_of_lists)
        print merged

Answer 3

Okay. This solution may be difficult to grasp at first, but it's quite logical and succint, IMO.

The list comprehension basically has two layers. The outer layer will itself create separate lists for each value of i (outer index) that satisfies the condition that the value it points to in the list is not equal to the value pointed to by the previous index + 1. So every numerical jump greater than one will create a new list within the outer list comprehension.

The math around the second (inner list comprehension) condition is a bit more complicated to explain, but essentially the condition seeks to make sure that the inner list only begins counting from the point where the outer index is at, stopping to where once again there is a numerical jump greater than one.

Assuming an even more complicated input:

listVar=[[1,2,3],[3,4,5],[5,6],[6,7],[9,10],[10,11],[65,231,140], [13,14,51]]

# Flattens the lists into one sorted list with no duplicates.
l = sorted(set([x for b in listVar for x in b]))

lGen = xrange(len(l))

print [
    [l[i2] for i2 in lGen if l[i2] + i == l[i] + i2] 
    for i in lGen if l[i] != l[i-1] + 1
]

>>> [[1, 2, 3, 4, 5, 6, 7], [9, 10, 11], [13, 14], [51], [65], [140], [231]]

Answer 4

I'm posting this as a new answer since the OP already accepted my other.

But as pointed out by @Eithos,

the input:

[[3,4], [1,2], [1,3]] 

should return

[[1,2,3,4]]

and the input

[[1,2,3],[3,4,5],[5,6],[6,7],[9,10],[10,11],[65,231,140], [13,14,51]]

should return

[[1, 2, 3, 4, 5, 6, 7], [9, 10, 11], [13, 14], [51], [65], [140], [231]]

Here's my attempt:

from itertools import chain

def merge_containing(input_list):
    print " input:", input_list
    chain_list = sorted(set(chain(*input_list))) # 1
    print " chain:",chain_list
    return_list = []
    new_sub_list = []
    for i, num in enumerate(chain_list):
        try:
            if chain_list[i + 1] == chain_list[i] + 1:  # 2
                new_sub_list.append(num)
            else:
                new_sub_list.append(num)  # 3
                return_list.append(new_sub_list)
                new_sub_list = []
        except IndexError:
            new_sub_list.append(num)  # 3
            return_list.append(new_sub_list)

    print 'result:', return_list
    return return_list

mylist = [[3,4], [1,2], [1,3]]
merge_containing(mylist)
print
mylist = [[1,2,3],[3,4,5],[5,6],[6,7],[9,10],[10,11],[65,231,140], [13,14,51]]
merge_containing(mylist)

Output:

 input: [[3, 4], [1, 2], [1, 3]]
 chain: [1, 2, 3, 4]
result: [[1, 2, 3, 4]]

 input: [[1, 2, 3], [3, 4, 5], [5, 6], [6, 7], [9, 10], [10, 11], [65, 231, 140], [13, 14, 51]]
 chain: [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 51, 65, 140, 231]
result: [[1, 2, 3, 4, 5, 6, 7], [9, 10, 11], [13, 14], [51], [65], [140], [231]]

Explanation:

This one is a little hacky them the last one

1. I use itertool.chain to flat all the lists and them I sort it.
2. Then I check if the current number is within the range of 1 digit from the next
3. If it is I store it in the new_sub_list, if not I store in the new_sub_list, then store new_sub_list in the return_list, and empty the new_sub_list.

Note the try/except Index Error, it to avoid comparing the last item of the list with one that doesn't exist,

Answer 5

Well... I couldn't resist answering @f.rodrigues' last answer with one of my own.

I have to be honest though, this final version was heavily influenced by jonrsharpe's solution (the code went through various revisions, each one more efficient until I realized his method was the only way to press the most amount of juice) over here: Using sublists to create new lists where numbers don't repeat

Which made me wonder... why are we answering the same question over and over again (from the very same person)? This question, how to merge two sublists sharing any number in common? and the one with jonrsharpe's solution.

Anyway, this joins lists in the way outlined in his first question, but, like the solutions he already received over there, this one also works just as well for solving this problem.

sequence = [[1, 4, 9], [2, 3, 6], [4, 13, 50], [13, 23, 29], [2, 3, 7]]

def combineSequences(seq):

    for index, y in enumerate(seq):
        while True:
            for x in seq[index + 1:]:
                if any(i in x for i in seq[index]):
                    seq.remove(x)
                    y.extend(x)
                    break
            else:
                index += 1
                break

    return [sorted(set(l)) for l in seq]

sequence = [[1, 4, 9], [2, 3, 6], [4, 13, 50], [13, 23, 29], [2, 3, 7]]
print combineSequences(sequence)

>>> [[1, 4, 9, 13, 23, 29, 50], [2, 3, 6, 7]] 

sequence = [[3, 4], [1, 2], [1, 3]]
print combineSequences(sequence)

>>> [[1, 2, 3, 4]]

This solution operates under a different assumption than the one I made earlier, just to clarify. This simply joins lists that have a common number. If the idea, however, was to only have them separated by intervals of 1, see my other answer.

That's it!