0
\$\begingroup\$

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?

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Looks more like sorting rather then grouping \$\endgroup\$ Commented Sep 30, 2020 at 19:28
  • \$\begingroup\$ @OlvinRoght yes you are right. Let me rename. \$\endgroup\$ Commented Sep 30, 2020 at 21:19
  • \$\begingroup\$ What is the expected output of [1,3], [3,2], [1,2]? \$\endgroup\$
    – vnp
    Commented Sep 30, 2020 at 21:37
  • \$\begingroup\$ The output of [[1, 3], [3, 2], [1, 2]] is same. \$\endgroup\$ Commented Sep 30, 2020 at 21:46
  • \$\begingroup\$ should it not be [[1, 2], [1, 3], [3, 2]] since it is technically sort? \$\endgroup\$
    – hjpotter92
    Commented Oct 1, 2020 at 2:21

1 Answer 1

2
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This keeps [[1, 2], [2, 3], [999], [3]] as is, without moving [3] next to [2, 3]. I think it should. \$\endgroup\$ Commented Oct 4, 2020 at 1:42
  • \$\begingroup\$ @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. \$\endgroup\$
    – RootTwo
    Commented Oct 4, 2020 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.