6

2つの比較的短い（約3〜8要素）リストが互いにシフトされたコピーであるかどうかをチェックする最も効率的な（時間内の）方法は何ですか？もしそうなら、オフセットを決定して返しますか？

これが私が望むサンプルコードと出力です：

>>> def is_shifted_copy(list_one, list_two):
>>>     # TODO
>>>
>>> is_shifted_copy([1, 2, 3], [1, 2, 3])
0
>>> is_shifted_copy([1, 2, 3], [3, 1, 2])
1
>>> is_shifted_copy([1, 2, 3], [2, 3, 1])
2
>>> is_shifted_copy([1, 2, 3], [3, 2, 1])
None
>>> is_shifted_copy([1, 2, 3], [1])
None
>>> is_shifted_copy([1, 1, 2], [2, 1, 1])
1

リストに重複するエントリが含まれている可能性があります。複数のオフセットが有効な場合は、任意のオフセットを返します。

4

4 に答える 4

5

これは、2n回の反復でジョブを実行する単純な反復子バージョンです（nはリストの長さです）

import itertools

def is_shifted_copy(list1, list2):

    if len(list1) != len(list2):
        return False

    iterator = iter(list2)

    for i, item in enumerate(itertools.chain(list1, list1)):
        try:
            if item == iterator.next():
                continue
            else:
                iterator = iter(list2)
        except StopIteration:
            return i - len(list2)

    else:
        return False


print is_shifted_copy([1, 2, 3], [1, 2, 3]) #0
print is_shifted_copy([1, 2, 3], [3, 1, 2]) #2
print is_shifted_copy([1, 2, 3], [3, 2, 1]) #False
print is_shifted_copy([1, 2, 3], [2, 3, 1]) #1
print is_shifted_copy([1, 1, 2], [2, 1, 1]) #2
print is_shifted_copy([1, 2, 3], [1]) #False
print is_shifted_copy([1, 2, 1], [2, 1, 1]) #1
print is_shifted_copy([1, 1, 1], [1, 1, 1]) #0

そしてあなたの仕様から、

is_shifted_copy([1, 1, 2], [2, 1, 1])返してはいけない2？

于 2013-03-14T16:56:45.707 に答える
4

最初のリストの 2 つのコピーを検索すると、過度の連結を回避できます。

def is_shifted_copy(l1, l2):
    l1l1 = l1 * 2
    n = len(l1)
    return next((i for i in range(n) if l1l1[i:i + n] == l2), None)
于 2013-03-14T17:12:20.077 に答える
3

以下は、すべての可能な一致位置をチェックするNPEのソリューションの修正バージョンです。これは、thkang（およびecatmur）の巧妙なイテレータソリューションと比べて遜色ありません。

import itertools as IT

def is_shifted_copy_thkang(list1, list2):
    N = len(list1)
    if N != len(list2):
        return None
    elif N == 0:
        return 0
    next_item = iter(list2).next
    for i, item in enumerate(IT.chain(list1, list1)):
        try:
            if item == next_item():
                continue
            else:
                next_item = iter(list2).next
        except StopIteration:
            return -i % N
    else:
        return None

def is_shifted_copy_NPE(list1, list2):
    N = len(list1)
    if N != len(list2):
        return None
    elif N == 0:
        return 0

    pos = -1
    first = list1[0]
    while pos < N:
        try:
            pos = list2.index(first, pos+1)
        except ValueError:
            break
        if (list2 + list2)[pos:pos+N] == list1:
            return pos
    return None

def is_shifted_copy_ecatmur(l1, l2):
    l1l1 = l1 * 2
    n = len(l1)
    return next((-i % n for i in range(n) if l1l1[i:i + n] == l2), None)


tests = [
    # ([], [], 0),    
    ([1, 2, 3], [1, 2, 3], 0),
    ([1, 2, 3], [3, 1, 2], 1),
    ([1, 2, 3], [2, 3, 1], 2),
    ([1, 2, 3], [3, 2, 1], None),
    ([1, 2, 3], [1], None),
    ([1, 1, 2], [2, 1, 1], 1),
    ([1,2,3,1,3,2], [1,3,2,1,2,3], 3)
    ]

for list1, list2, answer in tests:
    print(list1, list2, answer)
    assert is_shifted_copy_thkang(list1, list2) == answer
    assert is_shifted_copy_NPE(list1, list2) == answer    
    assert is_shifted_copy_ecatmur(list1, list2) == answer        

In [378]: %timeit is_shifted_copy_thkang([1, 2, 3], [3, 1, 2])
100000 loops, best of 3: 3.5 us per loop

In [377]: %timeit is_shifted_copy_ecatmur([1, 2, 3], [3, 1, 2])
100000 loops, best of 3: 2.37 us per loop

In [379]: %timeit is_shifted_copy_NPE([1, 2, 3], [3, 1, 2])
1000000 loops, best of 3: 1.13 us per loop

注：の戻り値を変更して、is_shifted_copy_thkang3is_shifted_copy_ecatmurつのバージョンすべてが元の投稿のテストに合格するようにしました。

変更がある場合とない場合の関数のベンチマークを行ったところ、関数のパフォーマンスに大きな影響はないことがわかりました。

たとえば、return i：

In [384]: %timeit is_shifted_copy_thkang([1, 2, 3], [3, 1, 2])
100000 loops, best of 3: 3.38 us per loop

とreturn -i % N：

In [378]: %timeit is_shifted_copy_thkang([1, 2, 3], [3, 1, 2])
100000 loops, best of 3: 3.5 us per loop
于 2013-03-14T17:11:47.570 に答える
3

インデックスとスライスに基づくソリューションは次のとおりです。

>>> def is_shifted_copy(l1, l2):
    try:
        return [l1[-i:] + l1[:-i] for i in range(len(l1))].index(l2)
    except ValueError:
        return None

結果は期待どおりです。

>>> is_shifted_copy([1, 2, 3], [1, 2, 3])
0
>>> is_shifted_copy([1, 2, 3], [3, 1, 2])
1
>>> is_shifted_copy([1, 2, 3], [2, 3, 1])
2
>>> is_shifted_copy([1, 2, 3], [2, 1, 3])
None
于 2013-03-14T17:00:30.793 に答える