Для данного положительного целого числа nрассмотрим все двоичные строки длины 2n-1. Для данной строки S, не говоря Lбыть массивом длиной , nкоторый содержит счетчик числа 1х в каждой подстроке длиной nиз S. Например, если n=3и S = 01010тогда L=[1,2,1]. Мы называем Lсчетный массив S.

Мы говорим , что две строки S1и S2той же длины матча , если их соответствующие счетные массивы L1и L2обладают свойством , что L1[i] <= 2*L2[i]и L2[i] <= 2*L1[i]для всех i.

задача

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

Ваш код должен выводить одно число на значение n.

Гол

Ваша оценка является самой высокой, nза которую никто другой не опубликовал более правильный ответ ни для одного из ваших ответов. Очевидно, что если у вас есть все оптимальные ответы, вы получите балл за самый высокий nпост. Тем не менее, даже если ваш ответ не является оптимальным, вы все равно можете получить счет, если никто другой не сможет его побить.

Пример ответов

Ибо n=1,2,3,4я получаю 2,4,10,16.

Языки и библиотеки

Вы можете использовать любой доступный язык и библиотеки, которые вам нравятся. Там, где это возможно, было бы хорошо иметь возможность запускать ваш код, поэтому, пожалуйста, включите полное объяснение того, как запускать / компилировать ваш код в Linux, если это вообще возможно.

Ведущие записи

• 5 от Мартина Бюттнера в Mathematica
• 6 Рето Коради в C ++ . Ценности есть 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086. Первые 5, как известно, являются оптимальными.
• 7 Питером Тейлором на Яве . Ценности есть 2, 4, 10, 16, 31, 47, 76, 111, 166, 235.
• 9 от joriki на Яве . Ценности есть 2, 4, 10, 16, 31, 47, 76, 112, 168.

2, 4, 10, 16, 31, 47, 76, 112, 168

Для каждого n этот код Java определяет возможные массивы подсчета и затем находит несоответствующие наборы увеличивающегося размера, для каждого размера, начиная со случайного набора и улучшая его путем рандомизированного наискорейшего спуска. На каждом этапе один из элементов набора случайно выбирается равномерно и заменяется другим счетным массивом, случайно выбранным среди тех, которые не используются. Шаг считается принятым, если он не увеличивает количество совпадений. Этот последний рецепт, кажется, имеет решающее значение; принимать шаги, только если они уменьшают количество совпадений, не так эффективно. Шаги, оставляющие количество совпадений неизменным, позволяют исследовать пространство поиска, и в конечном итоге может открыться некоторое пространство, чтобы избежать одного из совпадений. После 2 ^ 24 шагов без улучшения, предыдущий размер выводится для текущего значения n, и n увеличивается.

Результаты до n = 9 2, 4, 10, 16, 31, 47, 76, 112, 168улучшаются по сравнению с предыдущими результатами для n = 8 на один и для n = 9 на два. Для более высоких значений n может быть увеличено ограничение в 2 ^ 24 шага.

Я также пробовал моделируемый отжиг (с количеством спичек в качестве энергии), но без улучшения по сравнению с самым крутым спуском.

Код

сохранить как Question54354.java
скомпилировать с javac Question54354.java
запустить сjava Question54354

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Question54354 {
    static class Array {
        int [] arr;

        public Array (int [] arr) {
            this.arr = arr;
        }

        public int hashCode () {
            return Arrays.hashCode (arr);
        }

        public boolean equals (Object o) {
            return Arrays.equals (((Array) o).arr,arr);
        }
    }

    static int [] indices;
    static int [] [] counts;
    static boolean [] used;

    static Random random = new Random (0);

    static boolean match (int [] c1,int [] c2) {
        for (int k = 0;k < c1.length;k++)
            if (c1 [k] > 2 * c2 [k] || c2 [k] > 2 * c1 [k])
                return false;
        return true;
    }

    static int matches (int i) {
        int result = 0;
        for (int j = 0;j < indices.length;j++)
            if (j != i && match (counts [indices [i]],counts [indices [j]]))
                result++;
        return result;
    }

    static void randomize (int i) {
        do
            indices [i] = random.nextInt (counts.length);
        while (used [indices [i]]);
    }

    public static void main (String [] args) {
        for (int n = 1,length = 1;;n++,length += 2) {
            int [] lookup = new int [1 << n];
            for (int string = 0;string < 1 << n;string++)
                for (int bit = 1;bit < 1 << n;bit <<= 1)
                    if ((string & bit) != 0)
                        lookup [string]++;
            Set<Array> arrays = new HashSet<Array> ();
            for (int string = 0;string < 1 << length;string++) {
                int [] count = new int [n];
                for (int i = 0;i < n;i++)
                    count [i] = lookup [(string >> i) & ((1 << n) - 1)];
                arrays.add (new Array (count));
            }
            counts = new int [arrays.size ()] [];
            int j = 0;
            for (Array array : arrays)
                counts [j++] = array.arr;
            used = new boolean [counts.length];

            int m;
            outer:
            for (m = 1;m <= counts.length;m++) {
                indices = new int [m];
                for (;;) {
                    Arrays.fill (used,false);
                    for (int i = 0;i < m;i++) {
                        randomize (i);
                        used [indices [i]] = true;
                    }
                    int matches = 0;
                    for (int i = 0;i < m;i++)
                        matches += matches (i);
                    matches /= 2;
                    int stagnation = 0;
                    while (matches != 0) {
                        int k = random.nextInt (m);
                        int oldMatches = matches (k);
                        int oldIndex = indices [k];
                        randomize (k);
                        int newMatches = matches (k);
                        if (newMatches <= oldMatches) {
                            if (newMatches < oldMatches) {
                                matches += newMatches - oldMatches;
                                stagnation = 0;
                            }
                            used [oldIndex] = false;
                            used [indices [k]] = true;
                        }
                        else
                            indices [k] = oldIndex;

                        if (++stagnation == 0x1000000)
                            break outer;
                    }
                    break;
                }
            }
            System.out.println (n + " : " + (m - 1));
        }
    }
}

2, 4, 10, 16, 31, 47, 76, 111, 166, 235

Примечания

Если мы рассмотрим граф Gс вершинами 0до nи ребер , соединяющих две цифры , которые совпадают, то тензор мощность G^n имеет вершины , (x_0, ..., x_{n-1})образующие декартова степени {0, ..., n}^nи ребро между согласующими кортежами. Представляющий интерес граф является подграфом, G^n индуцированным теми вершинами, которые соответствуют возможным «счетным массивам».

Итак, первая подзадача состоит в том, чтобы создать эти вершины. Наивный подход перечисляет над 2^{2n-1}строками или порядка 4^n. Но если мы вместо этого посмотрим на массив первых разностей счетных массивов, мы обнаружим, что есть только 3^nвозможности, и из первых различий мы можем вывести диапазон возможных начальных значений, требуя, чтобы ни один элемент в нулевых разностях не был меньше 0или больше чем n.

Затем мы хотим найти максимальный независимый набор. Я использую одну теорему и две эвристики:

• Теорема: максимальное независимое множество непересекающегося объединения графов - это объединение их максимальных независимых множеств. Поэтому, если мы разбиваем график на несвязанные компоненты, мы можем упростить задачу.
• Эвристика: предположим, что (n, n, ..., n)будет в максимально независимом наборе. Есть довольно большая клика вершин, {m, m+1, ..., n}^nгде mнаименьшее целое число, которое соответствует n; (n, n, ..., n)гарантированно не будет совпадений за пределами этой клики.
• Эвристика: используйте жадный подход выбора вершины самой низкой степени.

На моем компьютере это происходит 111за n=816 секунд, 166за n=98 минут и 235за n=102 часа.

Код

Сохранить как PPCG54354.java, скомпилировать как javac PPCG54354.javaи запустить как java PPCG54354.

import java.util.*;

public class PPCG54354 {
    public static void main(String[] args) {
        for (int n = 1; n < 20; n++) {
            long start = System.nanoTime();

            Set<Vertex> constructive = new HashSet<Vertex>();
            for (int i = 0; i < (int)Math.pow(3, n-1); i++) {
                int min = 0, max = 1, diffs[] = new int[n-1];
                for (int j = i, k = 0; k < n-1; j /= 3, k++) {
                    int delta = (j % 3) - 1;
                    if (delta == -1) min++;
                    if (delta != 1) max++;
                    diffs[k] = delta;
                }

                for (; min <= max; min++) constructive.add(new Vertex(min, diffs));
            }

            // Heuristic: favour (n, n, ..., n)
            Vertex max = new Vertex(n, new int[n-1]);
            Iterator<Vertex> it = constructive.iterator();
            while (it.hasNext()) {
                Vertex v = it.next();
                if (v.matches(max) && !v.equals(max)) it.remove();
            }

            Set<Vertex> ind = independentSet(constructive, n);
            System.out.println(ind.size() + " after " + ((System.nanoTime() - start) / 1000000000L) + " secs");
        }
    }

    private static Set<Vertex> independentSet(Set<Vertex> vertices, int dim) {
        if (vertices.size() < 2) return vertices;

        for (int idx = 0; idx < dim; idx++) {
            Set<Set<Vertex>> p = connectedComponents(vertices, idx);
            if (p.size() > 1) {
                Set<Vertex> ind = new HashSet<Vertex>();
                for (Set<Vertex> part : connectedComponents(vertices, idx)) {
                    ind.addAll(independentSet(part, dim));
                }
                return ind;
            }
        }

        // Greedy
        int minMatches = Integer.MAX_VALUE;
        Vertex minV = null;
        for (Vertex v0 : vertices) {
            int numMatches = 0;
            for (Vertex vi : vertices) if (v0.matches(vi)) numMatches++;
            if (numMatches < minMatches) {
                minMatches = numMatches;
                minV = v0;
            }
        }

        Set<Vertex> nonmatch = new HashSet<Vertex>();
        for (Vertex vi : vertices) if (!minV.matches(vi)) nonmatch.add(vi);
        Set<Vertex> ind = independentSet(nonmatch, dim);
        ind.add(minV);
        return ind;
    }

    // Separates out a set of vertices which form connected components when projected into the idx axis.
    private static Set<Set<Vertex>> connectedComponents(Set<Vertex> vertices, final int idx) {
        List<Vertex> sorted = new ArrayList<Vertex>(vertices);
        Collections.sort(sorted, new Comparator<Vertex>() {
                public int compare(Vertex a, Vertex b) {
                    return a.x[idx] - b.x[idx];
                }
            });

        Set<Set<Vertex>> connectedComponents = new HashSet<Set<Vertex>>();
        Set<Vertex> current = new HashSet<Vertex>();
        int currentVal = 0;
        for (Vertex v : sorted) {
            if (!match(currentVal, v.x[idx]) && !current.isEmpty()) {
                connectedComponents.add(current);
                current = new HashSet<Vertex>();
            }

            current.add(v);
            currentVal = v.x[idx];
        }

        if (!current.isEmpty()) connectedComponents.add(current);
        return connectedComponents;
    }

    private static boolean match(int a, int b) {
        return a <= 2 * b && b <= 2 * a;
    }

    private static class Vertex {
        final int[] x;
        private final int h;

        Vertex(int[] x) {
            this.x = x.clone();

            int _h = 0;
            for (int xi : x) _h = _h * 37 + xi;
            h = _h;
        }

        Vertex(int x0, int[] diffs) {
            x = new int[diffs.length + 1];
            x[0] = x0;
            for (int i = 0; i < diffs.length; i++) x[i+1] = x[i] + diffs[i];

            int _h = 0;
            for (int xi : x) _h = _h * 37 + xi;
            h = _h;
        }

        public boolean matches(Vertex v) {
            if (v == this) return true;
            if (x.length != v.x.length) throw new IllegalArgumentException("v");
            for (int i = 0; i < x.length; i++) {
                if (!match(x[i], v.x[i])) return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            return h;
        }

        @Override
        public boolean equals(Object obj) {
            return (obj instanceof Vertex) && equals((Vertex)obj);
        }

        public boolean equals(Vertex v) {
            if (v == this) return true;
            if (x.length != v.x.length) return false;
            for (int i = 0; i < x.length; i++) {
                if (x[i] != v.x[i]) return false;
            }
            return true;
        }

        @Override
        public String toString() {
            if (x.length == 0) return "e";

            StringBuilder sb = new StringBuilder(x.length);
            for (int xi : x) sb.append(xi < 10 ? (char)('0' + xi) : (char)('A' + xi - 10));
            return sb.toString();
        }
    }
}

Mathematica n = 5,, 31 строка

Я только что написал решение для грубой силы, используя встроенные модули Mathematica, чтобы проверить примеры ответов Лембика, но оно также может справиться n = 5:

n = 5;
s = Tuples[{0, 1}, 2 n - 1];
l = Total /@ Partition[#, n, 1] & /@ s
g = Graph[l, 
  Cases[Join @@ Outer[UndirectedEdge, l, l, 1], 
   a_ <-> b_ /; 
    a != b && And @@ Thread[a <= 2 b] && And @@ Thread[b <= 2 a]]]
set = First@FindIndependentVertexSet[g]
Length@set

В качестве бонуса этот код создает визуализацию проблемы в виде графика, где каждое ребро указывает две совпадающие строки.

Вот график для n = 3:

C ++ (эвристический): 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086

Это немного отстает от результата Питера Тейлора, будучи на 1–3 меньше n=7, 9и 10. Преимущество в том, что это намного быстрее, поэтому я могу запустить его для более высоких значений n. И это можно понять без всякой причудливой математики. ;)

Текущий код рассчитан на запуск n=15. Время выполнения увеличивается примерно в 4 раза для каждого увеличения n. Например, это было 0,008 секунды n=7, 0,07 секунды n=9, 1,34 секунды n=11, 27 секунд n=13и 9 минут n=15.

Я использовал два ключевых наблюдения:

• Вместо того, чтобы воздействовать на сами значения, эвристика работает на подсчете массивов. Для этого сначала создается список всех уникальных счетных массивов.
• Использование подсчета массивов с небольшими значениями более выгодно, так как они уменьшают пространство решения. Это основано на каждом счете за cисключением диапазона c / 2для 2 * cдругих значений. Для меньших значений cэтот диапазон меньше, что означает, что меньшее количество значений исключается при его использовании.

Генерация уникальных массивов подсчета

Я использовал грубую силу, перебирая все значения, генерируя массив count для каждого из них и выводя результирующий список. Конечно, это можно сделать более эффективно, но этого достаточно для тех значений, с которыми мы работаем.

Это очень быстро для небольших значений. Для больших значений накладные расходы становятся существенными. Например, для n=15него используется около 75% всего времени выполнения. Это определенно будет область, на которую стоит обратить внимание при попытке подняться намного выше n=15. Даже просто использование памяти для построения списка подсчитывающих массивов для всех значений станет проблематичным.

Количество уникальных счетных массивов составляет около 6% от количества значений для n=15. Этот относительный счет становится меньше, когда nстановится больше.

Жадный выбор подсчета значений массива

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

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

Затем они проверяются по порядку, и выбирается значение, если оно совместимо со всеми ранее использованными значениями. Таким образом, это включает в себя один линейный проход через уникальные счетные массивы, где каждый кандидат сравнивается с ранее выбранными значениями.

У меня есть некоторые идеи о том, как можно улучшить эвристику. Но это казалось разумной отправной точкой, и результаты выглядели довольно хорошо.

Код

Это не очень оптимизировано. В какой-то момент у меня была более сложная структура данных, но для ее обобщения потребовалось бы больше работы n=8, и разница в производительности не казалась существенной.

#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>

typedef uint32_t Value;

class Counter {
public:
    static void setN(int n);

    Counter();
    Counter(Value val);

    bool operator==(const Counter& rhs) const;
    bool operator<(const Counter& rhs) const;

    bool collides(const Counter& other) const;

private:
    static const int FIELD_BITS = 4;
    static const uint64_t FIELD_MASK = 0x0f;

    static int m_n;
    static Value m_valMask;

    uint64_t fieldSum() const;

    uint64_t m_fields;
};

void Counter::setN(int n) {
    m_n = n;
    m_valMask = (static_cast<Value>(1) << n) - 1;
}

Counter::Counter()
  : m_fields(0) {
}

Counter::Counter(Value val) {
    m_fields = 0;
    for (int k = 0; k < m_n; ++k) {
        m_fields <<= FIELD_BITS;
        m_fields |= __builtin_popcount(val & m_valMask);
        val >>= 1;
    }
}

bool Counter::operator==(const Counter& rhs) const {
    return m_fields == rhs.m_fields;
}

bool Counter::operator<(const Counter& rhs) const {
    uint64_t lhsSum = fieldSum();
    uint64_t rhsSum = rhs.fieldSum();
    if (lhsSum < rhsSum) {
        return true;
    }
    if (lhsSum > rhsSum) {
        return false;
    }

    return m_fields < rhs.m_fields;
}

bool Counter::collides(const Counter& other) const {
    uint64_t fields1 = m_fields;
    uint64_t fields2 = other.m_fields;

    for (int k = 0; k < m_n; ++k) {
        uint64_t c1 = fields1 & FIELD_MASK;
        uint64_t c2 = fields2 & FIELD_MASK;

        if (c1 > 2 * c2 || c2 > 2 * c1) {
            return false;
        }

        fields1 >>= FIELD_BITS;
        fields2 >>= FIELD_BITS;
    }

    return true;
}

int Counter::m_n = 0;
Value Counter::m_valMask = 0;

uint64_t Counter::fieldSum() const {
    uint64_t fields = m_fields;
    uint64_t sum = 0;
    for (int k = 0; k < m_n; ++k) {
        sum += fields & FIELD_MASK;
        fields >>= FIELD_BITS;
    }

    return sum;
}

typedef std::vector<Counter> Counters;

int main(int argc, char* argv[]) {
    int n = 0;
    std::istringstream strm(argv[1]);
    strm >> n;

    Counter::setN(n);

    int nBit = 2 * n - 1;
    Value maxVal = static_cast<Value>(1) << nBit;

    Counters allCounters;

    for (Value val = 0; val < maxVal; ++val) {
        Counter counter(val);
        allCounters.push_back(counter);
    }

    std::sort(allCounters.begin(), allCounters.end());

    Counters::iterator uniqEnd =
        std::unique(allCounters.begin(), allCounters.end());
    allCounters.resize(std::distance(allCounters.begin(), uniqEnd));

    Counters solCounters;
    int nSol = 0;

    for (Value idx = 0; idx < allCounters.size(); ++idx) {
        const Counter& counter = allCounters[idx];

        bool valid = true;
        for (int iSol = 0; iSol < nSol; ++iSol) {
            if (solCounters[iSol].collides(counter)) {
                valid = false;
                break;
            }
        }

        if (valid) {
            solCounters.push_back(counter);
            ++nSol;
        }
    }

    std::cout << "result: " << nSol << std::endl;

    return 0;
}