Какой может быть самый эффективный (с точки зрения времени) алгоритм для генерации анаграмм?

Question

Ниже приведен код, который я придумал, чтобы найти анаграммы данной строки, однако я обнаружил, что это очень медленно, когда строка очень большая. Что я могу сделать, чтобы сделать это быстрее? Есть ли другой алгоритм, который делает эту операцию быстрой?

def combinate(stri, comb,n,li):
    if stri == "":
        if comb not in li:
            li.append(comb)
        return
    for sdx, s in enumerate(stri):
        combinate(stri[0:sdx] + stri[sdx + 1:], comb+s,n)

Answer 1

Сортируйте символы в строке и в возможных анаграммах и сравнивайте отсортированные версии.

"task": "akst"
"skat": "akst"

Обратите внимание, что словарная запись по ключу "akst" может содержать список анаграмм в качестве значения

Answer 2

Если вы ищете "наиболее эффективный" по сложности времени, возьмите каждый термин и отсортируйте его символы по порядку, а затем сохраните их в (многозначной) карте. По заданному слову, для которого вы хотите найти анаграммы, также сортируйте его символы и ищите соответствующие записи на карте. Это будет O(1) для каждого поиска, хотя предварительное вычисление является линейным по общему количеству членов.

Я думаю, что можно с уверенностью сказать, что это наилучшая возможная временная сложность, но вы можете по-разному обрабатывать анаграммы из нескольких слов - это будет непрактично для комбинаций из нескольких слов (предварительное вычисление будет очень большим), так что вы, вероятно, захотите построить свою анаграмму по одному слову за раз.