在Python中，高效地确定两个列表是否是彼此的移位副本

Question

什么是检查两个相对较短的列表（大约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

列表中可能有重复的条目。如果有多个偏移量是有效的，请返回任何一个偏移量。

- devtk

---

如果列表很短，为什么要关心时间效率！ - Amine Hajyoussef

是的，如果速度那么重要的话，你应该使用另一种数据结构。 - Henry Gomersall

Answer 1

这里有一个简单的迭代器版本，可以在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 吗？

- thkang

---

我认为规范是一致的。但这只是一个细节问题。只要保持一致，我并不在意你返回1还是2。 - devtk

Answer 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)

- ecatmur

---

3行代码，没有try语句，性能非常接近其他解决方案的最佳表现。谢谢！ - devtk

请注意：这是一个O(n**2)时间复杂度和O(n)空间复杂度的问题。如果n很大，可能更倾向于使用@thkang的解决方案，它具有O(n)时间复杂度和O(1)空间复杂度。虽然对于n在3到8之间的情况并不重要。 - jfs

Answer 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

- Emmanuel

Answer 4

以下是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_thkang和is_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

With 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

- unutbu

---

为什么在i in range(n)的情况下要使用i % n？仅使用i就足够了。 - jfs

@J.F.Sebastian: 感谢您发现错误。我本打算是 -i％n for i in range（n）... （这样所有版本都可以通过相同的测试），但不知怎么出现了错别字。 - unutbu

在@thkang的版本中，您可以使用next_item = iter(list2).next。在else子句（空列表情况）中，它不应该返回0吗？ - jfs

@J.F.Sebastian：我将thkang的代码更改为使用next_item = iter(list2).next，因为这样可以稍微提高一些速度。我修复了thkang和NPE版本，使其在输入两个空列表时返回0，但是我不知道如何优雅地修改ecatmur的代码，因为它非常简洁，我不想碰它。计时结果基本保持不变。 - unutbu

Answer 5

有缺陷的解决方案

不幸的是，thkang提供的解决方案以及unutbu修改后的版本在一些简单的输入情况下会失败。

例如，对于列表[1, 2, 1]和[1, 1, 2]，我们（正确地）得到了一个整数结果：

>>> is_shifted_copy([1, 2, 1], [1, 1, 2])
2

然而，当交换参数时，我们得到了（不正确的）结果False：

>>> is_shifted_copy([1, 1, 2], [1, 2, 1])
False

同样，其他被移位复制的列表也无法正确处理：

>>> is_shifted_copy([1, 2, 2], [2, 1, 2])
False
>>> is_shifted_copy([1, 1, 2, 1], [1, 2, 1, 1])
False
>>> is_shifted_copy([1, 2, 1, 3, 3], [3, 1, 2, 1, 3])
False

为了理解这个问题的源头，让我重现一下thkang解决方案的当前版本（使用Python 3的修改调用next）。

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 == next(iterator):
                continue
            else:
                iterator = iter(list2)  # Reset iterator
        except StopIteration:
            return i - len(list2)
    else:
        return False

现在，对于像is_shifted_copy([1, 2, 2], [2, 1, 2])这样的调用，会发生以下情况：

i	item	next(iterator)	结果
0	1	2^	重置迭代器
1	2	2^	继续循环
2	2	1	重置迭代器
3	1	2^	重置迭代器
4	2	2^	继续循环
5	2	1	重置迭代器，返回False

返回list2的第一个元素。

正如我们所看到的，输入列表中重复的元素导致迭代器itertools.chain(list1, list1)在我们甚至没有机会到达list2的最后一个元素之前就被耗尽了。

可能的解决方法

如果我们坚持使用迭代器（例如为了防止复制潜在的大型输入列表），我们必须确保第一个列表的迭代器在我们可以与第二个列表的元素进行比较之前不会被耗尽。我目前唯一能想到的保证第一个迭代器不被耗尽的方法是创建所有可能的list1移位版本的新迭代器：

import itertools

def is_shifted_copy(list1, list2):
    length = len(list1)

    if len(list2) != length:
        return

    for i in range(length):
        iterator1 = itertools.islice(itertools.cycle(list1), i, i + length + 1)
        iterator2 = iter(list2)

        for item in iterator1:
            try:
                if item != next(iterator2):
                    break
            except StopIteration:
                return -i % length

    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], [3, 2, 1])
None
>>> is_shifted_copy([1, 2, 3], [1])
None
>>> is_shifted_copy([1, 1, 2], [2, 1, 1])
1
>>> is_shifted_copy([1, 2, 1], [1, 1, 2])
1
>>> is_shifted_copy([1, 1, 2], [1, 2, 1])
2
>>> is_shifted_copy([1, 2, 2], [2, 1, 2])
1
>>> is_shifted_copy([1, 1, 2, 1], [1, 2, 1, 1])
3
>>> is_shifted_copy([1, 2, 1, 3, 3], [3, 1, 2, 1, 3])
1

最好的情况下，上述算法在O(n)步骤内完成。对于大部分元素重复的输入列表，该算法的最坏情况是O(n^2)。

- Maurits Silvis