Para un entero positivo dado n, considere todas las cadenas binarias de longitud 2n-1. Para una cadena dada S, dejemos Lser una matriz de longitud nque contiene el recuento del número de 1s en cada subcadena de longitudn de S. Por ejemplo, si n=3y S = 01010entonces L=[1,2,1]. Llamamos a Lla matriz de conteo de S.

Decimos que dos cuerdas S1y S2de la misma longitud coinciden si sus respectivas matrices de conteoL1 y L2tienen la propiedad eso L1[i] <= 2*L2[i]y L2[i] <= 2*L1[i]para todos i.

Tarea

Para aumentar a npartir de n=1, la tarea es encontrar el tamaño del conjunto de cadenas más grande, cada uno de longitud 2n-1para que no coincidan dos cadenas.

Su código debe generar un número por valor de n.

Puntuación

Su puntaje es el más alto npara el que nadie más ha publicado una respuesta correcta más alta para ninguna de sus respuestas. Claramente, si tiene todas las respuestas óptimas, obtendrá la puntuación más alta nque publique. Sin embargo, incluso si su respuesta no es la óptima, aún puede obtener el puntaje si nadie más puede superarlo.

Ejemplos de respuestas

Por lo n=1,2,3,4que entiendo 2,4,10,16.

Idiomas y bibliotecas

Puede usar cualquier idioma y bibliotecas disponibles que desee. Siempre que sea posible, sería bueno poder ejecutar su código, por lo tanto, si es posible, incluya una explicación completa sobre cómo ejecutar / compilar su código en Linux.

Entradas principales

• 5 por Martin Büttner en Mathematica
• 6 por Reto Koradi en C ++ . Los valores son2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086 . Se sabe que los primeros 5 son óptimos.
• 7 de Peter Taylor en Java . Los valores son 2, 4, 10, 16, 31, 47, 76, 111, 166, 235.
• 9 por joriki en Java . Los valores son 2, 4, 10, 16, 31, 47, 76, 112, 168.

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

Para cada n, este código de Java determina las posibles matrices de conteo y luego encuentra conjuntos no coincidentes de tamaño creciente, para cada tamaño que comienza con un conjunto aleatorio y lo mejora mediante el descenso aleatorio más pronunciado. En cada paso, uno de los elementos del conjunto se selecciona aleatoriamente de manera uniforme y se reemplaza por otro conjunto de conteo seleccionado aleatoriamente de manera uniforme entre los que no están en uso. El paso se acepta si no aumenta el número de coincidencias. Esta última prescripción parece ser crucial; aceptar pasos solo si reducen el número de coincidencias no es tan efectivo. Los pasos que dejan el número de coincidencias invariables permiten explorar el espacio de búsqueda y, finalmente, se puede abrir algo de espacio para evitar una de las coincidencias. Después de 2 ^ 24 pasos sin mejora, el tamaño anterior se genera para el valor presente de n, yn se incrementa.

Los resultados hasta n = 9 son 2, 4, 10, 16, 31, 47, 76, 112, 168 , mejorando en los resultados anteriores para n = 8 por uno y para n = 9 por dos. Para valores más altos de n, puede que sea necesario aumentar el límite de 2 ^ 24 pasos.

También probé el recocido simulado (con el número de partidos como la energía), pero sin mejorar el descenso más pronunciado.

Código

guardar como Question54354.java
compilar con javac Question54354.java
ejecutar conjava 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

Notas

Si consideramos un gráfico Gcon vértices 0a ny bordes de unión de dos números que partido, entonces el poder tensor G^n tiene vértices (x_0, ..., x_{n-1})que forman el poder cartesiano {0, ..., n}^ny bordes entre tuplas las características determinadas. El gráfico de interés es el subgrafo de G^n inducido por aquellos vértices que corresponden a las posibles "matrices de conteo".

Entonces, la primera subtarea es generar esos vértices. El enfoque ingenuo enumera sobre 2^{2n-1}cadenas, o en el orden de 4^n. Pero si en cambio observamos la matriz de primeras diferencias de las matrices de conteo, encontramos que solo hay 3^nposibilidades, y de las primeras diferencias podemos deducir el rango de posibles valores iniciales al requerir que ningún elemento en las diferencias de cero sea menor 0o mayor que n.

Entonces queremos encontrar el conjunto independiente máximo. Estoy usando un teorema y dos heurísticas:

• Teorema: el conjunto independiente máximo de una unión disjunta de gráficos es la unión de sus conjuntos independientes máximos. Entonces, si dividimos un gráfico en componentes no conectados, podemos simplificar el problema.
• Heurística: suponga que (n, n, ..., n)estará en un conjunto máximo independiente. Hay una camarilla de vértices bastante grande {m, m+1, ..., n}^ndonde mes el número entero más pequeño que coincide n;(n, n, ..., n)se garantiza que no tendrá partidos fuera de esa camarilla.
• Heurística: adopte el enfoque codicioso de seleccionar el vértice del grado más bajo.

En mi equipo esta hallazgos 111para n=8en 16 segundos, 166para n=9en unos 8 minutos, y 235para n=10en aproximadamente 2 horas.

Código

Guardar como PPCG54354.java, compilar como javac PPCG54354.javay ejecutar como 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 cuerdas

Acabo de escribir una solución de fuerza bruta usando las funciones integradas de Mathematica para verificar las respuestas de ejemplo de Lembik, pero también puede manejar 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

Como beneficio adicional, este código produce una visualización del problema como un gráfico donde cada borde indica dos cadenas coincidentes.

Aquí está el gráfico para n = 3:

C ++ (heurístico): 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086

Esto está ligeramente por detrás del resultado de Peter Taylor, siendo 1 a 3 más bajo para n=7, 9y 10. La ventaja es que es mucho más rápido, por lo que puedo ejecutarlo para valores más altos de n. Y se puede entender sin ninguna matemática elegante. ;)

El código actual está dimensionado para ejecutarse hasta n=15. Los tiempos de ejecución aumentan aproximadamente en un factor de 4 por cada aumento en n. Por ejemplo, fue 0.008 segundos n=7, 0.07 segundos n=9, 1.34 segundos n=11, 27 segundos n=13y 9 minutos n=15.

Hay dos observaciones clave que utilicé:

• En lugar de operar en los valores mismos, la heurística opera en matrices de conteo. Para hacer esto, primero se genera una lista de todos los arreglos de conteo únicos.
• Usar matrices de conteo con valores pequeños es más beneficioso, ya que eliminan menos espacio de la solución. Esto se basa en cada recuento, cexcluyendo el rango de c / 2a 2 * cde otros valores. Para valores más pequeños de c, este rango es más pequeño, lo que significa que se excluyen menos valores al usarlo.

Generar matrices de recuento únicas

Fui fuerza bruta en este, iterando a través de todos los valores, generando la matriz de conteo para cada uno de ellos y uniquificando la lista resultante. Ciertamente, esto podría hacerse de manera más eficiente, pero es lo suficientemente bueno para los tipos de valores con los que estamos operando.

Esto es extremadamente rápido para los valores pequeños. Para los valores más grandes, la sobrecarga se vuelve sustancial. Por ejemplo, para n=15, utiliza aproximadamente el 75% de todo el tiempo de ejecución. Definitivamente, este sería un área a tener en cuenta cuando se intenta ir mucho más alto que n=15. Incluso el uso de memoria para construir una lista de las matrices de conteo para todos los valores comenzaría a ser problemático.

El número de matrices de conteo únicas es aproximadamente el 6% del número de valores para n=15. Este recuento relativo se vuelve más pequeño a medida que se nhace más grande.

Selección codiciosa de valores de matriz de conteo

La parte principal del algoritmo selecciona los valores de la matriz de conteo de la lista generada utilizando un enfoque codicioso simple.

Según la teoría de que el uso de matrices de conteo con recuentos pequeños es beneficioso, las matrices de conteo se ordenan por la suma de sus recuentos.

Luego se verifican en orden y se selecciona un valor si es compatible con todos los valores utilizados anteriormente. Por lo tanto, esto implica un único paso lineal a través de las matrices de conteo únicas, donde cada candidato se compara con los valores que se seleccionaron previamente.

Tengo algunas ideas sobre cómo podría mejorarse la heurística. Pero esto parecía un punto de partida razonable, y los resultados parecían bastante buenos.

Código

Esto no está muy optimizado. Tenía una estructura de datos más elaborada en algún momento, pero habría necesitado más trabajo para generalizarla más allá n=8, y la diferencia en el rendimiento no parecía muy sustancial.

#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;
}