Сравнить два списка, чтобы увидеть, если один поворот на другой 2


Вторая попытка решить эту проблему вращения, осуществляет двусторонний очереди, как было предложено в комментарии к моей первой попытке. Так что я, наконец, проблема какая-то справедливость или есть ли лучшее решение? И все, что я могу и должен убирать? Я хотел бы поблагодарить всех из моего предыдущего поста за помощь и предложения!

'''
Attempt 2
Problem statement: Given 2 integer arrays, determine if the 2nd array is a rotated version of the 1st array. 
Ex. Original Array A={1,2,3,5,6,7,8} Rotated Array B={5,6,7,8,1,2,3} 

@author: Anonymous3.1415
'''

from collections import deque


def is_rotated(lst1, lst2):
    '''is lst2 a rotation of lst1 '''

    if len(lst1) != len(lst2):
        return False
    if lst1 == [] and lst2 == []:
        return True

    d_lst1 = deque(lst1)
    d_lst2 = deque(lst2)

    #rotate all possible rotations to find match
    for n in range(len(d_lst1)):
        d_lst2.rotate(n) 
        if d_lst2 == d_lst1:
            return True
        d_lst2.rotate(-n)
    return False

# rotation
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,7,1,2,3,4]
assert is_rotated(lst1, lst2)

# rotation with repeated numbers
lst1, lst2 = [1,2,3,4,6,4,7,1], [6,4,7,1,1,2,3,4]
assert is_rotated(lst1, lst2)

# different set
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
assert not is_rotated(lst1, lst2)

# equal
lst2 = lst1
assert is_rotated(lst1, lst2)

# empty
lst1, lst2 = [], []
assert is_rotated(lst1, lst2)

# 1 empty, 1 not empty
lst1, lst2 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)


156
6
задан 28 марта 2018 в 05:03 Источник Поделиться
Комментарии
1 ответ

Если вы сравниваете один из списков со всеми поворотов другой список, это займет в худшем случае $\тета(н^2)\$.

Например, если мы сделаем тестов такой:

from timeit import timeit
def test(n):
l1 = [0] * n
l2 = [0] * (n - 1) + [1]
return timeit(lambda:is_rotated(l1, l2), number=1)

тогда квадратичная runtime может быть ясно видно в тайминги:

>>> test(10**3)
0.009426131844520569
>>> test(10**4)
0.5701698779594153
>>> test(10**5)
57.70295810396783

Есть несколько способов решить эту задачу за линейное время:


  1. Поиск одного списка в конкатенации другой список с себя, используя алгоритм поиска, который имеет линейное время в худшем случае, например Кнута–Морриса–Пратта.

    Вот иллюстрация этого подхода, используя строки вместо списков:

    >>> a, b = 'basketwork', 'workbasket'
    >>> a in b + b
    True

  2. Найти лексикографически минимальный вращения каждого из списков, чтобы быть по сравнению (например, используя алгоритм Бута) и посмотреть, если результаты такие же.

2
ответ дан 28 марта 2018 в 09:03 Источник Поделиться