Quando le stringhe sono equivalenti fino alla rotazione

Question

Ho un numero elevato di stringhe. Per i miei scopi, due stringhe sono equivalenti se una è una rotazione dell'altra (ad esempio "1234" equivale a "3412").

Che cos'è un modo efficiente per elaborare ogni stringa esattamente una volta (fino alla rotazione) in Python?

Un ingenuo realizzazione di ciò che voglio potrebbe essere simile:

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

selezionamento un modo tradizionale per rappresentare una classe di stringhe ruotate (ad esempio la rotazione lexicographically meno tra tutte le possibili rotazioni di una stringa), e lavorare solo con le rappresentazioni canoniche (canonicalizzazione).

Ad esempio:

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

Forse ha senso per ruotare il string ad un valore specifico, ad esempio, più piccolo di rotazione possibile, di quelle più piccole rotazioni sono unici, e potrebbe essere facilmente messo in un set.

Ecco un'implementazione di esempio e "rotate_to_smallest" può probabilmente essere migliorato.

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 

risultati:

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