Вычислить максимальное количество прогонов для данной строки длины

Ответ 1

Алгоритм поколений для поиска всех решений

Идея

В каждой строке последний символ может вносить только ограниченное количество прогонов.

Последний 0 может только добавить пробег в

10 + 0 => 100

поскольку в

00 + 0 => 000

это только повторение. Anf, если он добавляет минимальный пробег, следующий возможный минимальный запуск для добавления -

110010 + 0 => 1100100

заметьте еще раз

010010 + 0 => 0100100

не является дополнительным запуском, это повторение. Следующие возможные добавления:

111001001100100
1111001001100100111001001100100
...

Цифры могут меняться, но минимальные длины

3, 7, 15, 31

который

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

При запуске строки нет необходимости в другом символе, поэтому

maxaddlast = 4^n - 2

дает максимальное количество прогонов, которые могут быть добавлены добавлением последнего символа.

Алгоритм

• Пока выполняется поиск длины n, все варианты записываются со счетом запуска в [maxNumberOfRuns - maxaddlast (n + 1), maxNumberOfRuns].
• Чтобы найти решение с maxNumberOfRuns для n + 1, просто все записанные варианты расширены с помощью 0 и 1 и отмечены.

Семя

Оставшаяся проблема заключается в том, чтобы определить размер стека, чтобы собрать все варианты, которые необходимы для будущих семян.

Поскольку данных для угадывания допустимой формулы недостаточно, выбирается адаптивный алгоритм:

• Исходный размер стека для n угадывается из n - 1
• Для каждого решения проверяются используемые размеры стека, что в стеке всегда есть место 1.
• Если стек был полностью использован в некотором n, размер стека увеличивается, и вычисление перезапускается при n.

Результат

length 104 with 91 runs

достигается в течение 600 секунд. Затем память используется с настройками по умолчанию. Используйте -Xmx16G или более. Для больших номеров код должен быть изменен для сохранения семени на диске, а не в памяти.

И это намного быстрее, чем метод грубой силы.

** Код **

И вот мой пример кода в 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;
    }
}

Ответ 2

Частичный ответ. Идея состоит в том, чтобы взять страницу из строкового алгоритма поиска Boyer-Moore, модифицированного соответствующим образом, чтобы строка, которая должна быть сопоставлена, исходит из исходной строки.

Рассмотрим задачу для строки длины n, которая ищет пробеги периода k, где 2k < n. Если для этой задачи существует полиномиальный алгоритм времени, то для общей задачи существует один. Просто запустите такой алгоритм один раз для каждого 2 <= k <= n/2. Если конкретная проблема работает в O(p(n)), где p имеет степень d, то общая задача будет выполняться с полиномом степени d+1. Таким образом, достаточно рассмотреть конкретную проблему.

Пусть входная строка T[0 ... n-1]. Ключевым моментом здесь является осознание того, что если T[i] != T[i+k], то тогда пара индексов (i, i+k) создает препятствие для существования пробега. Когда мы видим препятствие, мы можем разбить задачу на две задачи на более короткие входные строки: T[0 ... i+k-1] и T[i+1 ... n-1]. Если какая-либо из этих строк слишком коротка, тогда алгоритм не испускает ничего и заканчивается; это так, что рекурсия завершается, когда пробег не существует. Теперь найдите препятствия a i+1, i+2,..., до i+k-1. Если таковые существуют, расщепите. С другой стороны, если существует последовательность [i ... i+k-1] без препятствий, то мы имеем пробег с длиной 2k. Если мы найдем пробег, мы обнаружим, что мы максимально расширяем его (это легко), а затем раскладываем проблему на три части: префикс, прогон и суффикс. Мы запускаем прогон, и теперь у нас есть две проблемы: префикс и суффикс, каждый из которых короче. Чтобы запустить этот рекурсивно, выберите начальный i со значением (n+k)/2.

Причина, по которой это частичный ответ, заключается в том, что я оставляю анализ, что это алгоритм полиномиального времени. Причина, по которой доказательство не является тривиальной, состоит в том, что если у вас есть препятствие, длины i+k и n-i-1 составляют n+k-1, что больше, чем n, поэтому можно предположить, что общая длина ввода на стеке рекурсии может расти экспоненциально. Еще один аргумент понадобится, чтобы показать, что это на самом деле не происходит.