42 votes

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

Il y A quelques semaines Lembik posé la question suivante:

Une période p d'une chaîne de caractères w est tout entier positif p tels que w[i]=w[i+p] chaque fois que les deux côtés de cette équation sont définis. Laissez - per(w)dénoter la taille de la plus petite période d' w . Nous disons qu'une chaîne de caractères west périodique iff per(w) <= |w|/2.

D'une façon informelle périodique de la chaîne est juste une chaîne de caractères qui est constitué à partir d'une autre chaîne de caractères répétées au moins une fois. La seule complication est qu'à la fin de la chaîne, nous ne nécessitent pas une copie complète de la nouvelle chaîne, tant qu'il est repris dans son intégralité au moins une fois.

Par exemple envisager 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 en tant que per(ababa) = 2.

Comme exemples, abcabca, ababababa et abcabcabc aussi périodique.

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 est de trouver tous maximal périodique des sous-chaînes dans une longue chaîne. Ce sont parfois des pistes dans la littérature.

Une sous-chaîne de caractères w[i,j] de w est un maximum de périodique substring (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 contenue dans une plus grande "exécuter" à la même période.

Parce que deux pistes peuvent représenter la même chaîne de caractères apparaissant dans différents endroits dans l'ensemble de la chaîne, nous allons représenter fonctionne par intervalles. Voici la définition ci-dessus répété en termes d'intervalles.

Une course (ou maximale du périodique, sous-chaîne) dans une chaîne de caractères T est un intervalle [i...j] avec j>=i, de telle sorte que

  • T[i...j] est un périodique mot avec la période p = per(T[i...j])
  • Elle est maximale. 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 une autonomie plus importante à la même période.

Désigner par RUNS(T) le jeu de pistes dans la chaîne T.

Exemples de pistes

  • Les quatre maximale périodique des sous-chaînes (pistes) en chaîne de caractères 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 éléments suivants 7 maximal périodique des sous-chaînes (fonctionne): 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 trois pistes. Ils sont les suivants: T[1, 4] = atat, T[6, 9] = atat et T[1, 10] = atatbatatb.

Ici, je suis en utilisant la 1-indexation.

L'objectif

Écrire le code de sorte que, pour chaque entier n à partir de 2, vous de la sortie du plus grand nombre de pistes contenues dans toute une chaîne binaire de longueur n.

Exemple optima

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

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

Est-il un moyen plus rapide pour trouver le nombre optimal de pistes pour des valeurs croissantes de n qu'un naïf O(n^2 2^n) approche de temps?

2voto

bebbo Points 349

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

L'Idée

Dans chaque chaîne le dernier caractère ne peut que contribuer à un nombre limité de pistes.

Un dernier 0 ne peut ajouter une course à

10 + 0 => 100

depuis dans

00 + 0 => 000

c'est seulement une répétition. Et s'il ajoute qu'un minimum de courir, la prochaine minimale exécuter à ajouter

110010 + 0 => 1100100

notez encore une fois

010010 + 0 => 0100100

n'est pas une course supplémentaire, c'est une répétition. La prochaine ajoute l'

111001001100100
1111001001100100111001001100100
...

Les chiffres peuvent varier, mais les longueurs minimales sont

3, 7, 15, 31

qui est

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

À la chaîne de démarrer il n'est pas nécessaire pour un caractère différent, donc

maxaddlast = 4^n - 2

donne le nombre maximal de pistes qui peuvent être ajoutés par l'ajout du dernier caractère.

L'Algorithme

  • Bien que la recherche de longueur n est fait, toutes les variantes sont enregistrées avec un compte run dans [maxNumberOfRuns - maxaddlast(n+1), maxNumberOfRuns].
  • Pour trouver une solution avec maxNumberOfRuns pour n+1 tout simplement tous enregistrés variantes sont prolongés par des 0 et des 1 et vérifié.

La Graine

Le problème reste de taille de la pile pour recueillir toutes les variantes qui sont nécessaires pour les futures graines.

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

  1. La première la taille de la pile pour n est deviné à partir de n - 1
  2. Pour chaque solution utilisée tailles de tapis sont vérifiées qu'il y a toujours de chambre par 1 dans la pile.
  3. Si la pile a été entièrement utilisés à un certain n, la taille de la pile est augmenté 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 alors utilisé avec les paramètres par défaut. Utilisez -Xmx16G ou plus. Pour un plus grand nombre, le code doit être modifié afin de conserver la semence sur le disque, pas en mémoire.

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

** 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 strings 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<Pair<byte[], ArrayList<Integer>>> seed = new ArrayList<>();
    private int max;
    private ArrayList<ArrayList<Pair<byte[], ArrayList<Integer>>>> nextSeedStack;

    private ArrayList<Integer> maxs = new ArrayList<>();
    private ArrayList<Integer> diffs = new ArrayList<>();
    private ArrayList<Integer> 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<Integer> n0 = new ArrayList<Integer>();
        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<Integer> 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<byte[], ArrayList<Integer>> p : seed) {
                fos.write(new String(p.getFirst()) + " " + p.getSecond().toString() + "\n");
            }
            fos.close();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * Compose new strings 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<Pair<byte[], ArrayList<Integer>>>());
        }

        buffer = new byte[length];
        // extend the bases
        for (Pair<byte[], ArrayList<Integer>> 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<String> solutions = new ArrayList<String>();
        for (Pair<byte[], ArrayList<Integer>> p : nextSeedStack.get(nextSeedStack.size() - 1)) {
            solutions.add(new String(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<Pair<byte[], ArrayList<Integer>>> 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<Integer> endRuns) {
        final ArrayList<Integer> 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<Pair<byte[], ArrayList<Integer>>>());
            ++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<Integer> incrementalCountRuns(final int l, final ArrayList<Integer> endRuns) {
        final ArrayList<Integer> res = new ArrayList<Integer>();
        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 String.
     * 
     * @param s
     *            the string
     * @return the count of runs.
     */
    static int countRuns(String 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;
    }
}

0voto

eh9 Points 3804

Réponse partielle. L'idée est de prendre une page de l'Boyer-Moore chaîne de l'algorithme de recherche, modifié convenablement, de sorte que la chaîne pour être assorti vient de la chaîne source.

Considérons le problème pour une chaîne de longueur n à la recherche pour les courses de la période k2k < n. S'il existe un algorithme polynomial en temps pour résoudre ce problème, puis il y en a une pour le problème général. Il suffit d'exécuter un tel algorithme une fois pour chaque 2 <= k <= n/2. Si le problème s'exécute en O(p(n))p a le degré d, alors que le problème général va fonctionner avec un polynôme de degré d+1. Ainsi, il suffit d'examiner le problème spécifique.

Laissez la chaîne d'entrée sera T[0 ... n-1]. La clé ici est de comprendre que si T[i] != T[i+k], puis ensuite, l'indice paire (i, i+k) crée une obstruction à l'existence d'un terme. Lorsque nous voyons une obstruction, nous pouvons diviser le problème en deux problèmes sur de courtes chaînes d'entrée: T[0 ... i+k-1] et T[i+1 ... n-1]. Si l'une de ces chaînes est trop court, alors l'algorithme n'émet rien et prend fin; c'est le moyen que la récursivité s'arrête lorsqu'un terme n'existe pas. Maintenant, regardez pour les obstructions un i+1, i+2, ..., jusqu'à l' i+k-1. Le cas échéant, cleave. D'autre part, s'il existe une séquence de [i ... i+k-1] avec aucun obstacle, alors nous avons une course avec une longueur 2k. Si nous trouvons une course, nous trouvons l'étendre au maximum (c'est facile), puis enchaînement sur le problème en trois morceaux: le préfixe, l'exécuter, et le suffixe. Nous émettons de la course et nous avons maintenant deux problèmes, le préfixe et le suffixe, chaque plus courte. Pour exécuter ce de manière récursive, en choisir un premier i valeur (n+k)/2.

La raison que c'est une réponse partielle, c'est que je pars de l'analyse que c'est un algorithme polynomial en temps. La raison que la preuve n'est pas trivial, c'est que, quand vous avez une obstruction, les longueurs i+k et n-i-1 ajouter jusqu'à n+k-1, ce qui est plus grand que n, il est donc concevable que l'apport total des longueurs sur une pile de récursion peut croître de façon exponentielle. Un autre raisonnement serait nécessaire pour montrer que ce n'est pas réellement se produire.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by: