генерируют N чисел, так что расстояние между ними должно быть не менее D

Question

Данные N, B и D: Найдите набор из N кодовых слов (1 < = N < = 64), каждый из бит бит B (1 < = B < = 8), так что каждое из кодовых слов является по меньшей мере расстоянием Хэмминга D (1 < = D < = 7) от каждого из других кодовых слов. Расстояние Хэмминга между двумя кодовыми словами - это число двоичных битов, которые различаются по их двоичной нотации. Рассмотрим два кодовых слова 0x554 и 0x234 и их различия (0x554 означает шестнадцатеричное число с шестнадцатеричных цифр 5, 5, и 4):

0x554 = 0101 0101 0100 
    0x234 = 0010 0011 0100 

Бит различия: ххх хх Так как пять битов были различны, то расстояние Хэмминга 5.

Пример

input :- N=16 B=7 D=3 
output :- 0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127 

можно генерировать все кодовые слова (двоичная строка) длины B и попытаться выбирая каждое подмножество размера N и посмотреть, если он каждое число в подобранной подмножества с другим числом в подмножестве по крайней мере D ham но это потребует времени nCk

(2**B) C N 

который может быть ужасным в наихудшем случае. Как эффективно генерировать числа?

Answer 1

This это аналогичный вопрос, и в ответах/комментариях упоминается, что эффективное строительство является открытой проблемой!

Вот компактный подход с помощью целочисленного программирования (который является NP-трудной), смоделированный с cvxpy в Python3:

import itertools 
import operator 
from cvxpy import * 

N = 16 
B = 7 
D = 3 

# Vars. 
X = Bool(N, B) 
Y = Bool(len(list(itertools.combinations(range(N), 2))), B) # ugly -> could use bin-formula 

# Objective 
objective = Minimize(1) # dummy objective -> only feasibility needed! 

# Constraints 
def xor_vectors(a, b, y): 
    """ Linearization of y-vec = xor(a-vec, b-vec) """ 
    return [y <= a + b, 
      y >= a-b, 
      y >= b-a, 
      y <= 2-a-b] 

constraints_xor = reduce(operator.add, [xor_vectors(X[pair[0], :], X[pair[1], :], Y[ind, :]) for ind, pair in 
         enumerate(itertools.combinations(range(N), 2))]) 
constraints_hamming_dist = [sum_entries(Y, axis=1) >= D] 

# Build problem 
prob = Problem(objective, constraints_xor + constraints_hamming_dist) 
# Solve 
result = prob.solve(solver=GUROBI, MIPFocus=1, verbose=True) 

print(X.value) 

Выход:

.... (verbose output) 

111 108 0.00000 18 424   - 0.00000  - 511 5s 
* 264 13    37  0.0000000 0.00000 0.00% 500 7s 

Cutting planes: 
Gomory: 2 
Zero half: 26 

Explored 270 nodes (139404 simplex iterations) in 7.74 seconds 
Thread count was 4 (of 4 available processors) 

Optimal solution found (tolerance 1.00e-04) 
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0% 
[[ 1. 1. 1. 1. 1. 1. 1.] 
[ 1. 0. 1. 0. 1. 1. 0.] 
[ 1. 1. 1. 0. 0. 0. 1.] 
[ 1. 1. 0. 0. 1. 0. 0.] 
[ 0. 1. 1. 1. 1. 0. 0.] 
[ 0. 1. 0. 0. 1. 1. 1.] 
[ 0. 1. 1. 0. 0. 1. 0.] 
[ 0. 1. 0. 1. 0. 0. 1.] 
[ 1. 1. 0. 1. 0. 1. 0.] 
[ 1. 0. 1. 1. 0. 0. 0.] 
[ 0. 0. 0. 1. 1. 1. 0.] 
[ 0. 0. 1. 1. 0. 1. 1.] 
[ 0. 0. 0. 0. 0. 0. 0.] 
[ 1. 0. 0. 0. 0. 1. 1.] 
[ 1. 0. 0. 1. 1. 0. 1.] 
[ 0. 0. 1. 0. 1. 0. 1.]] 

EDIT: Более ранний подход (другой решатель-p арам) потребовалось 48 минут, теперь потребовалось всего ~ 8 секунд. Я использовал коммерческий решатель (не бесплатно для неакадемического использования)!

Я думаю, что подход SAT-решения может быть быстрее, но кажется, что это очень тяжелая проблема (как упоминалось в моей ссылке выше)!