5

弦がたくさんあります。私の目的では、一方が他方の回転である場合、2つの文字列は同等です（たとえば、「1234」は「3412」と同等です）。

Pythonですべての文字列を1回だけ（回転まで）処理する効率的な方法は何ですか？

私が欲しいものの素朴な実装は次のようになります：

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
4

2 に答える 2

6

回転された文字列のクラスを表現する標準的な方法 (例: 文字列の可能なすべての回転の中で辞書編集的に最小の回転) を選択し、標準的な表現 ( 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)
于 2013-03-03T05:31:08.243 に答える
3

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'])
于 2013-03-03T04:36:53.857 に答える