Определение того, является ли список вращением другого списка

Я ищу способ определить, хранят ли два списка одинаковые значения в одном и том же циклическом порядке, но начальная точка этого порядка может различаться между двумя списками.

Когда я говорю о циклическом упорядочении, я имею в виду, что последний элемент списка можно рассматривать как элемент непосредственно перед первым элементом списка.

Например:

['foo', 'bar', 'baz'] == ['bar', 'baz', 'foo']
>>> True

Это должно вывести True, потому что 'foo' находится перед 'bar', который стоит перед 'baz' по кругу для обоих списков.

['foo', 'bar', 'baz'] == ['bar', 'foo', 'baz']
>>> False

Это должно вывести False, потому что значения в списке не в том же порядке, независимо от того, сколько раз вы вращаете любой список.

Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения постов в Twitter с помощью Python, Tweepy и Flair
Анализ настроения текстовых сообщений может быть настолько сложным или простым, насколько вы его сделаете. Как и в любом ML-проекте, вы можете выбрать...
7 лайфхаков для начинающих Python-программистов
7 лайфхаков для начинающих Python-программистов
В этой статье мы расскажем о хитростях и советах по Python, которые должны быть известны разработчику Python.
Установка Apache Cassandra на Mac OS
Установка Apache Cassandra на Mac OS
Это краткое руководство по установке Apache Cassandra.
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
Сертификатная программа "Кванты Python": Бэктестер ансамблевых методов на основе ООП
В одном из недавних постов я рассказал о том, как я использую навыки количественных исследований, которые я совершенствую в рамках программы TPQ...
Создание персонального файлового хранилища
Создание персонального файлового хранилища
Вы когда-нибудь хотели поделиться с кем-то файлом, но он содержал конфиденциальную информацию? Многие думают, что электронная почта безопасна, но это...
Создание приборной панели для анализа данных на GCP - часть I
Создание приборной панели для анализа данных на GCP - часть I
Недавно я столкнулся с интересной бизнес-задачей - визуализацией сбоев в цепочке поставок лекарств, которую могут просматривать врачи и...
1
0
35
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Имея два списка, сначала утверждаем, что их длины равны. Если это не так, вам не нужно проверять элементы списка — отношение равенства не может выполняться.

Если они имеют одинаковую длину, создайте новый список, который будет первым списком, объединенным сам с собой. Если два списка циклически равны, то второй список будет подсписком первого списка, объединенным сам с собой.

Итак, мы можем сделать следующее:

def is_circular_equal(first, second):
    if len(first) != len(second):
        return False
        
    repeated_first = first + first
    
    for start_idx in range(len(first)):
        if repeated_first[start_idx:start_idx + len(first)] == second:
            return True
    return False

Если списки короткие, то вы можете просто сделать копию второго списка и повернуть ее так, чтобы первое слово первого списка стало первым словом второго списка, а затем сравнить два списка. Вращение списка просто с нарезкой.

Однако, если списки очень длинные, создание нового списка может оказаться слишком неэффективным. Этот простой цикл позволяет избежать копирования:

def cmp_ring(lst1, lst2):
    if len(lst1) != len(lst2):
        return False
    # For each occurrence of lst1[0] in lst2...
    for start in [idx for idx,val in enumerate(lst2) if val == lst1[0]]:
        for i in range(len(lst1)):
            if lst1[i] != lst2[(i + start) % len(lst2)]:
                break
        else:
            return True
    return False

Для полноты, вот метод, упомянутый в первом абзаце:

def cmp_ring(lst1, lst2):
    if len(lst1) != len(lst2): return False
    for start in [idx for idx,val in enumerate(lst2) if val == lst1[0]]:
        if lst1 == lst2[start:] + lst2[:start]: return True
    return False

не работают, когда значения повторяются в списке. Ваша функция возвращает false в этом примере: lst1 = ['a', 'a', 'b', 'c', 'b', 'b', 'b', 'a', 'c'], lst2 = ['а', 'с', 'а', 'а', 'б', 'с', 'б', 'б', 'б']

Guilhain 09.04.2022 19:39

Хорошая точка зрения. Обновлено для обработки повторов.

Johnny Mopp 09.04.2022 19:59

Другие вопросы по теме