Gdy łańcuchy są równoważne do obrotu

Question

Mam dużą liczbę ciągów. Dla moich celów dwa łańcuchy są równoważne, jeśli jedno jest obrotem drugiego (np. "1234" jest równoważne "3412").

Jaki jest skuteczny sposób przetwarzania każdego ciągu dokładnie raz (do obrotu) w języku Python?

Naiwny realizacja tego, co chcę, może wyglądać następująco:

class DuplicateException(Exception): pass 
seen = set() 
for s in my_strings: 
    try: 
    s2 = s+s 
    for t in seen: 

     # Slick method I picked up here in SO 
     # for checking whether one string is 
     # a rotation of another 
     if len(s) == len(t) and t in s2: 
     raise DuplicateException() 

    seen.add(s) 
    process(s) 
    except DuplicateException: pass 

Answer 1

Wybierz kanoniczny sposób reprezentują klasę obróconych łańcuchy (np leksykograficznie najmniej rotacja wśród wszystkich możliwych obrotów sznurku) i działa tylko z kanonicznych przedstawień (kanonizacja).

Na przykład:

def canonicalize(s): 
    return min(s[i:]+s[:i] for i in xrange(len(s))) 

canonical_strings = {canonicalize(s) for s in my_strings} 
for cs in canonical_strings: 
    process(cs) 

Answer 2

Może to ma sens, aby obrócić string do określonej wartości, na przykład najmniejszy możliwy obrót, niż te najmniejsze obroty są unikalne i mogą łatwo umieścić w zestawie.

Oto przykładowa implementacja i najprawdopodobniej można ulepszyć "rotate_to_smallest".

my_strings = ['1234', '123', '2341', '4312', '312', '56', '65', '1236'] 

def rotate_to_smallest(x): 
    smallest = x 
    for i in xrange(1, len(x)): 
     rotation = x[i :] + x[: i] 
     if rotation < smallest: 
      smallest = rotation 
    return smallest 

def unique_rotations(my_strings): 
    uniques = set(()) 
    for s in my_strings: 
     smallest_rotation = rotate_to_smallest(s) 
     if smallest_rotation not in uniques: 
      uniques.add(smallest_rotation) 
    return uniques 

Wynik:

>>> unique_rotations(my_strings) 
set(['1234', '56', '1243', '123', '1236'])