Trouver la matrice ayant le score le plus élevé sans propriété X

Ce défi est en partie un défi d'algorithmes, en partie un défi d'optimisation et en partie simplement un défi de code le plus rapide.

Une matrice cyclique est entièrement spécifiée par sa première ligne r. Les lignes restantes sont chacune des permutations cycliques de la ligne ravec un décalage égal à l'index de la ligne. Nous autoriserons les matrices cycliques qui ne sont pas carrées de sorte qu'il leur manque simplement certaines de leurs dernières lignes. Nous supposons cependant toujours que le nombre de lignes n'est pas supérieur au nombre de colonnes. Par exemple, considérons la matrice cyclique 3 x 5 suivante.

10111
11011
11101

Nous disons qu'une matrice a la propriété X si elle contient deux ensembles de colonnes non vides avec des indices non identiques qui ont la même somme (vectorielle). La somme vectorielle de deux colonnes est simplement une somme par élément des deux colonnes. C'est la somme de deux colonnes contenant des xéléments chacune est une autre colonne contenant des xéléments.

La matrice ci-dessus a trivialement la propriété X car les première et dernière colonnes sont les mêmes. La matrice d'identité n'a jamais la propriété X.

Si nous supprimons simplement la dernière colonne de la matrice ci-dessus, nous obtenons un exemple qui n'a pas la propriété X et donnerait un score de 4/3.

1011
1101
1110

La tâche

La tâche consiste à écrire du code pour trouver la matrice cyclique au score le plus élevé dont les entrées sont toutes 0 ou 1 et qui n'a pas la propriété X.

But

Votre score sera le nombre de colonnes divisé par le nombre de lignes de votre matrice de meilleur score.

Tie break

Si deux réponses ont le même score, celle soumise en premier l'emporte.

Dans le cas (très) peu probable où quelqu'un trouverait une méthode pour obtenir des scores illimités, la première preuve valable d'une telle solution sera acceptée. Dans le cas encore plus improbable où vous pouvez trouver une preuve d'optimalité d'une matrice finie, j'attribuerai bien sûr également la victoire.

Allusion

Obtenir un score de 12/8 n'est pas trop difficile.

Langues et bibliothèques

Vous pouvez utiliser n'importe quelle langue disposant d'un compilateur / interprète / etc disponible gratuitement. pour Linux et toutes les bibliothèques qui sont également disponibles gratuitement pour Linux.

Entrées principales

• 36/19 de Peter Taylor (Java)
• 32/17 par Suboptimus Prime (C #)
• 21/12 par moitié (Python 2)

16/9 20/11 22/12 28/15 30/16 32/17 34/18 36/19 (Java)

Cela utilise un certain nombre d'idées pour réduire l'espace de recherche et les coûts. Consultez l'historique des révisions pour plus de détails sur les versions antérieures du code.

• Il est clair que wlog nous ne pouvons considérer que les matrices circulantes dans lesquelles la première ligne est un mot de Lyndon : si le mot n'est pas premier alors il doit avoir la propriété X, sinon nous pouvons tourner sans affecter le score ou la propriété X.
• Basé sur l'heuristique des gagnants courts observés, j'itère maintenant à travers les mots de Lyndon en commençant par ceux avec une densité de 50% (c'est-à-dire le même nombre de 0et 1) et en travaillant; J'utilise l'algorithme décrit dans Un code gris pour les colliers à densité fixe et les mots Lyndon à temps amorti constant , Sawada et Williams, Theoretical Computer Science 502 (2013): 46-54.
• Une observation empirique est que les valeurs se produisent par paires: chaque mot Lyndon optimal que j'ai trouvé a le même score que son inversion. J'obtiens donc environ un facteur de deux en ne considérant que la moitié de chacune de ces paires.
• Mon code d'origine a fonctionné BigIntegerpour donner un test exact. J'obtiens une amélioration significative de la vitesse, au risque de faux négatifs, en faisant fonctionner modulo un grand prime et en gardant le tout dans les primitives. Le nombre premier que j'ai choisi est le plus grand, inférieur à 2 ⁵⁷ , car cela permet de multiplier par la base de ma représentation vectorielle théorique sans déborder.
• J'ai volé l' heuristique de Suboptimus Prime selon laquelle il est possible d'obtenir des rejets rapides en considérant les sous-ensembles dans un ordre croissant de taille. J'ai maintenant fusionné cette idée avec l'approche de rencontre ternaire de sous-ensemble pour tester les sous-ensembles en collision. ( Nous remercions KennyTM d' avoir suggéré d'essayer d'adapter l'approche à partir du problème des sous-ensembles entiers; je pense que xnor et moi avons vu le moyen de le faire à peu près simultanément). Plutôt que de rechercher deux sous-ensembles pouvant inclure chaque colonne 0 ou 1 fois et ayant la même somme, nous recherchons un sous-ensemble pouvant inclure chaque colonne -1, 0 ou 1 fois et additionner à zéro. Cela réduit considérablement les besoins en mémoire.
• Il y a un facteur supplémentaire de deux économies de mémoire en observant que, puisque chaque élément dans {-1,0,1}^ma également sa négation, {-1,0,1}^mil est seulement nécessaire de stocker l'un des deux.
• J'améliore également les besoins en mémoire et les performances en utilisant une implémentation de hashmap personnalisée. Pour tester 36/19, il faut stocker 3 ^ 18 sommes, et 3 ^ 18 longs est presque 3 Go sans frais généraux - je lui ai donné 6 Go de tas car 4 Go ne suffisaient pas; pour aller plus loin (c.-à-d. test 38/20) à moins de 8 Go de RAM, il faudrait une optimisation supplémentaire pour stocker les pouces plutôt que les longs. Avec 20 bits requis pour dire quel sous-ensemble produit la somme qui laisserait 12 bits plus les bits implicites du compartiment; Je crains qu'il y ait trop de fausses collisions pour obtenir des coups.
• Étant donné que le poids des preuves suggère que nous devrions examiner 2n/(n+1), j'accélère les choses en testant simplement cela.
• Il y a des résultats statistiques inutiles mais rassurants.

import java.util.*;

// Aiming to find a solution for (2n, n+1).
public class PPCG41021_QRTernary_FixedDensity {
    private static final int N = 36;
    private static int density;
    private static long start;
    private static long nextProgressReport;

    public static void main(String[] args) {
        start = System.nanoTime();
        nextProgressReport = start + 5 * 60 * 1000000000L;

        // 0, -1, 1, -2, 2, ...
        for (int i = 0; i < N - 1; i++) {
            int off = i >> 1;
            if ((i & 1) == 1) off = ~off;
            density = (N >> 1) + off;

            // Iterate over Lyndon words of length N and given density.
            for (int j = 0; j < N; j++) a[j] = j < N - density ? '0' : '1';
            c = 1;
            Bs[1] = N - density;
            Bt[1] = density;
            gen(N - density, density, 1);
            System.out.println("----");
        }

        System.out.println("Finished in " + (System.nanoTime() - start)/1000000 + " ms");
    }

    private static int c;
    private static int[] Bs = new int[N + 1], Bt = new int[N + 1];
    private static char[] a = new char[N];
    private static void gen(int s, int t, int r) {
        if (s > 0 && t > 0) {
            int j = oracle(s, t, r);
            for (int i = t - 1; i >= j; i--) {
                updateBlock(s, t, i);
                char tmp = a[s - 1]; a[s - 1] = a[s+t-i - 1]; a[s+t-i - 1] = tmp;
                gen(s-1, t-i, testSuffix(r) ? c-1 : r);
                tmp = a[s - 1]; a[s - 1] = a[s+t-i - 1]; a[s+t-i - 1] = tmp;
                restoreBlock(s, t, i);
            }
        }
        visit();
    }

    private static int oracle(int s, int t, int r) {
        int j = pseudoOracle(s, t, r);
        updateBlock(s, t, j);
        int p = testNecklace(testSuffix(r) ? c - 1 : r);
        restoreBlock(s, t, j);
        return p == N ? j : j + 1;
    }

    private static int pseudoOracle(int s, int t, int r) {
        if (s == 1) return t;
        if (c == 1) return s == 2 ? N / 2 : 1;
        if (s - 1 > Bs[r] + 1) return 0;
        if (s - 1 == Bs[r] + 1) return cmpPair(s-1, t, Bs[c-1]+1, Bt[c-1]) <= 0 ? 0 : 1;
        if (s - 1 == Bs[r]) {
            if (s == 2) return Math.max(t - Bt[r], (t+1) >> 1);
            return Math.max(t - Bt[r], (cmpPair(s-1, t, Bs[c-1] + 1, Bt[c-1]) <= 0) ? 0 : 1); 
        }
        if (s == Bs[r]) return t;
        throw new UnsupportedOperationException("Hit the case not covered by the paper or its accompanying code");
    }

    private static int testNecklace(int r) {
        if (density == 0 || density == N) return 1;
        int p = 0;
        for (int i = 0; i < c; i++) {
            if (r - i <= 0) r += c;
            if (cmpBlocks(c-i, r-i) < 0) return 0;
            if (cmpBlocks(c-i, r-1) > 0) return N;
            if (r < c) p += Bs[r-i] + Bt[r-i];
        }
        return p;
    }

    private static int cmpPair(int a1, int a2, int b1, int b2) {
        if (a1 < b1) return -1;
        if (a1 > b1) return 1;
        if (a2 < b2) return -1;
        if (a2 > b2) return 1;
        return 0;
    }

    private static int cmpBlocks(int i, int j) {
        return cmpPair(Bs[i], Bt[i], Bs[j], Bt[j]);
    }

    private static boolean testSuffix(int r) {
        for (int i = 0; i < r; i++) {
            if (c - 1 - i == r) return true;
            if (cmpBlocks(c-1-i, r-i) < 0) return false;
            if (cmpBlocks(c-1-i, r-1) > 0) return true;
        }
        return false;
    }

    private static void updateBlock(int s, int t, int i) {
        if (i == 0 && c > 1) {
            Bs[c-1]++;
            Bs[c] = s - 1;
        }
        else {
            Bs[c] = 1;
            Bt[c] = i;
            Bs[c+1] = s-1;
            Bt[c+1] = t-i;
            c++;
        }
    }

    private static void restoreBlock(int s, int t, int i) {
        if (i == 0 && (c > 0 || (Bs[1] != 1 || Bt[1] != 0))) {
            Bs[c-1]--;
            Bs[c] = s;
        }
        else {
            Bs[c-1] = s;
            Bt[c-1] = t;
            c--;
        }
    }

    private static long[] stats = new long[N/2+1];
    private static long visited = 0;
    private static void visit() {
        String word = new String(a);

        visited++;
        if (precedesReversal(word) && testTernary(word)) System.out.println(word + " after " + (System.nanoTime() - start)/1000000 + " ms");
        if (System.nanoTime() > nextProgressReport) {
            System.out.println("Progress: visited " + visited + "; stats " + Arrays.toString(stats) + " after " + (System.nanoTime() - start)/1000000 + " ms");
             nextProgressReport += 5 * 60 * 1000000000L;
        }
    }

    private static boolean precedesReversal(String w) {
        int n = w.length();
        StringBuilder rev = new StringBuilder(w);
        rev.reverse();
        rev.append(rev, 0, n);
        for (int i = 0; i < n; i++) {
            if (rev.substring(i, i + n).compareTo(w) < 0) return false;
        }
        return true;
    }

    private static boolean testTernary(String word) {
        int n = word.length();
        String rep = word + word;

        int base = 1;
        for (char ch : word.toCharArray()) base += ch & 1;

        // Operating base b for b up to 32 implies that we can multiply by b modulo p<2^57 without overflowing a long.
        // We're storing 3^(n/2) ~= 2^(0.8*n) sums, so while n < 35.6 we don't get *too* bad a probability of false reject.
        // (In fact the birthday paradox assumes independence, and our values aren't independent, so we're better off than that).
        long p = (1L << 57) - 13;
        long[] basis = new long[n];
        basis[0] = 1;
        for (int i = 1; i < basis.length; i++) basis[i] = (basis[i-1] * base) % p;

        int rows = n / 2 + 1;
        long[] colVals = new long[n];
        for (int col = 0; col < n; col++) {
            for (int row = 0; row < rows; row++) {
                colVals[col] = (colVals[col] + basis[row] * (rep.charAt(row + col) & 1)) % p;
            }
        }

        MapInt57Int27 map = new MapInt57Int27();
        // Special-case the initial insertion.
        int[] oldLens = new int[map.entries.length];
        int[] oldSupercounts = new int[1 << 10];
        {
            // count = 1
            for (int k = 0; k < n/2; k++) {
                int val = 1 << (25 - k);
                if (!map.put(colVals[k], val)) { stats[1]++; return false; }
                if (!map.put(colVals[k + n/2], val + (1 << 26))) { stats[1]++; return false; }
            }
        }
        final long keyMask = (1L << 37) - 1;
        for (int count = 2; count <= n/2; count++) {
            int[] lens = map.counts.clone();
            int[] supercounts = map.supercounts.clone();
            for (int sup = 0; sup < 1 << 10; sup++) {
                int unaccountedFor = supercounts[sup] - oldSupercounts[sup];
                for (int supi = 0; supi < 1 << 10 && unaccountedFor > 0; supi++) {
                    int i = (sup << 10) + supi;
                    int stop = lens[i];
                    unaccountedFor -= stop - oldLens[i];
                    for (int j = oldLens[i]; j < stop; j++) {
                        long existingKV = map.entries[i][j];
                        long existingKey = ((existingKV & keyMask) << 20) + i;
                        int existingVal = (int)(existingKV >>> 37);

                        // For each possible prepend...
                        int half = (existingVal >> 26) * n/2;
                        // We have 27 bits of key, of which the top marks the half, so 26 bits. That means there are 6 bits at the top which we need to not count.
                        int k = Integer.numberOfLeadingZeros(existingVal << 6) - 1;
                        while (k >= 0) {
                            int newVal = existingVal | (1 << (25 - k));
                            long pos = (existingKey + colVals[k + half]) % p;
                            if (pos << 1 > p) pos = p - pos;
                            if (pos == 0 || !map.put(pos, newVal)) { stats[count]++; return false; }
                            long neg = (p - existingKey + colVals[k + half]) % p;
                            if (neg << 1 > p) neg = p - neg;
                            if (neg == 0 || !map.put(neg, newVal)) { stats[count]++; return false; }
                            k--;
                        }
                    }
                }
            }
            oldLens = lens;
            oldSupercounts = supercounts;
        }

        stats[n/2]++;
        return true;
    }

    static class MapInt57Int27 {
        private long[][] entries;
        private int[] counts;
        private int[] supercounts;

        public MapInt57Int27() {
            entries = new long[1 << 20][];
            counts = new int[1 << 20];
            supercounts = new int[1 << 10];
        }

        public boolean put(long key, int val) {
            int bucket = (int)(key & (entries.length - 1));
            long insert = (key >>> 20) | (((long)val) << 37);
            final long mask = (1L << 37) - 1;

            long[] chain = entries[bucket];
            if (chain == null) {
                chain = new long[16];
                entries[bucket] = chain;
                chain[0] = insert;
                counts[bucket]++;
                supercounts[bucket >> 10]++;
                return true;
            }

            int stop = counts[bucket];
            for (int i = 0; i < stop; i++) {
                if ((chain[i] & mask) == (insert & mask)) {
                    return false;
                }
            }

            if (stop == chain.length) {
                long[] newChain = new long[chain.length < 512 ? chain.length << 1 : chain.length + 512];
                System.arraycopy(chain, 0, newChain, 0, chain.length);
                entries[bucket] = newChain;
                chain = newChain;
            }
            chain[stop] = insert;
            counts[bucket]++;
            supercounts[bucket >> 10]++;
            return true;
        }
    }
}

Le premier trouvé est

000001001010110001000101001111111111

et c'est le seul succès en 15 heures.

Petits gagnants:

4/3:    0111                       (plus 8 different 8/6)
9/6:    001001011                  (and 5 others)
11/7:   00010100111                (and 3 others)
13/8:   0001001101011              (and 5 others)
15/9:   000010110110111            (and 21 others)
16/9:   0000101110111011           (and 1 other)
20/11:  00000101111011110111       (and others)
22/12:  0000001100110011101011     (and others)
24/13:  000000101011101011101011   (and others)
26/14:  00000001101110010011010111 (and others)
28/15:  0000000010000111100111010111 (and others)
30/16:  000000001011001110011010101111 (and probably others)
32/17:  00001100010010100100101011111111 (and others)
34/18:  0000101000100101000110010111111111 (and others)

Python 2 - 21/12

En train de prouver qu’il 2-(3/n)existe toujours unn

Inspiré par cette question , j'ai utilisé la séquence De Bruijn pour forcer brutalement les matrices possibles. Et après le bruteforcing pour n=6,7,8,9,10, j'ai trouvé un modèle dont la solution la plus élevée est toujours sous la forme (n, 2n-3).

J'ai donc créé une autre méthode pour renforcer brutalement cette forme de matrice et utiliser le multitraitement pour accélérer les choses, car cette tâche est hautement distribuable. Dans Ubuntu 16 cœurs, il peut trouver une solution n=12en environ 4 minutes:

Essayer (0, 254)
Essayer (254, 509)
Essayer (509, 764)
Essayer (764, 1018)
Essayer (1018, 1273)
Essayer (1273, 1528)
Essayer (1528, 1782)
Essayer (1782, 2037)
Essayer (2037, 2292)
Essayer (2292, 2546)
Essayer (2546, 2801)
Essayer (2801, 3056)
Essayer (3056, 3310)
Essayer (3820, 4075)
Essayer (3565, 3820)
Essayer (3310, 3565)
(1625, 1646)
[[0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0]
 [0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0]
 [0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0]
 [1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0]
 [0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1]
 [0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0]
 [1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0]
 [0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1]
 [1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0]
 [1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1]
 [1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1]
 [1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1]]
(12, 21)
Résultat: 1,7500

réel 4m9.121s
utilisateur 42m47.472s
sys 0m5.780s

La majeure partie du calcul va à la vérification de la propriété X, qui nécessite de vérifier tous les sous-ensembles (il existe des 2^(2n-3)sous - ensembles)

Notez que je tourne la première ligne vers la gauche, pas vers la droite comme dans la question. Mais ceux-ci sont équivalents car vous pouvez simplement inverser la matrice entière. =)

Le code:

import math
import numpy as np
from itertools import combinations
from multiprocessing import Process, Queue, cpu_count

def de_bruijn(k, n):
    """
    De Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    alphabet = list(range(k))
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

def generate_cyclic_matrix(seq, n):
    result = []
    for i in range(n):
        result.append(seq[i:]+seq[:i])
    return np.array(result)

def generate_cyclic_matrix_without_property_x(n=3, n_jobs=-1):
    seq = de_bruijn(2,n)
    seq = seq + seq[:n/2]
    max_idx = len(seq)
    max_score = 1
    max_matrix = np.array([[]])
    max_ij = (0,0)
    workers = []
    queue = Queue()
    if n_jobs < 0:
        n_jobs += cpu_count()+1
    for i in range(n_jobs):
        worker = Process(target=worker_function, args=(seq,i*(2**n-2*n+3)/n_jobs, (i+1)*(2**n-2*n+3)/n_jobs, n, queue))
        workers.append(worker)
        worker.start()
    (result, max_ij) = queue.get()
    for worker in workers:
        worker.terminate()
    return (result, max_ij)

def worker_function(seq,min_idx,max_idx,n,queue):
    print 'Trying (%d, %d)' % (min_idx, max_idx)
    for i in range(min_idx, max_idx):
        j = i+2*n-3
        result = generate_cyclic_matrix(seq[i:j], n)
        if has_property_x(result):
            continue
        else:
            queue.put( (result, (i,j)) )
            return

def has_property_x(mat):
    vecs = zip(*mat)
    vector_sums = set()
    for i in range(1, len(vecs)+1):
        for combination in combinations(vecs, i):
            vector_sum = tuple(sum(combination, np.array([0]*len(mat))))
            if vector_sum in vector_sums:
                return True
            else:
                vector_sums.add(vector_sum)
    return False

def main():
    import sys
    n = int(sys.argv[1])
    if len(sys.argv) > 2:
        n_jobs = int(sys.argv[2])
    else:
        n_jobs = -1
    (matrix, ij) = generate_cyclic_matrix_without_property_x(n, n_jobs)
    print ij
    print matrix
    print matrix.shape
    print 'Score: %.4f' % (float(matrix.shape[1])/matrix.shape[0])

if __name__ == '__main__':
    main()

Ancienne réponse, pour référence

Jusqu'à présent, la solution optimale ( n=10):

(855, 872)
[[1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0]
 [1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1]
 [0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1]
 [1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0]
 [0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1]
 [1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0]
 [0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1]
 [0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0]
 [1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0]
 [1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1]]
(10, 17)
Résultat: 1.7000

Pour n=7:

(86, 97)
[[0 1 1 1 0 1 0 0 1 1 1]
 [1 1 1 0 1 0 0 1 1 1 0]
 [1 1 0 1 0 0 1 1 1 0 1]
 [1 0 1 0 0 1 1 1 0 1 1]
 [0 1 0 0 1 1 1 0 1 1 1]
 [1 0 0 1 1 1 0 1 1 1 0]
 [0 0 1 1 1 0 1 1 1 0 1]]
(7, 11)
Résultat: 1,5714

Une solution avec la forme décrite par OP ( n=8):

(227, 239)
[[0 1 0 1 1 1 1 1 0 1 1 0]
 [1 0 1 1 1 1 1 0 1 1 0 0]
 [0 1 1 1 1 1 0 1 1 0 0 1]
 [1 1 1 1 1 0 1 1 0 0 1 0]
 [1 1 1 1 0 1 1 0 0 1 0 1]
 [1 1 1 0 1 1 0 0 1 0 1 1]
 [1 1 0 1 1 0 0 1 0 1 1 1]
 [1 0 1 1 0 0 1 0 1 1 1 1]]
(8, 12)
Résultat: 1.5000

Mais un meilleur ( n=8):

(95, 108)
[[0 1 1 0 0 1 0 0 0 1 1 0 1]
 [1 1 0 0 1 0 0 0 1 1 0 1 0]
 [1 0 0 1 0 0 0 1 1 0 1 0 1]
 [0 0 1 0 0 0 1 1 0 1 0 1 1]
 [0 1 0 0 0 1 1 0 1 0 1 1 0]
 [1 0 0 0 1 1 0 1 0 1 1 0 0]
 [0 0 0 1 1 0 1 0 1 1 0 0 1]
 [0 0 1 1 0 1 0 1 1 0 0 1 0]]
(8, 13)
Résultat: 1,6250

Il a également trouvé une autre solution optimale à n=9:

(103, 118)
[[0 1 0 1 1 1 0 0 0 0 1 1 0 0 1]
 [1 0 1 1 1 0 0 0 0 1 1 0 0 1 0]
 [0 1 1 1 0 0 0 0 1 1 0 0 1 0 1]
 [1 1 1 0 0 0 0 1 1 0 0 1 0 1 0]
 [1 1 0 0 0 0 1 1 0 0 1 0 1 0 1]
 [1 0 0 0 0 1 1 0 0 1 0 1 0 1 1]
 [0 0 0 0 1 1 0 0 1 0 1 0 1 1 1]
 [0 0 0 1 1 0 0 1 0 1 0 1 1 1 0]
 [0 0 1 1 0 0 1 0 1 0 1 1 1 0 0]]
(9, 15)
Résultat: 1,6667

Le code est comme suit. C'est juste de la force brute, mais au moins, il peut trouver quelque chose de mieux que la revendication d'OP =)

import numpy as np
from itertools import combinations

def de_bruijn(k, n):
    """
    De Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    alphabet = list(range(k))
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

def generate_cyclic_matrix(seq, n):
    result = []
    for i in range(n):
        result.append(seq[i:]+seq[:i])
    return np.array(result)

def generate_cyclic_matrix_without_property_x(n=3):
    seq = de_bruijn(2,n)
    max_score = 0
    max_matrix = []
    max_ij = (0,0)
    for i in range(2**n+1):
        for j in range(i+n, 2**n+1):
            score = float(j-i)/n
            if score <= max_score:
                continue
            result = generate_cyclic_matrix(seq[i:j], n)
            if has_property_x(result):
                continue
            else:
                if score > max_score:
                    max_score = score
                    max_matrix = result
                    max_ij = (i,j)
    return (max_matrix, max_ij)

def has_property_x(mat):
    vecs = zip(*mat)
    vector_sums = set()
    for i in range(1, len(vecs)):
        for combination in combinations(vecs, i):
            vector_sum = tuple(sum(combination, np.array([0]*len(mat))))
            if vector_sum in vector_sums:
                return True
            else:
                vector_sums.add(vector_sum)
    return False

def main():
    import sys
    n = int(sys.argv[1])
    (matrix, ij) = generate_cyclic_matrix_without_property_x(n)
    print ij
    print matrix
    print matrix.shape
    print 'Score: %.4f' % (float(matrix.shape[1])/matrix.shape[0])

if __name__ == '__main__':
    main()

24/13 26/14 28/15 30/16 32/17 (C #)

Edit: Supprimé les informations obsolètes de ma réponse. J'utilise principalement le même algorithme que Peter Taylor ( Edit: il semble qu'il utilise un meilleur algorithme maintenant), bien que j'aie ajouté certaines de mes propres optimisations:

• J'ai mis en place une stratégie de «rencontre au milieu» pour rechercher des ensembles de colonnes avec la même somme vectorielle (suggéré par le commentaire de KennyTM ). Cette stratégie a beaucoup amélioré l'utilisation de la mémoire, mais elle est plutôt lente, j'ai donc ajouté la HasPropertyXFastfonction, qui vérifie rapidement s'il y a de petits ensembles avec des sommes égales avant d'utiliser l'approche "rencontrer au milieu".
• En parcourant les jeux de colonnes dans la HasPropertyXFast fonction, je commence par vérifier les jeux de colonnes avec 1 colonne, puis avec 2, 3 et ainsi de suite. La fonction revient dès que la première collision de sommes de colonne est trouvée. En pratique, cela signifie que je dois généralement vérifier quelques centaines ou milliers de jeux de colonnes plutôt que des millions.
• j'utilise long variables pour stocker et comparer des colonnes entières et leurs sommes vectorielles. Cette approche est au moins un ordre de grandeur plus rapide que la comparaison de colonnes en tant que tableaux.
• J'ai ajouté ma propre implémentation de hashset, optimisée pour long le type de données et pour mes modèles d'utilisation.
• Je réutilise les mêmes 3 hashsets pendant toute la durée de vie de l'application pour réduire le nombre d'allocations de mémoire et améliorer les performances.
• Prise en charge du multithreading.

Sortie du programme:

00000000000111011101010010011111
10000000000011101110101001001111
11000000000001110111010100100111
11100000000000111011101010010011
11110000000000011101110101001001
11111000000000001110111010100100
01111100000000000111011101010010
00111110000000000011101110101001
10011111000000000001110111010100
01001111100000000000111011101010
00100111110000000000011101110101
10010011111000000000001110111010
01001001111100000000000111011101
10100100111110000000000011101110
01010010011111000000000001110111
10101001001111100000000000111011
11010100100111110000000000011101
Score: 32/17 = 1,88235294117647
Time elapsed: 02:11:05.9791250

Code:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    const int MaxWidth = 32;
    const int MaxHeight = 17;

    static object _lyndonWordLock = new object();

    static void Main(string[] args)
    {
        Stopwatch sw = Stopwatch.StartNew();
        double maxScore = 0;
        const int minHeight = 17; // 1
        for (int height = minHeight; height <= MaxHeight; height++)
        {
            Console.WriteLine("Row count = " + height);
            Console.WriteLine("Time elapsed: " + sw.Elapsed + "\r\n");

            int minWidth = Math.Max(height, (int)(height * maxScore) + 1);
            for (int width = minWidth; width <= MaxWidth; width++)
            {
#if MULTITHREADING
                int[,] matrix = FindMatrixParallel(width, height);
#else
                int[,] matrix = FindMatrix(width, height);
#endif
                if (matrix != null)
                {
                    PrintMatrix(matrix);
                    Console.WriteLine("Time elapsed: " + sw.Elapsed + "\r\n");
                    maxScore = (double)width / height;
                }
                else
                    break;
            }
        }
    }

#if MULTITHREADING
    static int[,] FindMatrixParallel(int width, int height)
    {
        _lyndonWord = 0;
        _stopSearch = false;

        int threadCount = Environment.ProcessorCount;
        Task<int[,]>[] tasks = new Task<int[,]>[threadCount];
        for (int i = 0; i < threadCount; i++)
            tasks[i] = Task<int[,]>.Run(() => FindMatrix(width, height));

        int index = Task.WaitAny(tasks);
        if (tasks[index].Result != null)
            _stopSearch = true;

        Task.WaitAll(tasks);
        foreach (Task<int[,]> task in tasks)
            if (task.Result != null)
                return task.Result;

        return null;
    }

    static volatile bool _stopSearch;
#endif

    static int[,] FindMatrix(int width, int height)
    {
#if MULTITHREADING
        _columnSums = new LongSet();
        _left = new LongSet();
        _right = new LongSet();
#endif

        foreach (long rowTemplate in GetLyndonWords(width))
        {
            int[,] matrix = new int[width, height];
            for (int x = 0; x < width; x++)
            {
                int cellValue = (int)(rowTemplate >> (width - 1 - x)) % 2;
                for (int y = 0; y < height; y++)
                    matrix[(x + y) % width, y] = cellValue;
            }

            if (!HasPropertyX(matrix))
                return matrix;

#if MULTITHREADING
            if (_stopSearch)
                return null;
#endif
        }

        return null;
    }

#if MULTITHREADING
    static long _lyndonWord;
#endif

    static IEnumerable<long> GetLyndonWords(int length)
    {
        long lyndonWord = 0;
        long max = (1L << (length - 1)) - 1;
        while (lyndonWord <= max)
        {
            if ((lyndonWord % 2 != 0) && PrecedesReversal(lyndonWord, length))
                yield return lyndonWord;

#if MULTITHREADING
            lock (_lyndonWordLock)
            {
                if (_lyndonWord <= max)
                    _lyndonWord = NextLyndonWord(_lyndonWord, length);
                else
                    yield break;

                lyndonWord = _lyndonWord;
            }
#else
            lyndonWord = NextLyndonWord(lyndonWord, length);
#endif
        }
    }

    static readonly int[] _lookup =
    {
        32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17,
        0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18
    };

    static int NumberOfTrailingZeros(uint i)
    {
        return _lookup[(i & -i) % 37];
    }

    static long NextLyndonWord(long w, int length)
    {
        if (w == 0)
            return 1;

        int currentLength = length - NumberOfTrailingZeros((uint)w);
        while (currentLength < length)
        {
            w += w >> currentLength;
            currentLength *= 2;
        }

        w++;

        return w;
    }

    private static bool PrecedesReversal(long lyndonWord, int length)
    {
        int shift = length - 1;

        long reverse = 0;
        for (int i = 0; i < length; i++)
        {
            long bit = (lyndonWord >> i) % 2;
            reverse |= bit << (shift - i);
        }

        for (int i = 0; i < length; i++)
        {
            if (reverse < lyndonWord)
                return false;

            long bit = reverse % 2;
            reverse /= 2;
            reverse += bit << shift;
        }

        return true;
    }

#if MULTITHREADING
    [ThreadStatic]
#endif
    static LongSet _left = new LongSet();
#if MULTITHREADING
    [ThreadStatic]
#endif
    static LongSet _right = new LongSet();

    static bool HasPropertyX(int[,] matrix)
    {
        long[] matrixColumns = GetMatrixColumns(matrix);
        if (matrixColumns.Length == 1)
            return false;

        return HasPropertyXFast(matrixColumns) || MeetInTheMiddle(matrixColumns);
    }

    static bool MeetInTheMiddle(long[] matrixColumns)
    {
        long[] leftColumns = matrixColumns.Take(matrixColumns.Length / 2).ToArray();
        long[] rightColumns = matrixColumns.Skip(matrixColumns.Length / 2).ToArray();

        if (PrepareHashSet(leftColumns, _left) || PrepareHashSet(rightColumns, _right))
            return true;

        foreach (long columnSum in _left.GetValues())
            if (_right.Contains(columnSum))
                return true;

        return false;
    }

    static bool PrepareHashSet(long[] columns, LongSet sums)
    {
        int setSize = (int)System.Numerics.BigInteger.Pow(3, columns.Length);
        sums.Reset(setSize, setSize);
        foreach (long column in columns)
        {
            foreach (long sum in sums.GetValues())
                if (!sums.Add(sum + column) || !sums.Add(sum - column))
                    return true;

            if (!sums.Add(column) || !sums.Add(-column))
                return true;
        }

        return false;
    }

#if MULTITHREADING
    [ThreadStatic]
#endif
    static LongSet _columnSums = new LongSet();

    static bool HasPropertyXFast(long[] matrixColumns)
    {
        int width = matrixColumns.Length;

        int maxColumnCount = width / 3;
        _columnSums.Reset(width, SumOfBinomialCoefficients(width, maxColumnCount));

        int resetBit, setBit;
        for (int k = 1; k <= maxColumnCount; k++)
        {
            uint columnMask = (1u << k) - 1;
            long sum = 0;
            for (int i = 0; i < k; i++)
                sum += matrixColumns[i];

            while (true)
            {
                if (!_columnSums.Add(sum))
                    return true;
                if (!NextColumnMask(columnMask, k, width, out resetBit, out setBit))
                    break;
                columnMask ^= (1u << resetBit) ^ (1u << setBit);
                sum = sum - matrixColumns[resetBit] + matrixColumns[setBit];
            }
        }

        return false;
    }

    // stolen from Peter Taylor
    static bool NextColumnMask(uint mask, int k, int n, out int resetBit, out int setBit)
    {
        int gap = NumberOfTrailingZeros(~mask);
        int next = 1 + NumberOfTrailingZeros(mask & (mask + 1));

        if (((k - gap) & 1) == 0)
        {
            if (gap == 0)
            {
                resetBit = next - 1;
                setBit = next - 2;
            }
            else if (gap == 1)
            {
                resetBit = 0;
                setBit = 1;
            }
            else
            {
                resetBit = gap - 2;
                setBit = gap;
            }
        }
        else
        {
            if (next == n)
            {
                resetBit = 0;
                setBit = 0;
                return false;
            }

            if ((mask & (1 << next)) == 0)
            {
                if (gap == 0)
                {
                    resetBit = next - 1;
                    setBit = next;
                }
                else
                {
                    resetBit = gap - 1;
                    setBit = next;
                }
            }
            else
            {
                resetBit = next;
                setBit = gap;
            }
        }

        return true;
    }

    static long[] GetMatrixColumns(int[,] matrix)
    {
        int width = matrix.GetLength(0);
        int height = matrix.GetLength(1);

        long[] result = new long[width];
        for (int x = 0; x < width; x++)
        {
            long column = 0;
            for (int y = 0; y < height; y++)
            {
                column *= 13;
                if (matrix[x, y] == 1)
                    column++;
            }

            result[x] = column;
        }

        return result;
    }

    static int SumOfBinomialCoefficients(int n, int k)
    {
        int result = 0;
        for (int i = 0; i <= k; i++)
            result += BinomialCoefficient(n, i);
        return result;
    }

    static int BinomialCoefficient(int n, int k)
    {
        long result = 1;
        for (int i = n - k + 1; i <= n; i++)
            result *= i;
        for (int i = 2; i <= k; i++)
            result /= i;
        return (int)result;
    }

    static void PrintMatrix(int[,] matrix)
    {
        int width = matrix.GetLength(0);
        int height = matrix.GetLength(1);

        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
                Console.Write(matrix[x, y]);
            Console.WriteLine();
        }

        Console.WriteLine("Score: {0}/{1} = {2}", width, height, (double)width / height);
    }
}


class LongSet
{
    private static readonly int[] primes =
    {
        17, 37, 67, 89, 113, 149, 191, 239, 307, 389, 487, 613, 769, 967, 1213, 1523, 1907,
        2389, 2999, 3761, 4703, 5879, 7349, 9187, 11489, 14369, 17971, 22469, 28087, 35111,
        43889, 54869, 68597, 85751, 107197, 133999, 167521, 209431, 261791, 327247, 409063,
        511333, 639167, 798961, 998717, 1248407, 1560511, 1950643, 2438309, 3047909,
        809891, 4762367, 5952959, 7441219, 9301529, 11626913, 14533661, 18167089, 22708867,
        28386089, 35482627, 44353297, 55441637, 69302071, 86627603, 108284507, 135355669,
        169194593, 211493263, 264366593, 330458263, 413072843, 516341057, 645426329,
        806782913, 1008478649, 1260598321
    };

    private int[] _buckets;
    private int[] _nextItemIndexes;
    private long[] _items;
    private int _count;
    private int _minCapacity;
    private int _maxCapacity;
    private int _currentCapacity;

    public LongSet()
    {
        Initialize(0, 0);
    }

    private int GetPrime(int capacity)
    {
        foreach (int prime in primes)
            if (prime >= capacity)
                return prime;

        return int.MaxValue;
    }

    public void Reset(int minCapacity, int maxCapacity)
    {
        if (maxCapacity > _maxCapacity)
            Initialize(minCapacity, maxCapacity);
        else
            ClearBuckets();
    }

    private void Initialize(int minCapacity, int maxCapacity)
    {
        _minCapacity = GetPrime(minCapacity);
        _maxCapacity = GetPrime(maxCapacity);
        _currentCapacity = _minCapacity;

        _buckets = new int[_maxCapacity];
        _nextItemIndexes = new int[_maxCapacity];
        _items = new long[_maxCapacity];
        _count = 0;
    }

    private void ClearBuckets()
    {
        Array.Clear(_buckets, 0, _currentCapacity);
        _count = 0;
        _currentCapacity = _minCapacity;
    }

    public bool Add(long value)
    {
        int bucket = (int)((ulong)value % (ulong)_currentCapacity);
        for (int i = _buckets[bucket] - 1; i >= 0; i = _nextItemIndexes[i])
            if (_items[i] == value)
                return false;

        if (_count == _currentCapacity)
        {
            Grow();
            bucket = (int)((ulong)value % (ulong)_currentCapacity);
        }

        int index = _count;
        _items[index] = value;
        _nextItemIndexes[index] = _buckets[bucket] - 1;
        _buckets[bucket] = index + 1;
        _count++;

        return true;
    }

    private void Grow()
    {
        Array.Clear(_buckets, 0, _currentCapacity);

        const int growthFactor = 8;
        int newCapacity = GetPrime(_currentCapacity * growthFactor);
        if (newCapacity > _maxCapacity)
            newCapacity = _maxCapacity;
        _currentCapacity = newCapacity;

        for (int i = 0; i < _count; i++)
        {
            int bucket = (int)((ulong)_items[i] % (ulong)newCapacity);
            _nextItemIndexes[i] = _buckets[bucket] - 1;
            _buckets[bucket] = i + 1;
        }
    }

    public bool Contains(long value)
    {
        int bucket = (int)((ulong)value % (ulong)_buckets.Length);
        for (int i = _buckets[bucket] - 1; i >= 0; i = _nextItemIndexes[i])
            if (_items[i] == value)
                return true;

        return false;
    }

    public IReadOnlyList<long> GetValues()
    {
        return new ArraySegment<long>(_items, 0, _count);
    }
}

Fichier de configuration:

<?xml version="1.0" encoding="utf-8" ?>
<configuration>
  <runtime>
    <gcAllowVeryLargeObjects enabled="true" />
  </runtime>
</configuration>