जब तार घूर्णन के बराबर होते हैं

Question

मेरे पास बड़ी संख्या में तार हैं। मेरे उद्देश्यों के लिए, यदि दो एक दूसरे के घूर्णन होते हैं (उदाहरण के लिए '1234' '3412' के बराबर है) तो दो तार समकक्ष होते हैं।

पायथन में बिल्कुल एक बार (रोटेशन तक) प्रत्येक स्ट्रिंग को संसाधित करने का एक प्रभावी तरीका क्या है?

मैं कैसा दिखाई दे सकता है जैसे चाहते हैं की एक भोली कार्यान्वयन:

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

घुमाया तार के एक वर्ग का प्रतिनिधित्व करने के लिए एक विहित तरीका उठाओ (जैसे कोषगत कम से कम एक स्ट्रिंग के सभी संभव रोटेशन के बीच रोटेशन) केवल विहित प्रतिनिधित्व के साथ, और काम (canonicalization)।

उदाहरण के लिए:

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

शायद यह समझ में अपने string एक विशिष्ट मूल्य के, उदाहरण के लिए छोटी संभव रोटेशन को घुमाने के लिए बनाता है, की तुलना में उन छोटी से छोटी रोटेशन अद्वितीय हैं, और कर सकते थे आसानी से एक सेट में रखा जाना चाहिए।

यहां एक उदाहरण कार्यान्वयन है, और "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 

परिणाम:

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