Calculer le nombre maximum de pistes possibles pour une chaîne de longueur donnée

Il y a quelques semaines, Lembik a posé la question suivante:

Une période p d’une chaîne w est un nombre entier positif p tel que w[i]=w[i+p] chaque fois que les deux côtés de cette équation sont définis. Soit per(w) la taille de la plus petite période de w . On dit qu’une chaîne w est périodique ssi per(w) <= |w|/2 .

Ainsi, de manière informelle, une chaîne périodique est simplement une chaîne composée d’une autre chaîne répétée au moins une fois. La seule complication est que, à la fin de la chaîne, nous n’avons pas besoin d’une copie complète de la chaîne répétée tant qu’elle est répétée au moins une fois.

Par exemple, considérons la chaîne x = abcab . per(abcab) = 3 comme x[1] = x[1+3] = a , x[2]=x[2+3] = b et il n’y a pas de plus petite période. La chaîne abcab n’est donc pas périodique. Cependant, la chaîne ababa est périodique per(ababa) = 2 .

Comme plus d’exemples, abcabca , ababababa et abcabcabc sont également périodiques.

Pour ceux qui aiment les regexes, celui-ci détecte si une chaîne est périodique ou non:

 \b(\w*)(\w+\1)\2+\b 

La tâche consiste à rechercher toutes les sous- chaînes périodiques maximales dans une chaîne plus longue. On les appelle parfois des séries dans la littérature.

Une sous-chaîne w[i,j] de w est une sous-chaîne périodique maximale (run) si elle est périodique et ni w[i-1] = w[i-1+p] ni w[j+1] = w[j+1-p] . De manière informelle, le “run” ne peut pas être contenu dans un plus grand “run” avec la même période.

Comme deux exécutions peuvent représenter la même chaîne de caractères à différents endroits de la chaîne, nous représenterons les exécutions par intervalles. Voici la définition ci-dessus répétée en termes d’intervalles.

Un run (ou sous-chaîne périodique maximale) dans une chaîne T est un intervalle [i...j] avec j>=i , tel que

  • T[i...j] est un mot périodique avec la période p = per(T[i...j])
  • C’est maximal. Formellement, ni T[i-1] = T[i-1+p] ni T[j+1] = T[j+1-p] . De manière informelle, la course ne peut pas être contenue dans un cycle plus important avec la même période.

RUNS(T) l’ensemble des exécutions dans la chaîne T

Exemples de courses

  • Les quatre sous-chaînes périodiques maximales (runs) dans la chaîne T = atattatt sont T[4,5] = tt , T[7,8] = tt , T[1,4] = atat , T[2,8] = tattatt .

  • La chaîne T = aabaabaaaacaacac contient les 7 sous-chaînes périodiques maximales (exécutions) suivantes: T[1,2] = aa , T[4,5] = aa , T[7,10] = aaaa , T[12,13] = aa , T[13,16] = acac , T[1,8] = aabaabaa , T[9,15] = aacaaca .

  • La chaîne T = atatbatatb contient les trois exécutions suivantes. Ce sont: T[1, 4] = atat , T[6, 9] = atat et T[1, 10] = atatbatatb .

Ici, j’utilise l’indexation 1.

Le but

Écrivez le code de sorte que pour chaque nombre entier n commençant à 2, vous produisiez le plus grand nombre d’exécutions contenues dans une chaîne binary de longueur n .

Exemple optima

Dans ce qui suit: n, optimum number of runs, example ssortingng .

 2 1 00 3 1 000 4 2 0011 5 2 00011 6 3 001001 7 4 0010011 8 5 00110011 9 5 000110011 10 6 0010011001 11 7 00100110011 12 8 001001100100 13 8 0001001100100 14 10 00100110010011 15 10 000100110010011 16 11 0010011001001100 17 12 00100101101001011 18 13 001001100100110011 19 14 0010011001001100100 

Existe-t-il un moyen plus rapide de trouver le nombre optimal de passages pour des valeurs croissantes de n qu’une approche de temps naïve O (n ^ 2 2 ^ n)?

Un algorithme générationnel pour trouver toutes les solutions

L’idée

Dans chaque chaîne, le dernier caractère ne peut consortingbuer qu’à un nombre limité d’exécutions.

Un dernier 0 peut seulement append une course à

 10 + 0 => 100 

depuis dans

 00 + 0 => 000 

c’est seulement une répétition. Si elle ajoute cette exécution minimale, la prochaine exécution minimale possible à append est

 110010 + 0 => 1100100 

note encore

 010010 + 0 => 0100100 

n’est pas une course supplémentaire, c’est une répétition. Les prochains ajouts possibles sont

 111001001100100 1111001001100100111001001100100 ... 

Les chiffres peuvent varier mais les longueurs minimales sont

 3, 7, 15, 31 

lequel est

 4^1 - 1, 4^2 - 1, ..., 4^n - 1 

Au début de la chaîne, il n’y a pas besoin d’un caractère différent, donc

 maxaddlast = 4^n - 2 

donne le nombre maximum de pistes pouvant être ajoutées en ajoutant le dernier caractère.

L’algorithme

  • Alors que la recherche de la longueur n est effectuée, toutes les variantes sont enregistrées avec un compte de nombre dans [maxNumberOfRuns – maxaddlast (n + 1), maxNumberOfRuns].
  • Pour trouver une solution avec maxNumberOfRuns pour n + 1, toutes les variantes enregistrées sont simplement étendues avec 0 et 1 et vérifiées.

La graine

Le problème restant consiste à dimensionner la stack pour collecter toutes les variantes requirejses pour les futures graines.

Comme il n’y a pas assez de données pour deviner une formule valide, un algorithme adaptatif est choisi:

  1. La taille initiale de la stack pour n est supposée de n – 1
  2. Pour chaque solution, les tailles de stack utilisées sont vérifiées pour qu’il y ait toujours de la place par 1 dans la stack.
  3. Si la stack était complètement utilisée à n, la taille de la stack est augmentée et le calcul est redémarré à n.

Le résultat

 length 104 with 91 runs 

est atteint dans les 600 secondes. La mémoire est ensuite utilisée avec les parameters par défaut. Utilisez -Xmx16G ou plus. Pour les plus grands nombres, le code doit être modifié pour conserver le germe sur le disque, pas en mémoire.

Et c’est beaucoup plus rapide que la méthode de la force brute.

** Le code **

Et voici mon exemple de code en Java:

 import java.io.BufferedReader; import java.io.FileReader; import java.io.FileWriter; import java.util.ArrayList; import de.bb.util.Pair; /** * A search algorithm to find all runs for increasing lengths of ssortingngs of 0s * and 1s. * * This algorithm uses a seed to generate the candidates for the next search. * The seed contains the solutions for rho(n), rho(n) - 1, ..., minstart(n). * Since the seed size is unknown, it starts with a minimal seed: minstart(n) = * rho(n) - 1; After the solutions are calculated the all seeds are checked. If * a seed with minstart(n) was used, that minstart(n) gets decremented and the * search is restarted at position n + 1. This guarantees that the seed is * always large enough. * * Optional TODO: Since the seed can occupy large amounts of memory, the seed is * maintained on disk. * * @author Stefan "Bebbo" Franke (c) 2016 */ public class MaxNumberOfRunsAdaptive { private static long start; private ArrayList>> seed = new ArrayList<>(); private int max; private ArrayList>>> nextSeedStack; private ArrayList maxs = new ArrayList<>(); private ArrayList diffs = new ArrayList<>(); private ArrayList totals = new ArrayList<>(); private int total; private byte[] buffer; public static void main(String[] args) { int limit = 9999; if (args.length == 1) { try { limit = Integer.parseInt(args[0]); } catch (Exception e) { } } start = System.currentTimeMillis(); new MaxNumberOfRunsAdaptive().run(limit); long took = (System.currentTimeMillis() - start) / 100; System.out.println("took " + (took / 10.) + "s"); } /** * Find a string with the max number of runs for all lengths from 2 to * limit; * * @param limit * the limit to stop calculation. */ private void run(int limit) { maxs.add(0); maxs.add(0); diffs.add(0); diffs.add(1); totals.add(0); totals.add(0); ArrayList n0 = new ArrayList(); n0.add(0); seed.add(Pair.makePair(new byte[] { '0' }, n0)); saveSeed(2); for (int i = 2; i <= limit;) { int restart = compose(i); if (restart < i) { System.out.println("*** restarting at: " + restart + " ***"); i = restart; loadSeed(i); total = totals.get(i - 1); } else { saveSeed(i + 1); ++i; } } } /** * Load the seed for the length from disk. * * @param length */ private void loadSeed(int length) { try { seed.clear(); final FileReader fr = new FileReader("seed-" + length + ".txt"); final BufferedReader br = new BufferedReader(fr); for (String line = br.readLine(); line != null; line = br.readLine()) { final int space = line.indexOf(' '); final byte[] b = line.substring(0, space).getBytes(); final String sends = line.substring(space + 2, line.length() - 1); final ArrayList ends = new ArrayList<>(); for (final String s : sends.split(",")) { ends.add(Integer.parseInt(s.trim())); } seed.add(Pair.makePair(b, ends)); } fr.close(); } catch (Exception e) { throw new RuntimeException(e); } } /** * Save the seed for the given length to the disk. * * @param length * the length */ private void saveSeed(int length) { try { final FileWriter fos = new FileWriter("seed-" + length + ".txt"); for (final Pair> p : seed) { fos.write(new Ssortingng(p.getFirst()) + " " + p.getSecond().toSsortingng() + "\n"); } fos.close(); } catch (Exception e) { throw new RuntimeException(e); } } /** * Compose new ssortingngs from all available bases. Also collect the candidates * for the next base. */ private int compose(int length) { max = 0; int nextStackSize; if (diffs.size() > length) nextStackSize = diffs.get(length) + 1; else nextStackSize = diffs.get(length - 1) - 1; if (nextStackSize < 2) nextStackSize = 2; // setup collector for next bases nextSeedStack = new ArrayList<>(); for (int i = 0; i < nextStackSize; ++i) { nextSeedStack.add(new ArrayList>>()); } buffer = new byte[length]; // extend the bases for (Pair> e : seed) { final byte[] s = e.getFirst(); System.arraycopy(s, 0, buffer, 0, length - 1); if (s.length < 3 || s[s.length - 1] == '1' || s[s.length - 2] == '1' || s[s.length - 3] == '1') { buffer[length - 1] = '0'; test(length, e.getSecond()); } if (s.length < 3 || s[s.length - 1] == '0' || s[s.length - 2] == '0' || s[s.length - 3] == '0') { buffer[length - 1] = '1'; test(length, e.getSecond()); } } long took = (System.currentTimeMillis() - start) / 100; final ArrayList solutions = new ArrayList(); for (Pair> p : nextSeedStack.get(nextSeedStack.size() - 1)) { solutions.add(new Ssortingng(p.getFirst())); } total += solutions.size(); if (totals.size() <= length) totals.add(0); totals.set(length, total); if (maxs.size() <= length) { maxs.add(0); } maxs.set(length, max); System.out.println(length + " " + max + " " + (took / 10.) + " " + total + " " + solutions); seed.clear(); // setup base for next level for (ArrayList>> t : nextSeedStack) { seed.addAll(t); } if (diffs.size() <= length) { diffs.add(1); } int restart = length; // check for restart for (final String b : solutions) { for (int i = 2; i < b.length(); ++i) { int diff = maxs.get(i) - countRuns(b.substring(0, i)); if (diff >= diffs.get(i)) { if (i < restart) restart = i; diffs.set(i, diff + 1); } } } System.out.println(diffs); return restart; } /** * Test the current buffer and at it to the next seed stack, * * @param l * the current length * @param endRuns * the end runs to store */ void test(final int l, final ArrayList endRuns) { final ArrayList r = incrementalCountRuns(l, endRuns); final int n = r.get(r.size() - 1); // shift the nextBaseStack while (max < n) { nextSeedStack.remove(0); nextSeedStack.add(new ArrayList>>()); ++max; } // add to set in stack, if in stack final int index = nextSeedStack.size() - 1 - max + n; if (index >= 0) nextSeedStack.get(index).add(Pair.makePair(buffer.clone(), r)); } /** * Find incremental the runs incremental. * * @param l * the lengths * @param endRuns * the runs of length-1 ending at length -1 * @return a new array containing the end runs plus the length */ private ArrayList incrementalCountRuns(final int l, final ArrayList endRuns) { final ArrayList res = new ArrayList(); int sz = endRuns.size(); // last end run dummy - contains the run count int n = endRuns.get(--sz); int pos = 0; for (int i = l - 2; i >= 0; i -= 2) { int p = (l - i) / 2; // found something ? if (equals(buffer, i, buffer, i + p, p)) { while (i > 0 && buffer[i - 1] == buffer[i - 1 + p]) { --i; } int lasti = -1; while (pos < sz) { lasti = endRuns.get(pos); if (lasti <= i) break; lasti = -1; ++pos; } if (lasti != i) ++n; res.add(i); } } res.add(n); return res; } /** * Compares one segment of a byte array with a segment of a 2nd byte array. * * @param a * first byte array * @param aOff * offset into first byte array * @param b * second byte array * @param bOff * offset into second byte array * @param len * length of the compared segments * @return true if the segments are equal, otherwise false */ public final static boolean equals(byte a[], int aOff, byte b[], int bOff, int len) { if (a == null || b == null) return a == b; while (len-- > 0) if (a[aOff + len] != b[bOff + len]) return false; return true; } /** * Simple slow stupid method to count the runs in a Ssortingng. * * @param s * the ssortingng * @return the count of runs. */ static int countRuns(Ssortingng s) { int n = 0; int l = s.length(); for (int i = 0; i < l - 1; ++i) { for (int k = i + 1; k < l; ++k) { int p = 0; while (i + p < k && k + p < l) { if (s.charAt(i + p) != s.charAt(k + p)) break; ++p; } if (i + p == k) { int jj = k + p - 1; if (i > 0 && s.charAt(i - 1) == s.charAt(i - 1 + p)) { continue; } while (jj + 1 < l && s.charAt(jj + 1) == s.charAt(jj + 1 - p)) { ++jj; ++k; } ++n; } } } return n; } } 

Réponse partielle L’idée est de prendre une page de l’algorithme de recherche de chaînes de Boyer-Moore, modifiée de manière appropriée pour que la chaîne à rechercher provienne de la chaîne source.

Considérez le problème pour une chaîne de longueur n recherchant des exécutions de la période k , où 2k < n . S'il y a un algorithme de temps polynomial pour ce problème, alors il y en a un pour le problème général. Il suffit de lancer un tel algorithme une fois pour chaque 2 <= k <= n/2 . Si le problème spécifique s'exécute en O(p(n))p a un degré d , le problème général se produira avec un polynôme de degré d+1 . Il suffit donc d'examiner le problème spécifique.

Soit la chaîne d'entrée T[0 ... n-1] . La clé ici est de réaliser que si T[i] != T[i+k] , alors la paire d'indices (i, i+k) crée une obstruction à l'existence d'une course. Lorsque nous voyons une obstruction, nous pouvons subdiviser le problème en deux problèmes sur des chaînes d'entrée plus courtes: T[0 ... i+k-1] et T[i+1 ... n-1] . Si l'une de ces chaînes est trop courte, l'algorithme n'émet rien et se termine; c'est la façon dont la récursivité se termine lorsqu'un run n'existe pas. Recherchez maintenant les obstructions a i+1 , i+2 , ..., jusqu'à i+k-1 . S'il en existe, cliver. Par contre, s'il y a une séquence [i ... i+k-1] sans aucune obstruction, alors nous avons une longueur de 2k . Si nous trouvons un run, nous constatons que nous l'étendons au maximum (c'est facile), puis nous divisons le problème en trois parties: le préfixe, le run et le suffixe. Nous émettons le run et nous avons maintenant deux problèmes, le préfixe et le suffixe, chacun plus court. Pour exécuter ceci de manière récursive, choisissez un initial i avec la valeur (n+k)/2 .

La raison pour laquelle ceci est une réponse partielle est que je laisse l'parsing que c'est un algorithme de temps polynomial. La raison pour laquelle la preuve n’est pas sortingviale est que, lorsque vous avez une obstruction, les longueurs i+k et ni-1 s’élèvent à n+k-1 , ce qui est plus grand que n . sur une stack de récurrence peut croître de manière exponentielle. D'autres arguments seraient nécessaires pour montrer que cela ne se produit pas réellement.