Algorithme Minimiser la liste de lecture sans modifier la lecture

Question

Je recherche un algorithme pour réduire une liste (liste de lecture) d'éléments ordonnés mais pas uniques. recherche de la théorie des ensembles, mais havent trouvé quoi que ce soit encore approprié

Exemples

[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. 

pense d'obtenir tous les sous-listes existantes et comptent chaque instance. S'il existe une sous-liste où le nombre de fois la longueur de sous-liste est égale à la liste originale, prenez la sous-liste la plus courte correspondant à ce critère.

Cela semble un peu brutal, il doit y avoir une solution plus simple/plus rapide disponible.

Answer 1

Pour chaque n <= N (où N est la longueur de la liste), si n est un facteur de N. Si c'est le cas, vérifiez si la répétition de la sous-liste des premiers caractères n génère la liste d'origine. Si c'est le cas, alors vous avez trouvé une réponse potentielle (la réponse est la plus courte). Cela devrait vous descendre à moins de O(N^2) mais toujours le même ordre d'efficacité que la force brute dans le pire des cas.

Vous pouvez effectuer une opération d'élagage en notant que, si par exemple une sous-liste de longueur 2 génère avec succès les 4 premiers caractères mais pas la liste complète, une sous-liste de longueur 4 échouera. Vous pouvez conserver une liste de toutes ces longueurs de sous-liste à et non vérifier et cela va réduire certains calculs.

Answer 2

Pour commencer, vous n'avez pas besoin de vérifier toutes les sous-listes - seulement celles avec des longueurs facteurs de la longueur de la liste complète.

Si votre principale préoccupation est la simplicité codage plutôt que la vitesse brute, laissez un moteur regex résoudre le problème:

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

Ce qui est une variante de Abigail's awesome Perl regex to find prime numbers.

Answer 3

Encoder chaque élément d'un ensemble avec un nombre premier.

Ex:

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

etc.

Maintenant, vous avez besoin de deux autres listes pour maintenir.

La première liste est pour les nombres premiers, la seconde est pour leurs exposants.

L'idée est; Lorsque vous tombez sur un élément, enregistrez son nombre premier et combien de fois de suite il apparaît.

Pour [a, b, b, c], vous obtenez ceci:

[2, 3, 3, 5] 

qui peut être enregistré comme:

[2, 3^2, 5] 

ou, plus précisément:

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

et vous maintenir deux listes:

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

Maintenant, vous parcourez ces deux listes de bout en bout, en vérifiant si le premier élément [p]^[e] est le même que le dernier élément; si c'est le cas, puis deuxième avec avant-dernier et ainsi de suite ... Si tous sont les mêmes, votre liste peut être réduite.

Dans cet exemple, vous vérifiez si 2^1*5^1 == 3^2*3^2; et puisque ce n'est pas le cas, cela ne peut pas être réduit.

Essayons [a, b, b, a, b, b]:

Ceci est codé comme

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

ou,

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

Maintenant, nous vérifions si 2^1 * 3^2 == 3^2 * 2^1 (premier premier, premier exposant multiplié par la dernière prime, dernière exposant, puis comparé avec le deuxième par rapport à l'avant-dernier)

Puisque cela est vrai, il est réductible.

Essayons [b, b, b, b, b]:

Cela peut être codé comme

[3^5] 

ou,

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

Ceci est un cas particulier: si vous avez 1 listes d'éléments, votre la liste originale est réductible.

Essayons [b, b, b, b, a]:

Cela peut être encodée comme

[3^4, 2^1] 

ou,

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

Nous vérifions si 3^4 == 2^1, et comme il n'est pas, votre liste n'est pas réductible.

Essayons [a, b, a, b, a, b]:

Cela peut être codé comme

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

ou,

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

Essayer la procédure ci-dessus fonctionne, car 2^1 * 3^1 == 3^1 * 2^1 == 2^1 * 3^1

Ainsi, l'algorithme serait être quelque chose comme ça:

---

Encode tous les nombres en nombres premiers.

Itération dans votre liste, faire deux listes et les remplir comme décrit

Maintenant que vous avez vos deux listes, p et e, tous les deux ayant une longueur n faire:

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; 

---

Note: Je n'ai pas vraiment codé cet algorithme et je l'ai essayé pour différentes entrées. C'est juste une idée. Aussi, si une liste est réductible, de sa longueur et longueur de n, il ne devrait pas être trop difficile de voir comment réduire la liste d'origine à sa forme de base.

Deuxième remarque: si quelqu'un voit une erreur ci-dessus, veuillez me corriger. Il est possible que rien de tout cela ne fonctionne vraiment car il est tard et ma concentration n'est pas optimale.

Answer 4

Voici un code simple qui devrait fonctionner dans un temps proche du temps linéaire (au pire O (n lg lg n) je pense, en me basant sur des maths plus élevés).

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

Essentiellement, l'algorithme effectue au-dessus du naïf, mais ignore certains périodicités qui sont connus pour être impossible en raison de précédents « quasi ». Par exemple, si vous essayez une période de 5 et voyez "aaaabaaaabaaaabaaaabab", vous pouvez sauter en toute sécurité 6, 7, ..., 10 puisque nous avons vu 4 cycles de 5 répétitions puis un échec. En fin de compte, vous finissez par faire une quantité linéaire de travail plus une quantité de travail linéaire dans sigma (n), la somme des diviseurs de n, qui est bornée par O (n lg lg n).

* Notez que prouver l'exactitude de ce saut est assez subtile, et j'ai peut-être fait une erreur sur les détails - les commentaires sont les bienvenus.