Найти матрицу с наивысшей оценкой без свойства X

Эта задача частично является задачей алгоритмов, частично задачей оптимизации, а частично просто самой быстрой задачей кода.

Циклическая матрица полностью определяется ее первой строкой r. Оставшиеся строки представляют собой циклические перестановки строк rсо смещением, равным индексу строки. Мы допустим циклические матрицы, которые не являются квадратными, так что они просто пропускают некоторые из своих последних строк. Однако мы всегда предполагаем, что количество строк не больше, чем количество столбцов. Например, рассмотрим следующую циклическую матрицу 3 на 5.

10111
11011
11101

Мы говорим, что матрица обладает свойством X, если она содержит два непустых набора столбцов с неидентичными индексами, которые имеют одинаковую (векторную) сумму. Векторная сумма двух столбцов - это просто поэлементное суммирование двух столбцов. То есть сумма двух столбцов, содержащих xэлементы, каждый является другим столбцом, содержащим xэлементы.

Приведенная выше матрица тривиально обладает свойством X, поскольку первый и последний столбцы совпадают. Тождественная матрица никогда не обладает свойством X.

Если мы просто удалим последний столбец матрицы выше, то получим пример, который не имеет свойства X и даст оценку 4/3.

1011
1101
1110

Задание

Задача состоит в том, чтобы написать код, чтобы найти циклическую матрицу с наивысшей оценкой, все записи которой равны 0 или 1 и которая не имеет свойства X.

Гол

Ваша оценка будет равна количеству столбцов, разделенному на количество строк в вашей наилучшей оценочной матрице.

Tie Breaker

Если два ответа имеют одинаковую оценку, победит тот, который отправил первый.

В (очень) маловероятном случае, когда кто-то найдет способ получить неограниченное количество баллов, будет принято первое действительное доказательство такого решения. В еще более маловероятном случае, когда вы сможете найти доказательство оптимальности конечной матрицы, я, конечно, также призову победу.

намек

Получить счет 12/8 не так уж сложно.

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

Вы можете использовать любой язык со свободно доступным компилятором / интерпретатором и т. Д. для Linux и любых библиотек, которые также свободно доступны для Linux.

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

• 36/19 Питер Тейлор (Ява)
• 32/17 от Suboptimus Prime (C #)
• 21/12 от justhalf (Python 2)

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

Это использует ряд идей, чтобы уменьшить пространство поиска и стоимость. Посмотрите историю изменений для более подробной информации о более ранних версиях кода.

• Понятно, что в wlog мы можем рассматривать только циркулянтные матрицы, в которых первая строка - это слово Линдона : если слово не простое, то оно должно иметь свойство X, а в противном случае мы можем вращаться, не влияя на оценку или свойство X.
• Основываясь на эвристике от наблюдаемых коротких победителей, я теперь перебираю слова Линдона, начиная с слов с плотностью 50% (то есть с тем же числом 0и 1) и заканчивая; Я использую алгоритм, описанный в коде Грея, для ожерелий с фиксированной плотностью и слов Линдона в постоянном амортизированном времени , Савада и Уильямс, Теоретическая информатика 502 (2013): 46-54.
• Эмпирическое наблюдение состоит в том, что значения встречаются парами: каждое оптимальное слово Линдона, которое я нашел, оценивается так же, как и его обращение. Таким образом, я получаю примерно двукратное ускорение, рассматривая только половину каждой такой пары.
• Мой оригинальный код работал, BigIntegerчтобы дать точный тест. Я получаю значительное улучшение скорости, рискуя получить ложные негативы, работая по модулю большого простого числа и сохраняя все в примитивах. Простое число, которое я выбрал, является самым большим, меньше чем 2 ⁵⁷ , поскольку это позволяет умножать на основание моего условного векторного представления без переполнения.
• Я украл эвристику Suboptimus Prime о том, что можно быстро получить отказ, рассматривая подмножества в порядке возрастания размера. Теперь я объединил эту идею с подходом троичного подмножества «посередине», чтобы проверить наличие сталкивающихся подмножеств. ( Благодарю KennyTM за предложение адаптировать подход к проблеме целочисленного подмножества; я думаю, что xnor и я нашли способ сделать это почти одновременно). Вместо того, чтобы искать два подмножества, которые могут включать каждый столбец 0 или 1 раз и иметь одинаковую сумму, мы ищем одно подмножество, которое может включать каждый столбец -1, 0 или 1 раз и суммировать до нуля. Это значительно снижает требования к памяти.
• Существует дополнительный фактор двухкратного сохранения требований к памяти, учитывая, что, поскольку каждый элемент {-1,0,1}^mимеет свое отрицание, также {-1,0,1}^mнеобходимо хранить только один из двух.
• Я также улучшаю требования к памяти и производительность, используя собственную реализацию hashmap. Для тестирования 36/19 требуется хранить 3 ^ 18 сумм, а 3 ^ 18 long - это почти 3 ГБ без каких-либо накладных расходов - я выделил ему 6 ГБ кучи, потому что 4 ГБ было недостаточно; чтобы пойти дальше (т. е. проверить 38/20) в пределах 8 ГБ ОЗУ, потребуется дополнительная оптимизация для хранения целых, а не длинных. С 20 битами требуется, чтобы сказать, какое подмножество производит сумму, которая оставила бы 12 битов плюс неявные биты из корзины; Я боюсь, что было бы слишком много ложных столкновений, чтобы получить какие-либо попадания.
• Поскольку вес доказательств говорит о том, что мы должны посмотреть 2n/(n+1), я ускоряю процесс, просто проверяя это.
• Есть некоторые ненужные, но обнадеживающие статистические данные.

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

Первый найденный

000001001010110001000101001111111111

и это единственный удар за 15 часов.

Меньшие победители:

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

В процессе доказательства того, что 2-(3/n)всегда существует для любогоn

Вдохновленный этим вопросом , я использовал последовательность де Брюйна для грубой силы возможных матриц. И после брутфорса n=6,7,8,9,10я обнаружил шаблон, который всегда имеет форму самого высокого решения (n, 2n-3).

Поэтому я создал еще один метод, чтобы использовать только эту форму матрицы и использовать многопроцессорную обработку, чтобы ускорить процесс, поскольку эта задача легко распространяется. В 16-ядерном Ubuntu решение может быть найдено n=12примерно за 4 минуты:

Пытается (0, 254)
Попытка (254, 509)
Попытка (509, 764)
Попытка (764, 1018)
Попытка (1018, 1273)
Попытка (1273, 1528)
Попытка (1528, 1782)
Попытка (1782, 2037)
Попытка (2037, 2292)
Попытка (2292, 2546)
Попытка (2546, 2801)
Попытка (2801, 3056)
Попытка (3056, 3310)
Попытка (3820, 4075)
Попытка (3565, 3820)
Попытка (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)
Оценка: 1.7500

настоящий 4м9.121с
пользователь 42m47.472s
sys 0m5,780s

Большая часть вычислений идет на проверку свойства X, которое требует проверки всех подмножеств (есть 2^(2n-3)подмножества)

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

Код:

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()

Старый ответ, для справки

Оптимальное решение пока ( 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)
Оценка: 1.7000

Для 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)
Оценка: 1.5714

Решение с формой, как описано 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)
Оценка: 1,5000

Но лучше ( 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)
Оценка: 1.6250

Также найдено другое оптимальное решение по адресу 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)
Оценка: 1.6667

Код выглядит следующим образом. Это просто грубая сила, но, по крайней мере, она может найти что-то лучше, чем претензия ОП =)

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: похоже, он сейчас использует лучший алгоритм), хотя я добавил некоторые из моих собственных оптимизаций:

• Я реализовал стратегию «встретиться посередине» для поиска наборов столбцов с одинаковой векторной суммой (предложено в этом комментарии KennyTM ). Эта стратегия значительно улучшила использование памяти, но она довольно медленная, поэтому я добавилHasPropertyXFast функцию, которая быстро проверяет наличие небольших наборов с равными суммами, прежде чем использовать подход «посередине».
• Выполняя итерацию по наборам столбцов в HasPropertyXFast функции, я начинаю с проверки наборов столбцов с 1 столбцом, затем с 2, 3 и так далее. Функция возвращается, как только найдено первое столкновение сумм столбцов. На практике это означает, что мне обычно приходится проверять несколько сотен или тысяч наборов столбцов, а не миллионы.
• Я использую longпеременные для хранения и сравнения целых столбцов и их векторных сумм. Этот подход по крайней мере на порядок быстрее, чем сравнение столбцов как массивов.
• Я добавил собственную реализацию hashset, оптимизированную для long типов данных и шаблонов использования.
• Я повторно использую одни и те же 3 хэш-набора для всего срока службы приложения, чтобы уменьшить количество выделенных памяти и повысить производительность.
• Поддержка многопоточности.

Выход программы:

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

Код:

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

Файл конфигурации:

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