Dla danej dodatniej liczby całkowitej nnależy uwzględnić wszystkie ciągi binarne długości 2n-1. Dla danego łańcucha S, niech Lbędzie tablica długości n, który zawiera licznik liczby 1sekund w każdym z fragmentu o długości nod S. Na przykład, jeśli n=3i S = 01010wtedy L=[1,2,1]. Nazywamy Ltablicę zliczającą S.

Mówimy, że dwa ciągi S1i S2tej samej długości meczu jeśli ich odpowiednie tablice liczenia L1i L2mają tę właściwość, że L1[i] <= 2*L2[i]i L2[i] <= 2*L1[i]dla wszystkich i.

Zadanie

Aby zwiększyć, nzaczynając od n=1, zadaniem jest znalezienie rozmiaru największego zestawu ciągów, z których każdy ma długość, 2n-1tak aby żadne dwa ciągi nie pasowały.

Twój kod powinien wypisywać jedną liczbę na wartość n.

Wynik

Twój wynik jest najwyższy, ndla którego nikt inny nie opublikował wyższej poprawnej odpowiedzi na którąkolwiek z twoich odpowiedzi. Oczywiście, jeśli masz wszystkie optymalne odpowiedzi, otrzymasz wynik za najwyższą, nktórą opublikujesz. Jednak nawet jeśli twoja odpowiedź nie jest optymalna, nadal możesz uzyskać wynik, jeśli nikt inny go nie pokona.

Przykładowe odpowiedzi

Bo n=1,2,3,4dostaję 2,4,10,16.

Języki i biblioteki

Możesz użyć dowolnego dostępnego języka i bibliotek, które ci się podobają. Tam, gdzie to możliwe, dobrze byłoby móc uruchomić kod, więc proszę podać pełne wyjaśnienie, w jaki sposób uruchomić / skompilować kod w systemie Linux, jeśli to w ogóle możliwe.

Wiodące wpisy

• 5 autorstwa Martina Büttnera w Mathematica
• 6 autorstwa Reto Koradi w C ++ . Wartości są 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086. Pierwsze 5 jest znanych jako optymalne.
• 7 autorstwa Petera Taylora w Javie . Wartości są 2, 4, 10, 16, 31, 47, 76, 111, 166, 235.
• 9 autorstwa joriki w Javie . Wartości są 2, 4, 10, 16, 31, 47, 76, 112, 168.

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

Dla każdego n ten kod Java określa możliwe tablice zliczające, a następnie znajduje niepasujące zestawy o rosnącym rozmiarze, dla każdego rozmiaru rozpoczynającego się od zestawu losowego i ulepszającego go przez losowe najbardziej strome zejście. Na każdym etapie jeden z elementów zestawu jest losowo wybierany równomiernie i zastępowany przez inny układ liczący losowo wybierany losowo spośród nieużywanych. Krok zostanie zaakceptowany, jeśli nie zwiększy liczby dopasowań. Ta ostatnia recepta wydaje się być kluczowa; akceptowanie kroków tylko wtedy, gdy zmniejszają liczbę dopasowań, nie jest tak skuteczne. Kroki pozostawiające niezmienną liczbę dopasowań pozwalają na zbadanie przestrzeni wyszukiwania, a ostatecznie może zostać otwarta przestrzeń, aby uniknąć jednego z dopasowań. Po 2 ^ 24 krokach bez poprawy poprzedni rozmiar jest wyprowadzany dla bieżącej wartości n, a n jest zwiększany.

Wyniki do n = 9 są 2, 4, 10, 16, 31, 47, 76, 112, 168lepsze od poprzednich wyników dla n = 8 o jeden i dla n = 9 o dwa. W przypadku wyższych wartości n może być konieczne zwiększenie limitu 2 ^ 24 kroków.

Próbowałem również symulować wyżarzanie (z liczbą dopasowań jako energią), ale bez poprawy w porównaniu z najbardziej stromym spadkiem.

Kod

zapisz jako Question54354.java
kompiluj z javac Question54354.java
uruchom zjava 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

Notatki

Jeśli weźmiemy pod uwagę wykres Gz wierzchołkami 0do ni krawędziami łączącymi dwie pasujące liczby, to siła tensora G^n ma wierzchołki (x_0, ..., x_{n-1})tworzące siłę kartezjańską {0, ..., n}^ni krawędzie między pasującymi krotkami. Wykres zainteresowania to podrozdział G^n indukowany przez te wierzchołki, które odpowiadają możliwym „macierzom zliczającym”.

Zatem pierwszym podzadaniem jest wygenerowanie tych wierzchołków. Naiwne podejście wylicza ponad 2^{2n-1}łańcuchami lub według kolejności 4^n. Jeśli jednak spojrzymy na tablicę pierwszych różnic tablic liczących, stwierdzimy, że są tylko 3^nmożliwości, a na podstawie pierwszych różnic możemy wydedukować zakres możliwych wartości początkowych, wymagając, aby żaden element w zerowych różnicach nie był mniejszy niż 0lub większy niż n.

Następnie chcemy znaleźć maksymalny niezależny zestaw. Używam jednego twierdzenia i dwóch heurystyk:

• Twierdzenie: maksymalny niezależny zbiór rozłącznego połączenia grafów jest połączeniem ich maksymalnych niezależnych zbiorów. Więc jeśli podzielimy wykres na niepowiązane komponenty, możemy uprościć problem.
• Heurystyczny: załóżmy, że (n, n, ..., n)będzie to maksymalnie niezależny zestaw. Jest dość duża klika wierzchołków, {m, m+1, ..., n}^ngdzie mjest najmniejszą liczbą całkowitą, która pasuje n; (n, n, ..., n)gwarantuje, że nie będzie pasować poza tą kliką.
• Heurystyczny: podejmij chciwe podejście do wyboru wierzchołka najniższego stopnia.

Na moim komputerze jest to wykrywane 111przez n=816 sekund, 166przez n=9około 8 minut i 235przez n=10około 2 godziny.

Kod

Zapisz jako PPCG54354.java, skompiluj jako javac PPCG54354.javai uruchom jako 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 strun

Właśnie napisałem rozwiązanie brutalnej siły przy użyciu wbudowanych aplikacji Mathematica, aby zweryfikować przykładowe odpowiedzi Lembika, ale może ono również obsłużyć 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

Jako bonus, ten kod tworzy wizualizację problemu w postaci wykresu, na którym każda krawędź wskazuje dwa pasujące ciągi.

Oto wykres dla n = 3:

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

Jest to nieco poniżej wyniku Petera Taylora, będąc o 1 do 3 niższym dla n=7, 9i 10. Zaletą jest to, że jest znacznie szybszy, więc mogę uruchomić go dla wyższych wartości n. I można to zrozumieć bez jakiejkolwiek fantazyjnej matematyki. ;)

Bieżący kod jest zwymiarowany do uruchomienia n=15. Czasy pracy zwiększają się z grubsza o współczynnik 4 dla każdego wzrostu w n. Na przykład było to 0,008 sekundy dla n=7, 0,07 sekundy dla n=9, 1,34 sekundy dla n=11, 27 sekund dla n=13i 9 minut dla n=15.

Użyłem dwóch kluczowych obserwacji:

• Zamiast operować na samych wartościach, heurystyka działa na liczeniu tablic. W tym celu najpierw generowana jest lista wszystkich unikalnych tablic zliczających.
• Korzystanie z tablic zliczających o małych wartościach jest bardziej korzystne, ponieważ eliminują one mniej miejsca na rozwiązanie. Opiera się to na każdym liczyć cz wyłączeniem zakres c / 2do 2 * cinnych wartości. W przypadku mniejszych wartości cten zakres jest mniejszy, co oznacza, że ​​przy jego użyciu wykluczonych jest mniej wartości.

Generuj unikalne tablice liczące

Wykorzystałem tę brutalną siłę, iterując wszystkie wartości, generując tablicę zliczeń dla każdej z nich i ujednolicając wynikową listę. Z pewnością można to zrobić bardziej efektywnie, ale jest wystarczająco dobre dla rodzajów wartości, z którymi operujemy.

Jest to niezwykle szybkie w przypadku małych wartości. W przypadku większych wartości narzut staje się znaczny. Na przykład n=15używa około 75% całego środowiska wykonawczego. To zdecydowanie byłby obszar, na który należy zwrócić uwagę, gdy próbuje się wznieść znacznie wyżej n=15. Problemem może stać się nawet użycie pamięci do budowania listy tablic zliczających dla wszystkich wartości.

Liczba unikalnych tablic zliczających wynosi około 6% liczby wartości n=15. Ta względna liczba maleje wraz ze nwzrostem.

Chciwy wybór wartości tablicy zliczającej

Główna część algorytmu wybiera zliczanie wartości tablic z wygenerowanej listy, stosując proste podejście zachłanne.

W oparciu o teorię, że korzystanie z tablic zliczających z małą liczbą jest korzystne, tablice zliczające są sortowane według sumy ich zliczeń.

Są one następnie sprawdzane w kolejności i wybierana jest wartość, jeśli jest zgodna ze wszystkimi poprzednio używanymi wartościami. Oznacza to jedno pojedyncze przejście liniowe przez unikalne tablice zliczające, w których każdy kandydat jest porównywany z wcześniej wybranymi wartościami.

Mam kilka pomysłów, w jaki sposób heurystykę można potencjalnie poprawić. Wydawało się to jednak rozsądnym punktem wyjścia, a wyniki wyglądały całkiem dobrze.

Kod

To nie jest wysoce zoptymalizowane. W pewnym momencie miałem bardziej rozbudowaną strukturę danych, ale potrzebowałem więcej pracy, aby ją uogólnić n=8, a różnica w wydajności nie wydawała się bardzo znacząca.

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