Нормализовать строки, представляющие (комбинаторные) ожерелья

Question

Я пытаюсь сопоставить "necklaces" символов в Python, просматривая их линейные представления, для которых я использую обычные строки. Например, строки "AABC", "ABCA", "BCAA", "CAAB" все представляют такое же ожерелье (на фото).

Для того, чтобы получить обзор, я храню только один эквивалентных строк данного ожерелье в качестве «представителя». Что касается проверки того, что я сохранил ожерелье кандидата, мне нужна функция для нормализации любого заданного строкового представления. Как своего рода псевдо-код, я написал функцию в Python:

import collections 

def normalized(s): 
    q = collections.deque(s) 
    l = list() 
    l.append(''.join(q)) 
    for i in range(len(s)-1): 
     q.rotate(1) 
     l.append(''.join(q)) 
    l.sort() 
    return l[0] 

Для всех строковых представлений в приведенном выше примере ожерелье, эта функция возвращает "AABC", который приходит первым в алфавитном порядке.

Поскольку я относительно новичок в Python, мне интересно - если я начну внедрять приложение в Python - будет ли эта функция уже «достаточно хороша» для производственного кода? Другими словами: может ли опытный программист Python использовать эту функцию или есть очевидные недостатки?

Answer 1

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

def normalized(s): 
    L = [s[i:] + s[:i] for i in range(len(s))] 
    return sorted(L)[0] 

Этот код работает только со строками, без преобразования между очереди и строки, как в вашем коде. Быстрый тест времени показывает, что этот код запускается через 30-50% времени. Было бы интересно узнать длину s в вашем приложении. Поскольку все перестановки должны храниться временно len (s)^2 байта необходимы для временного списка L. Надеюсь, это не ограничение в вашем случае.

Edit: Сегодня я наткнулся на замечание, что если вы конкатенации исходную строку себе она будет содержать все повороты как подстроки. Таким образом, код будет:

def normalized4(s): 
    ss = s + s  # contains all rotations of s as substrings 
    n = len(s) 
    return min((ss[i:i+n] for i in range(n))) 

Это действительно будет работать быстрее, так как есть только одна оставшаяся конкатенация плюс n slicings. С помощью lengthlength от 10 до 10 ** 5 время выполнения составляет от 55% до 66% на моей машине по сравнению с версией min() с генератором.

Обратите внимание, что вы торгуете скоростью для потребления памяти (2x), что здесь не имеет значения, но может быть выполнено в другой настройке.

Answer 2

Как о чем-то вроде этого:

patterns = ['abc', 'bca', 'cab'] 
normalized = lambda p: ''.join(sorted(p)) 
normalized_patterns = set(normalized(p) for p in patterns) 

Пример вывода:

In [1]: normalized = lambda p: ''.join(sorted(p)) 

In [2]: normalized('abba') 
Out[2]: 'aabb' 

In [3]: normalized('CBAE') 
Out[3]: 'ABCE' 

Answer 3

Вы можете использовать min, а затем сортировка:

def normalized2(s): 
    return min((s[i:] + s[:i] for i in range(len(s)))) 

Но все-таки нужно скопировать len(s) раз снабжать струной, тетивой и т.п.. Более быстрый способ - отфильтровать начальные индексы наименьшего символа, пока вы не получите только один.Эффективно поиск наименьшего цикла:

def normalized3(s): 
    ssize=len(s) 
    minchar= min(s) 
    minindexes= [ i for i in range(ssize) if minchar == s[i] ] 
    for offset in range(1,ssize): 
     if len(minindexes) == 1 : 
      break 
     minchar= min(s[(i+offset)%ssize] for i in minindexes) 
     minindexes= [i for i in minindexes if minchar == s[(i+offset)%ssize]] 
    return s[minindexes[0]:] + s[:minindexes[0]] 

Для длинной строки это намного быстрее:

In [143]: loop = [ random.choice("abcd") for i in range(100) ] 
In [144]: timeit normalized(loop) 
1000 loops, best of 3: 237 µs per loop 
In [145]: timeit normalized2(loop) 
10000 loops, best of 3: 91.3 µs per loop 
In [146]: timeit normalized3(loop) 
100000 loops, best of 3: 16.9 µs per loop 

Но если у нас есть много повторений, этот метод не eficient:

In [147]: loop = "abcd" * 25 
In [148]: timeit normalized(loop) 
1000 loops, best of 3: 245 µs per loop 
In [149]: timeit normalized2(loop) 
100000 loops, best of 3: 18.8 µs per loop 
In [150]: timeit normalized3(loop) 
1000 loops, best of 3: 612 µs per loop 

Мы может также сканировать вперед строку, но я сомневаюсь, что она может быть любой быстрее, без какого-либо фантастического алгоритма.