una - recorrer dos listas a la vez python

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

Question

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 idénticas circularmente

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 ?

Answer 1

Para pegar 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

Answer 2

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, 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 el hash completo 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 con un tamaño de palabra de máquina, y solo tiene que calcular P ^ N una vez.

Answer 3

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 lista en lista, sabemos que queremos que la lista comience con el valor mínimo, de modo 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 hay 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.

Answer 4

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.

Answer 5

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 expresión regular 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))

Answer 6

Dado que necesita hacer tantas comparaciones, ¿podría valer la pena tomar un pase inicial a través de 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.

Answer 7

En primer lugar, esto se puede hacer en O(n) en términos de la longitud de la lista. Puede notar que si duplica su lista 2 veces ( [1, 2, 3] ) será [1, 2, 3, 1, 2, 3] entonces 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 * 2 combinará una lista consigo misma, map(str, [1, 2]) convertirá todos los números a string 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 se logrará O(n) si se puede encontrar la subcadena en el tiempo O(n) . 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 se ejecuta potencialmente en O(n) tiempo y O(n) espacio, lo que lo hace mucho mejor que cualquier cosa en el dominio O(n^2) . 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 intente comparar esto con soluciones O(n^2) . Mientras lo compara, puede viajar de EE. UU. A Australia (muy probablemente en un crucero)

Answer 8

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;
}
}

Answer 9

Esta es la misma idea de Salvador Dali 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!

Answer 10

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 en el range(55) ). En esta representación, el desplazamiento circular de s por k viene dado por el set((i + k) % 55 for i in s) 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 de la forma {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)) para 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

Answer 11

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.

Answer 12

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, utilizando 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 encabezado de la lista desde la cola se puede hacer dividiendo entre 2. Esto porque si el cero se moviera realmente haría falso el bit 55, que ya no hace 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 55o bit verdadero y todo lo demás falso.

6.) Si una comparación del ancla y uint64_t compuesto 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 unas 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 ahora es de ~ 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;
}

Answer 13

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]

Answer 14

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 (reteniendo 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.

Answer 15

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

Answer 16

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 constante ; strstr , por ejemplo, hace esto. Sin embargo, implementarlo sería más doloroso.

Answer 17

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

• Cuente la cantidad de ceros entre las unidades (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 18 y 52 (inclusive). Vuelva a codificarlo entre 0 y 34 .
• El segundo número ( b ) debe estar entre 0 y 26 , pero no importa mucho.
• Suelte el tercer número, ya que es solo 52 - (a + b) y no agrega información

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

Answer 18

Simplificando el problema

• El problema consiste en una lista de artículos pedidos
• El dominio del valor es binario (0,1)
• Podemos reducir el problema mapeando 1 s consecutivos en un recuento
• y 0 s 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 lookup y look-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 DE ELEMENTOS CONSECUTIVOS MAP_LIST(LIST A):LIST MAPA COMO CUENTA EN UNA NUEVA LISTA

• LOOKUP_INDEX(LIST A, INTEGER E):LIST VOLVER LISTA DE ÍNDICES DONDE EL ELEMENTO E EXISTE EN LA LISTA A

• COUNT_CHAR(LIST A , INTEGER E):INTEGER RECUENTO COUNT_CHAR(LIST A , INTEGER E):INTEGER UN ELEMENTO E EN UNA LISTA A

• ALPHA_NGRAM(LIST A,LIST B,INTEGER I,INTEGER N):BOOLEAN COMPROBACIÓN ALPHA_NGRAM(LIST A,LIST B,INTEGER I,INTEGER N):BOOLEAN SI B[I] ES EQUIVALENTE A A[0] N-GRAM EN 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

• Aumentar el parámetro N de n gramos para reducir la probabilidad de pasar por una verificación lineal