sorting lists within list together given they have at least one common element

Question

I am grouping lists within list together given they have one element in common.

My input data is

[[1, 2], [3, 4], [5, 6], [1, 2, 7], [8, 2], [9, 5]]

My output is:

[[1, 2], [1, 2, 7], [8, 2], [3, 4], [5, 6], [9, 5]]

The code I am using to accomplish this is:

mylist = [[1, 2], [3, 4], [5, 6], [1, 2, 7], [8, 2], [9, 5]]
temp_result = list()
for i in range(len(mylist)):
 temp_result.append(mylist[i])
 for j in range(i + 1, len(mylist)):
 if (set(mylist[i]) & set(mylist[j])):
 temp_result.append(mylist[j])
result = []
for elem in temp_result:
 if elem not in result:
 result.append(elem)
print(result)

However, something tells me that this code can be improved a lot. Can someone please help me out?

• Olvin Roght: Looks more like sorting rather then grouping
• Ahmad Ismail: @OlvinRoght yes you are right. Let me rename.
• vnp: What is the expected output of [1,3], [3,2], [1,2]?
• Ahmad Ismail: The output of [[1, 3], [3, 2], [1, 2]] is same.
• hjpotter92: should it not be [[1, 2], [1, 3], [3, 2]] since it is technically sort?

Answer 1

Here's one way to approach the problem. There is a rule, or predicate, that determines whether list items should be grouped together. Use the predicate to partition the list into two parts, those that pass the predicate and those that fail. The ones that pass become grouped together in the result. The ones that fail get processed with a new predicate to see if any of them should be grouped. Repeat until there aren't any items left.

The code below matches the output of the code in the question. The predicate is true for any item that has an element in common with the first item in the sequence (the intersection is not empty).

The code is written to be understandable, not to be clever or concise.

def partition(predicate, sequence):
 """Return a list of sequence items that pass the predicate and a list
 of sequence items that do not pass the predicate.
 """
 pass_predicate = []
 fail_predicate = []
 for item in sequence:
 if predicate(item):
 pass_predicate.append(item)
 else:
 fail_predicate.append(item)
 return pass_predicate, fail_predicate
def group(sequence):
 """Groups items in the sequence that have elements in common.
 """
 result = []
 
 while sequence:
 predicate = set(sequence[0]).intersection
 passed, failed = partition(predicate, sequence)
 result.extend(passed)
 sequence = failed
 
 return result

• superb rain: This keeps [[1, 2], [2, 3], [999], [3]] as is, without moving [3] next to [2, 3]. I think it should.
• RootTwo: @superbrain, yeah the problem isn't well specified. As a counter example to yours, for input [[1, 2], [3, 4], [5, 6], [1, 2, 7], [8, 2], [9, 5], [7, 10]] the original code keeps the [7, 10] at the end instead of grouping it with the [1, 2, 7]. Is it supposed to look for common elements with the union of all items in the group? or just with the first item in the group? You think the former, I thought the later, and the original code does neither.