Como verificar se duas listas são circularmente idênticas em Python

Por exemplo, eu tenho listas:

a[0] = [1, 1, 1, 0, 0]
a[1] = [1, 1, 0, 0, 1]
a[2] = [0, 1, 1, 1, 0]
# and so on

Eles parecem ser diferentes, mas se supõe que o início e o fim estão conectados, eles são circularmente idênticos.

O problema é que cada lista que tenho tem um comprimento de 55 e contém apenas três e 52 zeros. Sem condição circular, existem 26.235 (55 escolha 3) listas. No entanto, se a condição 'circular' existir, haverá um grande número de listas circularmente idênticas

Atualmente, verifico circularmente a identidade, seguindo:

def is_dup(a, b):
    for i in range(len(a)):
        if a == list(numpy.roll(b, i)): # shift b circularly by i
            return True
    return False

Esta função requer 55 operações de mudança cíclica na pior das hipóteses. E existem 26.235 listas para serem comparadas entre si. Em resumo, preciso de 55 * 26.235 * (26.235 - 1) / 2 = 18.926.847.225 cálculos. São cerca de 20 Giga!

Existe alguma maneira de fazer isso com menos cálculos? Ou algum tipo de dado que suporte circular ?

Primeiramente, isso pode ser feito em O(n)termos do tamanho da lista. Você pode notar que, se duplicar sua lista duas vezes ( [1, 2, 3]), [1, 2, 3, 1, 2, 3]então sua nova lista conterá definitivamente todas as listas cíclicas possíveis.

Então, tudo que você precisa é verificar se a lista que você está pesquisando está dentro de 2 vezes a sua lista inicial. Em python, você pode conseguir isso da seguinte maneira (assumindo que os comprimentos sejam iguais).

list1 = [1, 1, 1, 0, 0]
list2 = [1, 1, 0, 0, 1]
print ' '.join(map(str, list2)) in ' '.join(map(str, list1 * 2))

Alguma explicação sobre o meu oneliner: list * 2combinará uma lista consigo mesma, map(str, [1, 2])converterá todos os números em string e ' '.join()converterá array ['1', '2', '111']em uma string '1 2 111'.

Conforme apontado por algumas pessoas nos comentários, o oneliner pode potencialmente fornecer alguns falsos positivos, de modo a cobrir todos os possíveis casos extremos:

def isCircular(arr1, arr2):
    if len(arr1) != len(arr2):
        return False

    str1 = ' '.join(map(str, arr1))
    str2 = ' '.join(map(str, arr2))
    if len(str1) != len(str2):
        return False

    return str1 in str2 + ' ' + str2

PS1 ao falar sobre complexidade de tempo, vale notar que O(n)será alcançado se a substring puder ser encontrada a O(n)tempo. Nem sempre é assim e depende da implementação em seu idioma ( embora potencialmente possa ser feito de forma linear tempo KMP, por exemplo).

PS2 para pessoas que estão com medo de operação de cordas e, devido a esse fato, pensam que a resposta não é boa. O que é importante é complexidade e velocidade. Esse algoritmo é potencialmente executado no O(n)tempo e no O(n)espaço, o que o torna muito melhor do que qualquer coisa no O(n^2)domínio. Para ver isso sozinho, você pode executar uma pequena referência (cria uma lista aleatória que aparece o primeiro elemento e o anexa ao final, criando assim uma lista cíclica. Você é livre para fazer suas próprias manipulações)

from random import random
bigList = [int(1000 * random()) for i in xrange(10**6)]
bigList2 = bigList[:]
bigList2.append(bigList2.pop(0))

# then test how much time will it take to come up with an answer
from datetime import datetime
startTime = datetime.now()
print isCircular(bigList, bigList2)
print datetime.now() - startTime    # please fill free to use timeit, but it will give similar results

0,3 segundos na minha máquina. Não é muito longo. Agora tente comparar isso com as O(n^2)soluções. Enquanto o compara, você pode viajar dos EUA para a Austrália (provavelmente por um navio de cruzeiro)

Não conhecedor o suficiente em Python para responder a isso na linguagem solicitada, mas em C / C ++, dados os parâmetros de sua pergunta, eu converteria os zeros e uns em bits e os empurraria para os bits menos significativos de um uint64_t. Isso permitirá que você compare todos os 55 bits de uma só vez - 1 relógio.

Muito rápido, e tudo se encaixa nos caches no chip (209.880 bytes). O suporte de hardware para mudar todos os 55 membros da lista para a direita simultaneamente está disponível apenas nos registros de uma CPU. O mesmo vale para comparar todos os 55 membros simultaneamente. Isso permite um mapeamento 1 por 1 do problema para uma solução de software. (e usando os registros SIMD / SSE de 256 bits, até 256 membros, se necessário) Como resultado, o código é imediatamente óbvio para o leitor.

Você pode implementar isso em Python, mas não o conheço o suficiente para saber se isso é possível ou qual pode ser o desempenho.

Depois de dormir, algumas coisas se tornaram óbvias, e tudo para melhor.

1.) É tão fácil girar a lista vinculada circularmente usando bits que o truque muito inteligente de Dali não é necessário. Dentro de um registro de 64 bits, a troca de bits padrão realizará a rotação de maneira muito simples e na tentativa de tornar tudo mais amigável ao Python, usando aritmética em vez de operações de bits.

2.) A troca de bits pode ser realizada facilmente usando a divisão por 2.

3.) Verificar o final da lista como 0 ou 1 pode ser facilmente realizado pelo módulo 2.

4.) "Mover" um 0 para o início da lista a partir da cauda pode ser feito dividindo-se por 2. Isso porque se o zero fosse realmente movido, tornaria o 55º bit falso, o que já é feito sem absolutamente nada.

5.) "Mover" um 1 para o topo da lista a partir da cauda pode ser feito dividindo por 2 e adicionando 18.014.398.509.481.984 - que é o valor criado pela marcação do 55º bit como verdadeiro e o restante como falso.

6.) Se uma comparação da âncora e do uint64_t composto for TRUE após uma rotação, interrompa e retorne TRUE.

Eu converteria toda a matriz de listas em uma matriz de uint64_ts logo no início, para evitar a conversão repetida.

Depois de passar algumas horas tentando otimizar o código, estudando a linguagem assembly, consegui economizar 20% do tempo de execução. Devo acrescentar que o compilador O / S e MSVC também foi atualizado no meio do dia ontem. Por qualquer motivo, a qualidade do código que o compilador C produziu melhorou drasticamente após a atualização (15/11/2014). O tempo de execução agora é de ~ 70 relógios, 17 nanossegundos para compor e comparar um anel de ancoragem com todas as 55 voltas de um anel de teste e o NxN de todos os anéis contra todos os outros é feito em 12,5 segundos .

Esse código é tão restrito, com exceção de quatro registros, sem fazer nada em 99% do tempo. A linguagem assembly corresponde ao código C quase linha por linha. Muito fácil de ler e entender. Um ótimo projeto de montagem se alguém estivesse ensinando isso a si mesmo.

O hardware é Hazwell i7, MSVC de 64 bits, otimizações completas.

#include "stdafx.h"
#include "stdafx.h"
#include <string>
#include <memory>
#include <stdio.h>
#include <time.h>

const uint8_t  LIST_LENGTH = 55;    // uint_8 supports full witdth of SIMD and AVX2
// max left shifts is 32, so must use right shifts to create head_bit
const uint64_t head_bit = (0x8000000000000000 >> (64 - LIST_LENGTH)); 
const uint64_t CPU_FREQ = 3840000000;   // turbo-mode clock freq of my i7 chip

const uint64_t LOOP_KNT = 688275225; // 26235^2 // 1000000000;

// ----------------------------------------------------------------------------
__inline uint8_t is_circular_identical(const uint64_t anchor_ring, uint64_t test_ring)
{
    // By trial and error, try to synch 2 circular lists by holding one constant
    //   and turning the other 0 to LIST_LENGTH positions. Return compare count.

    // Return the number of tries which aligned the circularly identical rings, 
    //  where any non-zero value is treated as a bool TRUE. Return a zero/FALSE,
    //  if all tries failed to find a sequence match. 
    // If anchor_ring and test_ring are equal to start with, return one.

    for (uint8_t i = LIST_LENGTH; i;  i--)
    {
        // This function could be made bool, returning TRUE or FALSE, but
        // as a debugging tool, knowing the try_knt that got a match is nice.
        if (anchor_ring == test_ring) {  // test all 55 list members simultaneously
            return (LIST_LENGTH +1) - i;
        }

        if (test_ring % 2) {    //  ring's tail is 1 ?
            test_ring /= 2;     //  right-shift 1 bit
            // if the ring tail was 1, set head to 1 to simulate wrapping
            test_ring += head_bit;      
        }   else    {           // ring's tail must be 0
            test_ring /= 2;     // right-shift 1 bit
            // if the ring tail was 0, doing nothing leaves head a 0
        }
    }
    // if we got here, they can't be circularly identical
    return 0;
}
// ----------------------------------------------------------------------------
    int main(void)  {
        time_t start = clock();
        uint64_t anchor, test_ring, i,  milliseconds;
        uint8_t try_knt;

        anchor = 31525197391593472; // bits 55,54,53 set true, all others false
        // Anchor right-shifted LIST_LENGTH/2 represents the average search turns
        test_ring = anchor >> (1 + (LIST_LENGTH / 2)); //  117440512; 

        printf("\n\nRunning benchmarks for %llu loops.", LOOP_KNT);
        start = clock();
        for (i = LOOP_KNT; i; i--)  {
            try_knt = is_circular_identical(anchor, test_ring);
            // The shifting of test_ring below is a test fixture to prevent the 
            //  optimizer from optimizing the loop away and returning instantly
            if (i % 2) {
                test_ring /= 2;
            }   else  {
                test_ring *= 2;
            }
        }
        milliseconds = (uint64_t)(clock() - start);
        printf("\nET for is_circular_identical was %f milliseconds."
                "\n\tLast try_knt was %u for test_ring list %llu", 
                        (double)milliseconds, try_knt, test_ring);

        printf("\nConsuming %7.1f clocks per list.\n",
                (double)((milliseconds * (CPU_FREQ / 1000)) / (uint64_t)LOOP_KNT));

        getchar();
        return 0;
}

Lendo nas entrelinhas, parece que você está tentando enumerar um representante de cada classe de equivalência circular de strings com 3 e 52 zeros. Vamos mudar de uma representação densa para uma esparsa (conjunto de três números range(55)). Nesta representação, o deslocamento circular de spor ké dado pela compreensão set((i + k) % 55 for i in s). O representante mínimo lexicographic em uma classe contém sempre a posição 0. Dado um conjunto da forma {0, i, j}com 0 < i < j, os outros candidatos para mínima da classe são {0, j - i, 55 - i}e {0, 55 - j, 55 + i - j}. Portanto, precisamos (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j))que o original seja mínimo. Aqui está um código de enumeração.

def makereps():
    reps = []
    for i in range(1, 55 - 1):
        for j in range(i + 1, 55):
            if (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j)):
                reps.append('1' + '0' * (i - 1) + '1' + '0' * (j - i - 1) + '1' + '0' * (55 - j - 1))
    return reps

Repita a primeira matriz e use o algoritmo Z (O (n) time) para encontrar a segunda matriz dentro da primeira.

(Nota: você não precisa copiar fisicamente a primeira matriz. Você pode apenas girar durante a correspondência.)

O bom do algoritmo Z é que ele é muito simples comparado ao KMP, BM etc.
No entanto, se você estiver se sentindo ambicioso, poderá fazer a correspondência de strings em tempo linear e espaço constante - strstrpor exemplo, faz isso. Implementá-lo seria mais doloroso, no entanto.

Seguindo a solução muito inteligente de Salvador Dali, a melhor maneira de lidar com isso é garantir que todos os elementos tenham o mesmo comprimento, assim como os dois LISTAS tenham o mesmo comprimento.

def is_circular_equal(lst1, lst2):
    if len(lst1) != len(lst2):
        return False
    lst1, lst2 = map(str, lst1), map(str, lst2)
    len_longest_element = max(map(len, lst1))
    template = "{{:{}}}".format(len_longest_element)
    circ_lst = " ".join([template.format(el) for el in lst1]) * 2
    return " ".join([template.format(el) for el in lst2]) in circ_lst

Não há pista se isso é mais rápido ou mais lento que a solução de regex recomendada por AshwiniChaudhary na resposta de Salvador Dali, que diz:

import re

def is_circular_equal(lst1, lst2):
    if len(lst2) != len(lst2):
        return False
    return bool(re.search(r"\b{}\b".format(' '.join(map(str, lst2))),
                          ' '.join(map(str, lst1)) * 2))

Dado que você precisa fazer tantas comparações, vale a pena dar uma passada inicial em suas listas para convertê-las em algum tipo de forma canônica que pode ser facilmente comparada?

Você está tentando obter um conjunto de listas circularmente exclusivas? Nesse caso, você pode jogá-los em um conjunto depois de converter em tuplas.

def normalise(lst):
    # Pick the 'maximum' out of all cyclic options
    return max([lst[i:]+lst[:i] for i in range(len(lst))])

a_normalised = map(normalise,a)
a_tuples = map(tuple,a_normalised)
a_unique = set(a_tuples)

Desculpas a David Eisenstat por não ter encontrado sua resposta semelhante.

Você pode rolar uma lista como esta:

list1, list2 = [0,1,1,1,0,0,1,0], [1,0,0,1,0,0,1,1]

str_list1="".join(map(str,list1))
str_list2="".join(map(str,list2))

def rotate(string_to_rotate, result=[]):
    result.append(string_to_rotate)
    for i in xrange(1,len(string_to_rotate)):
        result.append(result[-1][1:]+result[-1][0])
    return result

for x in rotate(str_list1):
    if cmp(x,str_list2)==0:
        print "lists are rotationally identical"
        break

Primeiro converter todos os de sua lista elementos (em uma cópia, se necessário) para que versão rotacionada que é lexicamente maior.

Em seguida, classifique a lista de listas resultante (mantendo um índice na posição da lista original) e unifique a lista classificada, marcando todas as duplicatas na lista original, conforme necessário.

Pegando carona na observação do @ SalvadorDali ao procurar correspondências de a em qualquer fatia de tamanho a em b + b, aqui está uma solução usando apenas operações de lista.

def rollmatch(a,b):
    bb=b*2
    return any(not any(ax^bbx for ax,bbx in zip(a,bb[i:])) for i in range(len(a)))

l1 = [1,0,0,1]
l2 = [1,1,0,0]
l3 = [1,0,1,0]

rollmatch(l1,l2)  # True
rollmatch(l1,l3)  # False

Segunda abordagem: [excluído]

Não é uma resposta completa e independente, mas no tópico de otimizar reduzindo comparações, eu também estava pensando em representações normalizadas.

Ou seja, se o alfabeto de entrada for {0, 1}, você poderá reduzir significativamente o número de permutações permitidas. Gire a primeira lista para uma forma (pseudo-) normalizada (dada a distribuição em sua pergunta, eu escolheria uma em que um dos 1 bits esteja na extrema esquerda e um dos 0 bits na extrema direita). Agora, antes de cada comparação, gire sucessivamente a outra lista pelas posições possíveis com o mesmo padrão de alinhamento.

Por exemplo, se você tiver um total de quatro bits 1, pode haver no máximo 4 permutações com esse alinhamento e se você tiver grupos de 1 bits adjacentes, cada bit adicional nesse cluster reduzirá a quantidade de posições.

List 1   1 1 1 0 1 0

List 2   1 0 1 1 1 0  1st permutation
         1 1 1 0 1 0  2nd permutation, final permutation, match, done

Isso generaliza para alfabetos maiores e diferentes padrões de alinhamento; o principal desafio é encontrar uma boa normalização com apenas algumas representações possíveis. Idealmente, seria uma normalização adequada, com uma única representação única, mas, dado o problema, não acho possível.

Aprofundando a resposta do RocketRoy: converta todas as suas listas antecipadamente em números de 64 bits não assinados. Para cada lista, gire esses 55 bits para encontrar o menor valor numérico.

Agora você tem um único valor de 64 bits não assinado para cada lista que você pode comparar diretamente com o valor das outras listas. A função is_circular_identical () não é mais necessária.

(Em essência, você cria um valor de identidade para suas listas que não é afetado pela rotação dos elementos das listas). Isso funcionaria mesmo se você tivesse um número arbitrário em suas listas.

Essa é a mesma idéia de Salvador Dali, mas não precisa da conversão de strings. Atrás está a mesma idéia de recuperação do KMP para evitar uma inspeção de turno impossível. Eles chamam apenas KMPModified (lista1, lista2 + lista2).

    public class KmpModified
    {
        public int[] CalculatePhi(int[] pattern)
        {
            var phi = new int[pattern.Length + 1];
            phi[0] = -1;
            phi[1] = 0;

            int pos = 1, cnd = 0;
            while (pos < pattern.Length)
                if (pattern[pos] == pattern[cnd])
                {
                    cnd++;
                    phi[pos + 1] = cnd;
                    pos++;
                }
                else if (cnd > 0)
                    cnd = phi[cnd];
                else
                {
                    phi[pos + 1] = 0;
                    pos++;
                }

            return phi;
        }

        public IEnumerable<int> Search(int[] pattern, int[] list)
        {
            var phi = CalculatePhi(pattern);

            int m = 0, i = 0;
            while (m < list.Length)
                if (pattern[i] == list[m])
                {
                    i++;
                    if (i == pattern.Length)
                    {
                        yield return m - i + 1;
                        i = phi[i];
                    }
                    m++;
                }
                else if (i > 0)
                {
                    i = phi[i];
                }
                else
                {
                    i = 0;
                    m++;
                }
        }

        [Fact]
        public void BasicTest()
        {
            var pattern = new[] { 1, 1, 10 };
            var list = new[] {2, 4, 1, 1, 1, 10, 1, 5, 1, 1, 10, 9};
            var matches = Search(pattern, list).ToList();

            Assert.Equal(new[] {3, 8}, matches);
        }

        [Fact]
        public void SolveProblem()
        {
            var random = new Random();
            var list = new int[10];
            for (var k = 0; k < list.Length; k++)
                list[k]= random.Next();

            var rotation = new int[list.Length];
            for (var k = 1; k < list.Length; k++)
                rotation[k - 1] = list[k];
            rotation[rotation.Length - 1] = list[0];

            Assert.True(Search(list, rotation.Concat(rotation).ToArray()).Any());
        }
    }

Espero que esta ajuda!

Simplificando o problema

• O problema consiste na lista de itens solicitados
• O domínio do valor é binário (0,1)
• Podemos reduzir o problema mapeando 1s consecutivos em uma contagem
• e 0s consecutivos em uma contagem negativa

Exemplo

A = [ 1, 1, 1, 0, 0, 1, 1, 0 ]
B = [ 1, 1, 0, 1, 1, 1, 0, 0 ]
~
A = [ +3, -2, +2, -1 ]
B = [ +2, -1, +3, -2 ]

• Esse processo exige que o primeiro e o último item sejam diferentes
• Isso reduzirá a quantidade de comparações gerais

Processo de Verificação

• Se assumirmos que eles são duplicados, podemos assumir o que estamos procurando
• Basicamente, o primeiro item da primeira lista deve existir em algum lugar da outra lista
• Seguido pelo que é seguido na primeira lista e da mesma maneira
• Os itens anteriores devem ser os últimos itens da primeira lista
• Por ser circular, o pedido é o mesmo

A aderência

• A questão aqui é por onde começar, tecnicamente conhecido como lookup elook-ahead
• Vamos apenas verificar onde o primeiro elemento da primeira lista existe através da segunda lista
• A probabilidade de elemento frequente é menor, pois mapeamos as listas em histogramas

Pseudo-código

FUNCTION IS_DUPLICATE (LIST L1, LIST L2) : BOOLEAN

    LIST A = MAP_LIST(L1)
    LIST B = MAP_LIST(L2)

    LIST ALPHA = LOOKUP_INDEX(B, A[0])

    IF A.SIZE != B.SIZE
       OR COUNT_CHAR(A, 0) != COUNT_CHAR(B, ALPHA[0]) THEN

        RETURN FALSE

    END IF

    FOR EACH INDEX IN ALPHA

        IF ALPHA_NGRAM(A, B, INDEX, 1) THEN

            IF IS_DUPLICATE(A, B, INDEX) THEN

                RETURN TRUE

            END IF

        END IF

    END FOR

    RETURN FALSE

END FUNCTION

FUNCTION IS_DUPLICATE (LIST L1, LIST L2, INTEGER INDEX) : BOOLEAN

    INTEGER I = 0

    WHILE I < L1.SIZE DO

        IF L1[I] != L2[(INDEX+I)%L2.SIZE] THEN

            RETURN FALSE

        END IF

        I = I + 1

    END WHILE

    RETURN TRUE

END FUNCTION

Funções

• MAP_LIST(LIST A):LIST MAPA DE ELEMENTOS CONSQUETIVOS COMO CONTA EM UMA NOVA LISTA

• LOOKUP_INDEX(LIST A, INTEGER E):LISTLISTA DE RETORNO DE ÍNDICES EM QUE O ELEMENTO EEXISTE NA LISTAA

• COUNT_CHAR(LIST A , INTEGER E):INTEGERCONTAR QUANTAS VEZES UM ELEMENTO EOCORRE EM UMA LISTAA

• ALPHA_NGRAM(LIST A,LIST B,INTEGER I,INTEGER N):BOOLEANVERIFIQUE SE B[I]É EQUIVALENTE A[0] N-GRAMEM DUAS DIREÇÕES

Finalmente

Se o tamanho da lista for muito grande ou se o elemento do qual estamos começando a verificar o ciclo for frequentemente alto, podemos fazer o seguinte:

• Procure o item menos frequente na primeira lista para começar

• aumente o parâmetro n-gram N para diminuir a probabilidade de passar por uma verificação linear

Uma "forma canônica" eficiente e rápida de calcular para as listas em questão pode ser derivada como:

• Conte o número de zeros entre eles (ignorando o contorno), para obter três números.
• Gire os três números para que o maior número seja o primeiro.
• O primeiro número ( a) deve estar entre 18e 52(inclusive). Recodifique-o como entre 0e34 .
• O segundo número ( b) deve estar entre 0e 26, mas não importa muito.
• Largue o terceiro número, pois é justo 52 - (a + b)e não adiciona informação

A forma canônica é o número inteiro b * 35 + a, que está entre 0e 936(inclusive), que é bastante compacto (existem 477listas circularmente exclusivas no total).

Eu escrevi uma solução simples que compara as duas listas e apenas aumenta (e envolve) o índice do valor comparado para cada iteração.

Como eu não conheço bem python, escrevi em Java, mas é realmente simples, portanto deve ser fácil adaptá-lo a qualquer outra linguagem.

Por isso, você também pode comparar listas de outros tipos.

public class Main {

    public static void main(String[] args){
        int[] a = {0,1,1,1,0};
        int[] b = {1,1,0,0,1};

        System.out.println(isCircularIdentical(a, b));
    }

    public static boolean isCircularIdentical(int[] a, int[]b){
        if(a.length != b.length){
            return false;
        }

        //The outer loop is for the increase of the index of the second list
        outer:
        for(int i = 0; i < a.length; i++){
            //Loop trough the list and compare each value to the according value of the second list
            for(int k = 0; k < a.length; k++){
                // I use modulo length to wrap around the index
                if(a[k] != b[(k + i) % a.length]){
                    //If the values do not match I continue and shift the index one further
                    continue outer;
                }
            }
            return true;
        }
        return false;
    }
}

Como outros já mencionaram, depois de encontrar a rotação normalizada de uma lista, você pode compará-las.

Heres algum código de trabalho que faz isso, o método básico é encontrar uma rotação normalizada para cada lista e comparar:

• Calcule um índice de rotação normalizado em cada lista.
• Passe o loop pelas duas listas com seus desvios, comparando cada item e retornando se não corresponderem.

Note que este método é que não depende de números, você pode passar listas de strings (quaisquer valores que possam ser comparados).

Em vez de fazer uma pesquisa de lista na lista, sabemos que queremos que a lista comece com o valor mínimo - para que possamos percorrer os valores mínimos, pesquisando até encontrar qual deles tem os menores valores sucessivos, armazenando-o para comparações adicionais até que tenhamos o melhor.

Existem muitas oportunidades para sair mais cedo ao calcular o índice, detalhes sobre algumas otimizações.

• Pule a busca pelo melhor valor mínimo quando houver apenas um.
• Pule a pesquisa de valores mínimos quando o anterior também for um valor mínimo (nunca será uma correspondência melhor).
• Pule a pesquisa quando todos os valores forem iguais.
• Falha no início quando as listas têm valores mínimos diferentes.
• Use comparação regular quando as compensações corresponderem.
• Ajuste as compensações para evitar agrupar os valores do índice em uma das listas durante a comparação.

Observe que no Python uma pesquisa de lista na lista pode muito bem ser mais rápida, no entanto, eu estava interessado em encontrar um algoritmo eficiente - que também pudesse ser usado em outros idiomas. Além disso, há algumas vantagens em evitar criar novas listas.

def normalize_rotation_index(ls, v_min_other=None):
    """ Return the index or -1 (when the minimum is above `v_min_other`) """

    if len(ls) <= 1:
        return 0

    def compare_rotations(i_a, i_b):
        """ Return True when i_a is smaller.
            Note: unless there are large duplicate sections of identical values,
            this loop will exit early on.
        """
        for offset in range(1, len(ls)):
            v_a = ls[(i_a + offset) % len(ls)]
            v_b = ls[(i_b + offset) % len(ls)]
            if v_a < v_b:
                return True
            elif v_a > v_b:
                return False
        return False

    v_min = ls[0]
    i_best_first = 0
    i_best_last = 0
    i_best_total = 1
    for i in range(1, len(ls)):
        v = ls[i]
        if v_min > v:
            v_min = v
            i_best_first = i
            i_best_last = i
            i_best_total = 1
        elif v_min == v:
            i_best_last = i
            i_best_total += 1

    # all values match
    if i_best_total == len(ls):
        return 0

    # exit early if we're not matching another lists minimum
    if v_min_other is not None:
        if v_min != v_min_other:
            return -1
    # simple case, only one minimum
    if i_best_first == i_best_last:
        return i_best_first

    # otherwise find the minimum with the lowest values compared to all others.
    # start looking after the first we've found
    i_best = i_best_first
    for i in range(i_best_first + 1, i_best_last + 1):
        if (ls[i] == v_min) and (ls[i - 1] != v_min):
            if compare_rotations(i, i_best):
                i_best = i

    return i_best


def compare_circular_lists(ls_a, ls_b):
    # sanity checks
    if len(ls_a) != len(ls_b):
        return False
    if len(ls_a) <= 1:
        return (ls_a == ls_b)

    index_a = normalize_rotation_index(ls_a)
    index_b = normalize_rotation_index(ls_b, ls_a[index_a])

    if index_b == -1:
        return False

    if index_a == index_b:
        return (ls_a == ls_b)

    # cancel out 'index_a'
    index_b = (index_b - index_a)
    if index_b < 0:
        index_b += len(ls_a)
    index_a = 0  # ignore it

    # compare rotated lists
    for i in range(len(ls_a)):
        if ls_a[i] != ls_b[(index_b + i) % len(ls_b)]:
            return False
    return True


assert(compare_circular_lists([0, 9, -1, 2, -1], [-1, 2, -1, 0, 9]) == True)
assert(compare_circular_lists([2, 9, -1, 0, -1], [-1, 2, -1, 0, 9]) == False)
assert(compare_circular_lists(["Hello" "Circular", "World"], ["World", "Hello" "Circular"]) == True)
assert(compare_circular_lists(["Hello" "Circular", "World"], ["Circular", "Hello" "World"]) == False)

Veja: esse trecho para algumas mais testes / exemplos.

Você pode verificar se uma lista A é igual a uma mudança cíclica da lista B no tempo esperado de O (N) com bastante facilidade.

Eu usaria uma função de hash polinomial para calcular o hash da lista A e todos os turnos cíclicos da lista B. Onde um turno da lista B tem o mesmo hash da lista A, comparo os elementos reais para ver se são iguais .

A razão disso é rápido é que, com funções de hash polinomial (que são extremamente comuns!), É possível calcular o hash de cada mudança cíclica da anterior em tempo constante, para que você possa calcular hashes para todas as mudanças cíclicas em O ( N) tempo.

Funciona assim:

Digamos que B tenha N elementos, então o hash de B usando P primo é:

Hb=0;
for (i=0; i<N ; i++)
{
    Hb = Hb*P + B[i];
}

Essa é uma maneira otimizada de avaliar um polinômio em P e é equivalente a:

Hb=0;
for (i=0; i<N ; i++)
{
    Hb += B[i] * P^(N-1-i);  //^ is exponentiation, not XOR
}

Observe como todo B [i] é multiplicado por P ^ (N-1-i). Se deslocarmos B para a esquerda por 1, todos os B [i] serão multiplicados por um P extra, exceto o primeiro. Como a multiplicação distribui pela adição, podemos multiplicar todos os componentes de uma só vez multiplicando todo o hash e, em seguida, fixar o fator para o primeiro elemento.

O hash do deslocamento esquerdo de B é apenas

Hb1 = Hb*P + B[0]*(1-(P^N))

O segundo turno esquerdo:

Hb2 = Hb1*P + B[1]*(1-(P^N))

e assim por diante...

NOTA: toda a matemática acima é executada em módulos com tamanho de palavra de máquina e você só precisa calcular P ^ N uma vez.

Para colar da maneira mais pitônica, use conjuntos!

from sets import Set
a = Set ([1, 1, 1, 0, 0])
b = Set ([0, 1, 1, 1, 0]) 
c = Set ([1, 0, 0, 1, 1])
a==b
True
a==b==c
True