python - write a function that receives a list of strings and return list of lists

Question

I can't find any similar solution for this specific question.

write a function that receives a list of strings and returns list of lists, each item in a group of lists has the same letters as the other items in that list (different order).

(abc, acb, aab, aba) --> ((abc, acb), (aab, aba))

this is the code that I have so far, but its not quite right, first of all its runs in O(n^2) and I need a solution in O(n) second, if there are more than 2 similarities the whole result isn't right.

def ex1(str_list: list = ()) -> list:
    result = []
        items = []
        for item in str_list:
            items.append(''.join(sorted(item)))
        for i in range(len(items)):
            for j in range(i):
                if items[i] == items[j]:
                    result.append([str_list[j], str_list[i]])

        return result

the solution I seek is using a dictionary and with time complexity of O(n) example for

input: ['abc', 'acb', 'aab', 'aba', 'bac']

Output: [['abc', 'acb', 'bac'], ['aab', 'aba']]

question from:https://stackoverflow.com/questions/65831397/write-a-function-that-receives-a-list-of-strings-and-return-list-of-lists

Answer 1

Here is a simple working example:

from collections import defaultdict
from typing import List, Tuple


def string_key(string: str) -> Tuple[str, ...]:
    """Returns a key which is unique on the characters in the string (ignoring ordering)."""
    return tuple(sorted(string))


def group_by_chars(data: List[str]) -> List[List[str]]:
    """Group strings by the characters they contain, regardless of order."""
    result = defaultdict(list)
    for value in data:
        key = string_key(value)
        result[key].append(value)
    return list(result.values())


assert group_by_chars(["abc", "acb", "aab", "aba"]) == [["abc", "acb"], ["aab", "aba"]]

The trick is defining a function which maps values which belong to the same group to the same key, and putting each value into a bucket based on the output of that key function.

Another approach would be to use sorted and itertools.groupby:

from itertools import groupby

from typing import List, Tuple


def string_key(string: str) -> Tuple[str, ...]:
    """Returns a key which is unique on the characters in the string (ignoring ordering)."""
    return tuple(sorted(string))


def alternate_group_by_chars(data: List[str]) -> List[List[str]]:
    result = []
    for _key, group in groupby(sorted(data, key=string_key), string_key):
        result.append(list(group))
    return result

However this will return results in a different order (due to the necessary sorted) and think its less readable.