Algoritmo Minimizar la lista de reproducción sin alterar la reproducción

Question

Estoy buscando un algoritmo para reducir una lista (lista de reproducción) de artículos ordenados pero no únicos. de la búsqueda de la teoría de conjuntos, pero No se han detectado nada adecuado embargo

Ejemplos

[a, b, b, c] -> [a, b, b, c] Cannot be reduced. 
[a, b, b, a, b, b] -> [a, b, b]. 
[b, b, b, b, b] -> [b]. 
[b, b, b, b, a] -> [b, b, b, b, a] Cannot be reduced. 

pensando en conseguir todas las listas secundarias existentes y el recuento de cada instancia. Si existe tal sublista donde el recuento multiplicado por el tiempo de la sublista es igual a la lista original, tome la sublista más corta que coincida con este criterio.

Esto parece un poco de fuerza bruta, debe haber una solución más simple/más rápida disponible.

Answer 1

Para cada n <= N (donde N es la longitud de la lista), si n es un factor de N. Si es así, compruebe si la repetición de la sublista de los primeros caracteres n genera la lista original. Si lo hace, entonces ha encontrado una respuesta potencial (la respuesta es la más corta). Esto debería reducirlo a menos de O(N^2) pero sigue teniendo el mismo orden de eficacia que la fuerza bruta en el peor de los casos.

Puede hacer algunos ajustes al observar que, si, por ejemplo, una sublista de longitud 2 genera satisfactoriamente los primeros 4 caracteres pero no la lista completa, una sublista de longitud 4 fallará. Puede mantener una lista de todas estas longitudes de sublista en , no en, y esto reducirá algunos cálculos.

Answer 2

Para empezar, no necesita verificar todas las sublistas, solo aquellas con longitudes que son factores de la longitud de la lista completa.

Si su principal preocupación es la codificación simplicidad en lugar de la velocidad pura, dejar que un motor de expresiones regulares a resolver el problema:

/^(.+?)\1+$/ 

que es una variante de Abigail's awesome Perl regex to find prime numbers.

Answer 3

Codifica cada elemento del conjunto con un número primo.

Ex:

a -> 2 
b -> 3 
c -> 5 

etc.

Ahora, se necesitan dos listas más que mantener.

La primera lista es para primos, la segunda es para sus exponentes.

La idea es; cuando tropiezas con un elemento, registra su número primo y cuántas veces en sucesión aparece.

Para [a, b, b, c], se obtiene lo siguiente:

[2, 3, 3, 5] 

que puede ser registrado como:

[2, 3^2, 5] 

o, más precisamente:

[2^1, 3^2, 5^1] 

y mantener dos listas:

[2,3,5] // primes in succession - list [p] 
[1,2,1] // exponents - list [e] 

Ahora, itere a través de estas dos listas de extremos a medios, verificando si el primer elemento [p]^[e] es el mismo que el último elemento; si lo es, luego el segundo con el penúltimo y así sucesivamente ... Si todos son iguales, su lista se puede reducir.

En este ejemplo, marque 2^1*5^1 == 3^2*3^2; y como no lo es, no se puede reducir.

Probemos [a, b, b, a, b, b]:

Esto se codifica como

[2^1, 3^2, 2^1, 3^2] 

o,

[2, 3, 2, 3] // primes 
[1, 2, 1, 2] // exponents 

Ahora, comprobamos si 2^1 * 3^2 == 3^2 * 2^1 (primer primer, primer exponente multiplicado por último primer, último exponente, y luego se compara con el segundo frente al penúltimo)

Como esto es válido, es reducible.

Probemos [b, b, b, b, b]:

Esto puede ser codificada como

[3^5] 

o,

[3] // primes 
[5] // exponents 

Este es un caso especial: si tienes 1 listas de elementos, entonces su la lista original es reducible.

Probemos [b, b, b, b, a]:

Esto puede ser codificado como

[3^4, 2^1] 

o,

[3, 2] // primes 
[4, 1] // exponents 

Comprobamos si 3^4 == 2^1, y puesto que no es así, la lista no es reducible.

Probemos [a, b, a, b, a, b]:

Esto puede ser codificada como

[2^1, 3^1, 2^1, 3^1, 2^1, 3^1] 

o,

[2, 3, 2, 3, 2, 3] 
[1, 1, 1, 1, 1, 1] 

Tratando el procedimiento anterior funciona, porque 2^1 * 3^1 == 3^1 * 2^1 == 2^1 * 3^1

Por lo tanto, el algoritmo haría ser algo como esto:

---

Codifique todos los números en números primos.

Iterar a través de su lista, haga dos listas y poblar como se describe

Ahora que tiene sus dos listas, p y e, ambos tienen una longitud n hacer esto:

var start = p[0]^e[0] * p[n-1]^e[n-1] 
var reducible = true; 

for (int i = 0; i < n/2, ++i) : 
    if ((p[i]^e[i] * p[n-i]^e[n-i]) != start) : 
     reducible = false; 
     break; 

---

Nota: Realmente no codifiqué este algoritmo y lo intenté para varias entradas. Es solo una idea Además, si una lista es reducible, a partir de su longitud y longitud de n, no debería ser demasiado difícil ver cómo reducir la lista original a su forma básica.

Segunda nota: si alguien ve un error anterior, por favor corrígeme. Es posible que nada de esto realmente funcione ya que es tarde y mi concentración no es óptima.

Answer 4

Aquí hay un código simple que debe ejecutarse cerca del tiempo lineal (en el peor O (n lg lg n) creo, dependiendo de algunas matemáticas superiores).

f(x) { 
    i = 1; 
    while (i <= size(x)/2) { 
    if (size(x) % i != 0) { i++; continue;} 
    b = true; 
    for (j = 0; j + i < x.size(); j++) { 
     if (x[i] != x[j]) { 
     b = false; 
     break; 
     } 
    } 
    if (b) return i; 
    i = max(i + 1, j/i * i/2); // skip some values of i if j is large enough 
    } 
    return -1; 
} 

En esencia, lo anterior lleva a cabo el algoritmo ingenuo, pero se salta algunas periodicidades que son conocidos por ser imposible debido a anteriores "cuasi accidentes". Por ejemplo, si prueba un período de 5 y observa "aaaabaaaabaaaabaaaabab", puede saltear con seguridad 6, 7, ..., 10 ya que vimos 4 ciclos de 5 repeticiones y luego una falla.

En última instancia, terminas haciendo una cantidad lineal de trabajo más una cantidad de trabajo que es lineal en sigma (n), la suma de los divisores de n, que está limitado por O (n lg lg n).

* Tenga en cuenta que probar la exactitud de este salto es bastante sutil, y puedo haber cometido un error en los detalles, los comentarios son bienvenidos.