Para um número inteiro positivo n, considere todas as cadeias binárias de comprimento 2n-1. Para uma determinada string S, Lseja uma matriz de comprimento nque contenha a contagem do número de 1s em cada substring de comprimento nde S. Por exemplo, se n=3e S = 01010então L=[1,2,1]. Chamamos La matriz de contagem de S.

Dizemos que duas seqüências de caracteres S1e S2o mesmo comprimento correspondem às suas respectivas matrizes de contagem L1e L2têm a propriedade que L1[i] <= 2*L2[i]e L2[i] <= 2*L1[i]para todos i.

Tarefa

Para aumentar o ninício de n=1, a tarefa é encontrar o tamanho do maior conjunto de strings, cada um de comprimento, 2n-1para que não haja duas strings correspondentes.

Seu código deve gerar um número por valor de n.

Ponto

Sua pontuação é a mais alta npara a qual ninguém postou uma resposta correta mais alta para nenhuma das suas respostas. Claramente, se você tiver todas as respostas ideais, obterá a pontuação mais alta que nvocê postar. No entanto, mesmo que sua resposta não seja ótima, você ainda pode obter a pontuação se ninguém mais conseguir vencê-la.

Respostas de exemplo

Pois n=1,2,3,4eu entendo 2,4,10,16.

Línguas e bibliotecas

Você pode usar qualquer idioma e bibliotecas disponíveis que desejar. Onde for possível, seria bom poder executar seu código, portanto, inclua uma explicação completa de como executar / compilar seu código no linux, se possível.

Entradas principais

• 5 por Martin Büttner em Mathematica
• 6 por Reto Koradi em C ++ . Valores são 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086. Os 5 primeiros são conhecidos por serem ótimos.
• 7 por Peter Taylor em Java . Valores são 2, 4, 10, 16, 31, 47, 76, 111, 166, 235.
• 9 por joriki em Java . Valores são 2, 4, 10, 16, 31, 47, 76, 112, 168.

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

Para cada n, esse código Java determina as possíveis matrizes de contagem e, em seguida, encontra conjuntos não correspondentes de tamanho crescente, para cada tamanho começando com um conjunto aleatório e melhorando-o pela descida mais íngreme aleatória. Em cada etapa, um dos elementos do conjunto é selecionado aleatoriamente uniformemente e substituído por outra matriz de contagem selecionada aleatoriamente uniformemente entre os que não estão em uso. A etapa é aceita se não aumentar o número de correspondências. Essa última receita parece ser crucial; aceitar etapas apenas se reduzirem o número de correspondências não é tão eficaz. As etapas que deixam o número de correspondências invariáveis ​​permitem que o espaço de pesquisa seja explorado e, eventualmente, algum espaço pode ser aberto para evitar uma das correspondências. Após 2 ^ 24 etapas sem melhoria, o tamanho anterior é gerado para o valor presente de n e n é incrementado.

Os resultados até n = 9 são 2, 4, 10, 16, 31, 47, 76, 112, 168, melhorando os resultados anteriores para n = 8 por um e para n = 9 por dois. Para valores mais altos de n, o limite de 2 ^ 24 etapas pode ter que ser aumentado.

Eu também tentei recozimento simulado (com o número de correspondências como a energia), mas sem melhorar a descida mais acentuada.

Código

salvar como Question54354.java
compilar com javac Question54354.java
executar comjava 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

Se considerarmos um gráfico Gcom os vértices 0a ne arestas que unem dois números que fósforo, então a potência tensor G^n tem vértices (x_0, ..., x_{n-1}), formando o poder cartesiano {0, ..., n}^ne arestas entre tuplos correspondentes. O gráfico de interesse é o subgrafo G^n induzido pelos vértices que correspondem às possíveis "matrizes de contagem".

Portanto, a primeira subtarefa é gerar esses vértices. A abordagem ingênua enumera sobre 2^{2n-1}strings, ou na ordem de 4^n. Mas se olharmos para a matriz das primeiras diferenças das matrizes de contagem, descobrimos que existem apenas 3^npossibilidades e, a partir das primeiras diferenças, podemos deduzir o intervalo de possíveis valores iniciais exigindo que nenhum elemento nas diferenças zero seja menor 0ou igual a maior que n.

Em seguida, queremos encontrar o conjunto independente máximo. Estou usando um teorema e duas heurísticas:

• Teorema: o conjunto independente máximo de uma união disjunta de gráficos é a união de seus conjuntos independentes máximos. Portanto, se dividirmos um gráfico em componentes não conectados, podemos simplificar o problema.
• Heurística: assuma que (n, n, ..., n)estará em um conjunto independente máximo. Há uma camarilha bastante grande de vértices, {m, m+1, ..., n}^nonde mé o menor número inteiro que corresponde n; (n, n, ..., n)é garantido que não há correspondências fora dessa camarilha.
• Heurística: adote a abordagem gananciosa de selecionar o vértice de menor grau.

No meu computador isto encontra 111para n=8em 16 segundos, 166para n=9em cerca de 8 minutos, e 235para n=10em cerca de 2 horas.

Código

Salve como PPCG54354.java, compile como javac PPCG54354.javae execute 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 strings

Acabei de escrever uma solução de força bruta usando os recursos do Mathematica para verificar as respostas de exemplo do Lembik, mas ele também pode lidar n = 5com:

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 um bônus, esse código produz uma visualização do problema como um gráfico em que cada aresta indica duas seqüências correspondentes.

Aqui está o gráfico para n = 3:

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

Isso está um pouco atrás do resultado de Peter Taylor, sendo 1 a 3 menor para n=7, 9e 10. A vantagem é que é muito mais rápido, para que eu possa executá-lo com valores mais altos de n. E isso pode ser entendido sem nenhuma matemática sofisticada. ;)

O código atual é dimensionado para executar até n=15. Os tempos de execução aumentam aproximadamente um fator de 4 para cada aumento em n. Por exemplo, foram 0,008 segundos para n=7, 0,07 segundos para n=9, 1,34 segundos para n=11, 27 segundos para n=13e 9 minutos para n=15.

Existem duas observações principais que usei:

• Em vez de operar com os próprios valores, a heurística opera contando matrizes. Para fazer isso, uma lista de todas as matrizes de contagem exclusivas é gerada primeiro.
• Usar matrizes de contagem com valores pequenos é mais benéfico, pois elimina menos espaço na solução. Isso é baseado em cada contagem, cexcluindo o intervalo de c / 2até 2 * cde outros valores. Para valores menores de c, esse intervalo é menor, o que significa que menos valores são excluídos usando-o.

Gere matrizes de contagem exclusivas

Fiz força bruta neste, iterando todos os valores, gerando a matriz de contagem para cada um deles e unificando a lista resultante. Isso certamente poderia ser feito com mais eficiência, mas é bom o suficiente para os tipos de valores com os quais estamos operando.

Isso é extremamente rápido para os pequenos valores. Para os valores maiores, a sobrecarga se torna substancial. Por exemplo, n=15ele usa cerca de 75% de todo o tempo de execução. Definitivamente, seria uma área para se olhar ao tentar ir muito mais alto do que n=15. Mesmo o uso da memória para criar uma lista de matrizes de contagem para todos os valores começaria a se tornar problemático.

O número de matrizes de contagem exclusivas é de cerca de 6% do número de valores para n=15. Essa contagem relativa se torna menor à medida que nse torna maior.

Seleção gananciosa dos valores da matriz de contagem

A parte principal do algoritmo seleciona os valores da matriz de contagem da lista gerada usando uma abordagem simples e gananciosa.

Com base na teoria de que o uso de matrizes de contagem com pequenas contagens é benéfico, as matrizes de contagem são classificadas pela soma de suas contagens.

Eles são então verificados em ordem e um valor é selecionado se for compatível com todos os valores usados ​​anteriormente. Portanto, isso envolve uma única passagem linear pelas matrizes de contagem exclusivas, em que cada candidato é comparado aos valores que foram selecionados anteriormente.

Tenho algumas idéias sobre como a heurística poderia ser potencialmente aprimorada. Mas isso parecia um ponto de partida razoável, e os resultados pareciam muito bons.

Código

Isso não é altamente otimizado. Eu tinha uma estrutura de dados mais elaborada em algum momento, mas seria necessário mais trabalho para generalizá-la além n=8, e a diferença no desempenho não parecia muito substancial.

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