string - tengo - Calcule el número máximo de carreras posibles para una cadena de longitud dada

tengo 32 años que puedo estudiar

Question

Hace unas semanas, Lembik hizo la siguiente pregunta:

Un período p de una cadena w es cualquier entero positivo p tal que w[i]=w[i+p] cuando se definen ambos lados de esta ecuación. Deje per(w) denotar el tamaño del período más pequeño de w . Decimos que una cadena w es iff periódica per(w) <= |w|/2 .

De manera informal, una cadena periódica es solo una cadena compuesta de otra cadena repetida al menos una vez. La única complicación es que al final de la cadena no necesitamos una copia completa de la cadena repetida siempre que se repita en su totalidad al menos una vez.

Por ejemplo, considere la cadena x = abcab . per(abcab) = 3 como x[1] = x[1+3] = a , x[2]=x[2+3] = b y no hay un período más pequeño. La cadena abcab no es periódica. Sin embargo, la cadena ababa es periódica según per(ababa) = 2 .

Como más ejemplos, abcabca , ababababa y abcabcabc también son periódicos.

Para aquellos a los que les gustan las expresiones regulares, esta detecta si una cadena es periódica o no:

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

La tarea es encontrar todas las subcadenas periódicas máximas en una cadena más larga. A veces se llaman carreras en la literatura.

Una subcadena w[i,j] de w es una subcadena periódica máxima (ejecución) si es periódica y ni w[i-1] = w[i-1+p] ni w[j+1] = w[j+1-p] . Informalmente, la "ejecución" no se puede contener en una "ejecución" más grande con el mismo período.

Debido a que dos ejecuciones pueden representar la misma cadena de caracteres que ocurre en diferentes lugares en la cadena general, representaremos las ejecuciones por intervalos. Aquí está la definición anterior repetida en términos de intervalos.

Una ejecución (o subcadena periódica máxima) en una cadena T es un intervalo [i...j] con j>=i , tal que

• T[i...j] es una palabra periódica con el período p = per(T[i...j])
• Es máximo Formalmente, ni T[i-1] = T[i-1+p] ni T[j+1] = T[j+1-p] . Informalmente, la carrera no se puede contener en una carrera más grande con el mismo período.

Denote por RUNS(T) el conjunto de ejecuciones en la cadena T

Ejemplos de carreras

• Las cuatro subcadenas periódicas máximas (ejecuciones) en la cadena T = atattatt son T[4,5] = tt , T[7,8] = tt , T[1,4] = atat , T[2,8] = tattatt .

• La cadena T = aabaabaaaacaacac contiene las siguientes 7 subcadenas periódicas máximas (ejecuciones): 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 cadena T = atatbatatb contiene las siguientes tres ejecuciones. Ellos son: T[1, 4] = atat , T[6, 9] = atat y T[1, 10] = atatbatatb .

Aquí estoy usando 1 indexación.

La meta

Escriba el código de modo que para cada entero n que comienza en 2, genere el mayor número de carreras contenidas en cualquier cadena binaria de longitud n .

Ejemplo optima

En lo siguiente: 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

¿Hay una forma más rápida de encontrar el número óptimo de carreras para valores de n mayores que un enfoque de tiempo ingenuo O (n ^ 2 2 ^ n)?

Answer 1

Respuesta parcial. La idea es tomar una página del algoritmo de búsqueda de cadenas de Boyer-Moore, modificada adecuadamente para que la cadena que se va a combinar provenga de la cadena fuente.

Considere el problema para una cadena de longitud n busca ejecuciones del período k , donde 2k < n . Si hay un algoritmo de tiempo polinomial para este problema, entonces hay uno para el problema general. Simplemente ejecute dicho algoritmo una vez para cada 2 <= k <= n/2 . Si el problema específico se ejecuta en O(p(n)) donde p tiene un grado d , entonces el problema general se ejecutará con un polinomio de grado d+1 . Por lo tanto, es suficiente para examinar el problema específico.

Deje que la cadena de entrada sea T[0 ... n-1] . La clave aquí es darse cuenta de que si T[i] != T[i+k] , entonces el par índice (i, i+k) crea una obstrucción a la existencia de una ejecución. Cuando vemos una obstrucción, podemos subdividir el problema en dos problemas en cadenas de entrada más cortas: T[0 ... i+k-1] y T[i+1 ... n-1] . Si cualquiera de estas cadenas es demasiado corta, entonces el algoritmo no emite nada y termina; esta es la forma en que la recursividad termina cuando una ejecución no existe. Ahora busque obstrucciones a i+1 , i+2 , ..., hasta i+k-1 . Si hay alguno, escinde. Por otro lado, si hay una secuencia [i ... i+k-1] sin obstrucciones, entonces tenemos una carrera con longitud 2k . Si encontramos una ejecución, descubrimos que la ampliamos al máximo (eso es fácil) y luego dividimos el problema en tres partes: el prefijo, la ejecución y el sufijo. Emitimos la corrida y ahora tenemos dos problemas, el prefijo y el sufijo, cada uno más corto. Para ejecutar esto recursivamente, elija una i inicial con valor (n+k)/2 .

La razón por la cual esta es una respuesta parcial es que estoy dejando fuera el análisis de que este es un algoritmo de tiempo polinomial. La razón por la que la prueba no es trivial es que, cuando tienes una obstrucción, las longitudes i+k y ni-1 suman n+k-1 , que es mayor que n , por lo que es concebible que las longitudes de entrada totales en una pila de recursión podría crecer exponencialmente. Algún argumento adicional sería necesario para mostrar que esto no ocurre en realidad.

Answer 2

Un algoritmo generacional para encontrar todas las soluciones

La idea

En cada cadena, el último personaje solo puede contribuir a un número limitado de ejecuciones.

Un último 0 solo puede agregar una ejecución a

10 + 0 => 100

ya que en

00 + 0 => 000

es solo una repetición. Anf si agrega esa corrida mínima, la siguiente carrera mínima posible para agregar es

110010 + 0 => 1100100

nota de nuevo

010010 + 0 => 0100100

no es una ejecución adicional, es una repetición. Las siguientes posibles adiciones son

111001001100100
1111001001100100111001001100100
...

Los dígitos pueden variar, pero las longitudes mínimas son

3, 7, 15, 31

cual es

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

Al comienzo de la secuencia no hay necesidad de un personaje diferente, por lo tanto

maxaddlast = 4^n - 2

cede el número máximo de carreras que se pueden agregar agregando el último carácter.

El algoritmo

• Mientras se realiza la búsqueda de la longitud n, todas las variantes se registran con un recuento de ejecución en [maxNumberOfRuns - maxaddlast (n + 1), maxNumberOfRuns].
• Para encontrar una solución con maxNumberOfRuns para n + 1, simplemente todas las variantes registradas se extienden con 0 y 1 y se marcan.

La semilla

El problema restante es dimensionar la pila para recoger todas las variantes que se requieren para las futuras semillas.

Como no hay suficientes datos para adivinar una fórmula válida, se elige un algoritmo adaptativo:

1. El tamaño de pila inicial para n se adivina desde n - 1
2. Para cada solución, se verifican los tamaños de pila usados ​​que siempre hay espacio por 1 en la pila.
3. Si la pila se utilizó por completo en algún n, el tamaño de la pila aumenta y el cálculo se reinicia en n.

El resultado

length 104 with 91 runs

se alcanza en 600 segundos. Luego, la memoria se utiliza con la configuración predeterminada. Use -Xmx16G o más. Para números más grandes, el código debe ser modificado para mantener la semilla en el disco, no en la memoria.

Y es mucho más rápido que el método de fuerza bruta.

** El código **

Y aquí está mi código de ejemplo 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;
    }
}