Dizeler rotasyona eşdeğer olduğunda

Question

Çok sayıda dizim var. Benim amaçlarım için biri diğerinin bir rotasyonu ise iki dizgenin karşılığıdır (örneğin '1234', '3412' değerine eşittir).

Her dizeyi Python'da tam olarak bir kez (dönüşüme kadar) işlemenin verimli bir yolu nedir?

ben gibi görünebilir ne istediğini Saf bir uygulama: O en küçük rotasyonlar benzersizdir daha

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

(örn tüm olası bir dize rotasyonlar arasında sözlük sırasında en az rotasyon) sadece kanonik temsiller ile ve çalışma (döndürülmüş dizeleri sınıfını temsil edecek bir kanonik yol seç kanonikleştirme). Örneğin

: Bir * çok * daha basit bu kodu yapabilirsiniz

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

Belki senin string belirli bir değere, örneğin mümkün olan en küçük rotasyon döndürmek için mantıklı ve could kolayca bir küme koymak.

İşte bir örnek uygulama ve "rotate_to_smallest" büyük olasılıkla geliştirilebilir.

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 

Sonuç:

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