Cómo verificar si dos listas son circularmente idénticas en Python

Por ejemplo, tengo 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

Parecen ser diferentes, pero si se supone que el inicio y el final están conectados, entonces son circularmente idénticos.

El problema es que cada lista que tengo tiene una longitud de 55 y contiene solo tres unos y 52 ceros. Sin condición circular, hay 26,235 (55 elegir 3) listas. Sin embargo, si existe la condición 'circular', hay una gran cantidad de listas circularmente idénticas

Actualmente verifico circularmente la identidad siguiendo:

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 función requiere 55 operaciones de desplazamiento cíclico en el peor de los casos. Y hay 26.235 listas para comparar entre sí. En resumen, necesito 55 * 26,235 * (26,235 - 1) / 2 = 18,926,847,225 cálculos. ¡Se trata de casi 20 Giga!

¿Hay alguna buena manera de hacerlo con menos cálculos? ¿O algún tipo de datos que admita circular ?

En primer lugar, esto se puede hacer en O(n)términos de la longitud de la lista. Puede notar que si duplica su lista 2 veces ( [1, 2, 3]), [1, 2, 3, 1, 2, 3]su nueva lista definitivamente tendrá todas las listas cíclicas posibles.

Entonces, todo lo que necesita es verificar si la lista que está buscando está dentro de 2 veces de su lista de inicio. En python puede lograr esto de la siguiente manera (suponiendo que las longitudes sean las mismas).

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

Alguna explicación sobre mi línea: list * 2combinará una lista consigo misma, map(str, [1, 2])convertirá todos los números en una cadena y ' '.join()convertirá la matriz ['1', '2', '111']en una cadena '1 2 111'.

Como señalaron algunas personas en los comentarios, oneliner potencialmente puede dar algunos falsos positivos, por lo que para cubrir todos los casos límite posibles:

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 cuando se habla de la complejidad del tiempo, vale la pena notar que O(n)se logrará si la subcadena se puede encontrar a O(n)tiempo. No siempre es así y depende de la implementación en su idioma ( aunque potencialmente se puede hacer en tiempo lineal KMP, por ejemplo).

PS2 para personas que tienen miedo a la operación de cadenas y debido a este hecho piensan que la respuesta no es buena. Lo importante es la complejidad y la velocidad. Este algoritmo potencialmente se ejecuta en O(n)tiempo y O(n)espacio, lo que lo hace mucho mejor que cualquier cosa en el O(n^2)dominio. Para ver esto usted mismo, puede ejecutar un pequeño punto de referencia (crea una lista aleatoria que muestra el primer elemento y lo agrega al final, creando así una lista cíclica. Usted es libre de hacer sus propias manipulaciones)

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 en mi máquina. No mucho tiempo. Ahora intenta comparar esto con O(n^2)soluciones. Mientras lo compara, puede viajar de EE. UU. A Australia (muy probablemente en un crucero)

No estoy lo suficientemente informado en Python para responder esto en el lenguaje solicitado, pero en C / C ++, dados los parámetros de su pregunta, convertiría los ceros y unos en bits y los insertaría en los bits menos significativos de un uint64_t. Esto le permitirá comparar los 55 bits de una sola vez: 1 reloj.

Perversamente rápido, y todo encajará en cachés en chip (209,880 bytes). El soporte de hardware para desplazar los 55 miembros de la lista a la derecha simultáneamente está disponible solo en los registros de una CPU. Lo mismo ocurre con la comparación de los 55 miembros simultáneamente. Esto permite un mapeo 1 por 1 del problema a una solución de software. (y utilizando los registros SIMD / SSE de 256 bits, hasta 256 miembros si es necesario) Como resultado, el código es inmediatamente obvio para el lector.

Es posible que pueda implementar esto en Python, pero no lo sé lo suficiente como para saber si eso es posible o cuál podría ser el rendimiento.

Después de dormir, algunas cosas se volvieron obvias, y todo para mejor.

1.) Es tan fácil girar la lista enlazada circularmente con bits que el ingenioso truco de Dali no es necesario. Dentro de un registro de 64 bits, el desplazamiento de bits estándar logrará la rotación de manera muy simple, y en un intento de hacer que esto sea más amigable con Python, usando aritmética en lugar de operaciones de bits.

2.) El desplazamiento de bits se puede lograr fácilmente usando dividir entre 2.

3.) El módulo 2 puede verificar fácilmente el final de la lista para 0 o 1.

4.) "Mover" un 0 al principio de la lista desde la cola se puede hacer dividiendo entre 2. Esto porque si el cero se moviera realmente haría que el bit 55 sea falso, lo que ya es al no hacer absolutamente nada.

5.) "Mover" un 1 al comienzo de la lista desde la cola se puede hacer dividiendo por 2 y sumando 18,014,398,509,481,984, que es el valor creado al marcar el 55 ° bit verdadero y todo lo demás falso.

6.) Si una comparación del ancla y el compuesto uint64_t es VERDADERO después de una rotación dada, rompa y devuelva VERDADERO.

Convertiría toda la matriz de listas en una matriz de uint64_ts por adelantado para evitar tener que hacer la conversión repetidamente.

Después de pasar algunas horas tratando de optimizar el código, estudiando el lenguaje ensamblador, pude ahorrar un 20% del tiempo de ejecución. Debo agregar que ayer también se actualizó el compilador O / S y MSVC. Por cualquier motivo, la calidad del código que el compilador C produjo mejoró dramáticamente después de la actualización (15/11/2014). El tiempo de ejecución es ahora ~ 70 relojes, 17 nanosegundos para componer y comparar un anillo de anclaje con las 55 vueltas de un anillo de prueba y NxN de todos los anillos contra todos los demás se realiza en 12.5 segundos .

Este código es tan estricto que todos menos 4 registros están sentados sin hacer nada el 99% del tiempo. El lenguaje ensamblador coincide con el código C casi línea por línea. Muy fácil de leer y entender. Un gran proyecto de montaje si alguien se estuviera enseñando eso.

El hardware es Hazwell i7, MSVC de 64 bits, optimizaciones 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;
}

Leyendo entre líneas, parece que estás tratando de enumerar un representante de cada clase de cadenas de equivalencia circular con 3 unidades y 52 ceros. Cambiemos de una representación densa a una escasa (conjunto de tres números range(55)). En esta representación, el desplazamiento circular de sby kviene dado por la comprensión set((i + k) % 55 for i in s). El representante mínimo lexicográfico en una clase siempre contiene la posición 0. Dado un conjunto del formulario {0, i, j}con 0 < i < j, los otros candidatos para el mínimo en la clase son {0, j - i, 55 - i}y {0, 55 - j, 55 + i - j}. Por lo tanto, necesitamos (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j))que el original sea mínimo. Aquí hay un código de enumeración.

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 la primera matriz, luego use el algoritmo Z (tiempo O (n)) para encontrar la segunda matriz dentro de la primera.

(Nota: no tiene que copiar físicamente la primera matriz. Simplemente puede ajustar durante la coincidencia).

Lo bueno del algoritmo Z es que es muy simple en comparación con KMP, BM, etc.
Sin embargo, si se siente ambicioso, podría hacer una coincidencia de cadenas en tiempo lineal y espacio constantestrstr ; por ejemplo, hace esto. Sin embargo, implementarlo sería más doloroso.

Continuando con la solución muy inteligente de Salvador Dalí, la mejor manera de manejarla es asegurarse de que todos los elementos tengan la misma longitud, así como que ambas LISTAS tengan la misma longitud.

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

No tengo idea si esto es más rápido o más lento que la solución de expresiones regulares recomendada por AshwiniChaudhary en la respuesta de Salvador Dali, que dice:

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 necesita hacer tantas comparaciones, ¿podría valer la pena tomar un primer paso por sus listas para convertirlas en algún tipo de forma canónica que se pueda comparar fácilmente?

¿Estás tratando de obtener un conjunto de listas únicas circulares? Si es así, puedes tirarlos en un conjunto después de convertirlos en 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)

Disculpas a David Eisenstat por no detectar su respuesta muy similar.

Puede rodar una 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

Primero convierta cada uno de los elementos de su lista (en una copia si es necesario) a esa versión rotada que es léxicamente mejor.

Luego ordene la lista de listas resultante (manteniendo un índice en la posición original de la lista) y unifique la lista ordenada, marcando todos los duplicados en la lista original según sea necesario.

Piggybacking en la observación de @ SalvadorDali sobre la búsqueda de coincidencias de a en cualquier segmento de tamaño alargado en b + b, aquí hay una solución que usa solo operaciones 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

Segundo enfoque: [eliminado]

No es una respuesta completa e independiente, pero sobre el tema de la optimización mediante la reducción de las comparaciones, yo también estaba pensando en representaciones normalizadas.

Es decir, si su alfabeto de entrada es {0, 1}, podría reducir significativamente el número de permutaciones permitidas. Gire la primera lista a una forma (pseudo-) normalizada (dada la distribución en su pregunta, elegiría uno donde uno de los 1 bits esté en el extremo izquierdo y uno de los 0 bits esté en el extremo derecho). Ahora, antes de cada comparación, gire sucesivamente la otra lista a través de las posibles posiciones con el mismo patrón de alineación.

Por ejemplo, si tiene un total de cuatro bits 1, puede haber como máximo 4 permutaciones con esta alineación, y si tiene grupos de 1 bits adyacentes, cada bit adicional en dicho grupo reduce la cantidad de posiciones.

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

Esto se generaliza a alfabetos más grandes y diferentes patrones de alineación; El principal desafío es encontrar una buena normalización con solo unas pocas representaciones posibles. Idealmente, sería una normalización adecuada, con una única representación única, pero dado el problema, no creo que sea posible.

Continuando con la respuesta de Rocket Roy: Convierta todas sus listas por adelantado en números de 64 bits sin signo. Para cada lista, gire esos 55 bits para encontrar el valor numérico más pequeño.

Ahora le queda un único valor de 64 bits sin signo para cada lista que puede comparar directamente con el valor de las otras listas. La función is_circular_identical () ya no es necesaria.

(En esencia, crea un valor de identidad para sus listas que no se ve afectado por la rotación de los elementos de las listas) Eso incluso funcionaría si tiene un número arbitrario de uno en sus listas.

Esta es la misma idea de Salvador Dalí, pero no necesita la conversión de cadena. Detrás está la misma idea de recuperación de KMP para evitar una inspección de turno imposible. Solo llaman a KMPModified (list1, list2 + list2).

    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 esto ayude!

Simplificando el problema

• El problema consiste en una lista de artículos ordenados
• El dominio del valor es binario. (0,1)
• Podemos reducir el problema mapeando 1s consecutivos en un recuento
• y 0s consecutivos en un recuento negativo

Ejemplo

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 ]

• Este proceso requiere que el primer elemento y el último elemento sean diferentes
• Esto reducirá la cantidad de comparaciones en general

Proceso de verificación

• Si suponemos que están duplicados, podemos suponer lo que estamos buscando.
• Básicamente, el primer elemento de la primera lista debe existir en algún lugar de la otra lista
• Seguido de lo que sigue en la primera lista, y de la misma manera
• Los elementos anteriores deben ser los últimos elementos de la primera lista.
• Como es circular, el orden es el mismo.

La empuñadura

• La pregunta aquí es por dónde empezar, técnicamente conocido como lookupylook-ahead
• Solo verificaremos dónde existe el primer elemento de la primera lista a través de la segunda lista
• La probabilidad de elemento frecuente es menor dado que mapeamos las listas en histogramas

Pseudocó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

Las funciones

• MAP_LIST(LIST A):LIST MAPA ELEMENTOS CONSECUTIVOS COMO CUENTA EN UNA NUEVA LISTA

• LOOKUP_INDEX(LIST A, INTEGER E):LISTVOLVER LISTA DE ÍNDICES DONDE EL ELEMENTO EEXISTE EN LA LISTAA

• COUNT_CHAR(LIST A , INTEGER E):INTEGERCUENTA CUANTAS VECES OCURRE UN ELEMENTO EEN UNA LISTAA

• ALPHA_NGRAM(LIST A,LIST B,INTEGER I,INTEGER N):BOOLEANCOMPRUEBE SI B[I]ES EQUIVALENTE A[0] N-GRAMEN AMBAS DIRECCIONES

Finalmente

Si el tamaño de la lista va a ser bastante grande o si el elemento del que estamos comenzando a verificar el ciclo es con frecuencia alto, entonces podemos hacer lo siguiente:

• Busque el elemento menos frecuente en la primera lista para comenzar

• aumente el parámetro N de n-gramo para disminuir la probabilidad de pasar por una verificación lineal

Una "forma canónica" eficiente y rápida de calcular para las listas en cuestión puede derivarse como:

• Cuente el número de ceros entre ellos (ignorando el ajuste), para obtener tres números.
• Gire los tres números para que el mayor sea el primero.
• El primer número ( a) debe estar entre 18y 52(inclusive). Vuelva a codificarlo entre 0y34 .
• El segundo número ( b) debe estar entre 0y26 , pero no importa mucho.
• Suelte el tercer número, ya que es justo 52 - (a + b)y no agrega información

La forma canónica es el número entero b * 35 + a, que está entre 0y 936(inclusive), que es bastante compacto (hay 477listas circulares únicas en total).

Escribí una solución sencilla que compara ambas listas y solo aumenta (y ajusta) el índice del valor comparado para cada iteración.

No conozco Python bien, así que lo escribí en Java, pero es realmente simple, por lo que debería ser fácil adaptarlo a cualquier otro idioma.

De este modo, también podría comparar listas de otros 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 otros han mencionado, una vez que encuentre la rotación normalizada de una lista, puede compararlos.

Aquí hay un código de trabajo que hace esto, el método básico es encontrar una rotación normalizada para cada lista y comparar:

• Calcule un índice de rotación normalizado en cada lista.
• Recorre ambas listas con sus compensaciones, compara cada elemento y regresa si no coinciden.

Tenga en cuenta que este método no depende de los números, puede pasar listas de cadenas (cualquier valor que se pueda comparar).

En lugar de hacer una búsqueda de lista en lista, sabemos que queremos que la lista comience con el valor mínimo, para que podamos recorrer los valores mínimos, buscando hasta encontrar cuál tiene los valores sucesivos más bajos, almacenando esto para futuras comparaciones. hasta que tengamos lo mejor.

Hay muchas oportunidades para salir temprano al calcular el índice, detalles sobre algunas optimizaciones.

• Omita la búsqueda del mejor valor mínimo cuando solo haya uno.
• Omita la búsqueda de valores mínimos cuando el anterior también es un valor mínimo (nunca será una mejor coincidencia).
• Omita la búsqueda cuando todos los valores sean iguales.
• Fallar temprano cuando las listas tienen valores mínimos diferentes.
• Use una comparación regular cuando las compensaciones coincidan.
• Ajuste las compensaciones para evitar ajustar los valores de índice en una de las listas durante la comparación.

Tenga en cuenta que en Python una búsqueda lista por lista puede ser más rápida, sin embargo, estaba interesado en encontrar un algoritmo eficiente, que también podría usarse en otros idiomas. Además, hay algunas ventajas en evitar crear nuevas 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)

Ver: este fragmento para algunas pruebas / ejemplos más.

Puede verificar si una lista A es igual a un cambio cíclico de la lista B en el tiempo esperado de O (N) con bastante facilidad.

Usaría una función de hash polinomial para calcular el hash de la lista A, y cada cambio cíclico de la lista B. Cuando un cambio de la lista B tiene el mismo hash que la lista A, compararía los elementos reales para ver si son iguales .

La razón por la que esto es rápido es que con las funciones de hash polinomiales (¡que son extremadamente comunes!), Puede calcular el hash de cada cambio cíclico del anterior en tiempo constante, por lo que puede calcular los hash para todos los cambios cíclicos en O ( N) tiempo.

Funciona así:

Digamos que B tiene N elementos, entonces el hash de B usando P principal es:

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

Esta es una forma optimizada de evaluar un polinomio en P, y es equivalente a:

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

Observe cómo cada B [i] se multiplica por P ^ (N-1-i). Si desplazamos B a la izquierda por 1, entonces cada B [i] se multiplicará por una P adicional, excepto la primera. Dado que la multiplicación se distribuye sobre la suma, podemos multiplicar todos los componentes a la vez simplemente multiplicando todo el hash y luego arreglar el factor para el primer elemento.

El hash del desplazamiento a la izquierda de B es solo

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

El segundo turno a la izquierda:

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

y así...

NOTA: todas las matemáticas anteriores se realizan en un módulo de tamaño de palabra de máquina, y solo tiene que calcular P ^ N una vez.

Para pegarte a la forma más pitónica de hacerlo, ¡usa sets!

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