Python 2 - 17/10 = 1.72-(3/n)
for any n
Inspired by this question, I used De Bruijn Sequence to brute force the possible matrices. And after bruteforcing for n=10n=6,7,8,9,10
, itI found a pattern that the highest solution with score 17/10is always in the shape of (n, 2n-3)
.
So I created another method to bruteforce just that shape of matrix, and use multiprocessing to speed things up, since this task is highly distributable. In 16-core ubuntu, it can find solution for n=12
in around 4 minutes:
Trying (0, 254)
Trying (254, 509)
Trying (509, 764)
Trying (764, 1018)
Trying (1018, 1273)
Trying (1273, 1528)
Trying (1528, 1782)
Trying (1782, 2037)
Trying (2037, 2292)
Trying (2292, 2546)
Trying (2546, 2801)
Trying (2801, 3056)
Trying (3056, 3310)
Trying (3820, 4075)
Trying (3565, 3820)
Trying (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)
Score: 1.7500
real 4m9.121s
user 42m47.472s
sys 0m5.780s
The bulk of computation goes to checking property X, which requires checking all subsets (there are 2^(2n-3)
subsets)
The 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()
Old answer, for reference
A solution with the shape as described by OP (n=8
):
But a better one (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)
Score: 1.6250
It also found another suboptimaloptimal solution at n=9
:
(418103, 432118)
[[0 0 1 10 1 1 1 0 10 0 0 1 1 0 0 1]
[0 1[1 10 1 1 1 0 10 0 0 1 1 0 0 1 0]
[1 1[0 1 1 1 0 10 0 0 1 1 0 0 1 0 0]1]
[1 1 1 1 0 10 0 0 1 1 10 0 1 0 1]1 0]
[1 1 1 0 10 0 0 1 1 10 0 1 0 1 0 1]
[1 1 0 10 0 0 1 1 10 0 1 0 1 0 1 1]
[1[0 0 1 0 0 1 1 10 0 1 0 1 0 1 1 1]
[0 1 0 0 1 1 10 0 1 0 1 0 1 1 1 1]0]
[1 0[0 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0]]
(9, 1415)
Score: 1.55566667
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), 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()