N Nummern erzeugen, so dass die Hammingdistanz zwischen jedem von ihnen mindestens gleich ist D

Question

Gegeben N, B und D: Finde einen Satz von N Codewörtern (1 < = N < = 64), jedes der Länge B Bits (1 < = B < = 8), so dass jedes der Codewörter wenigstens Hamming-Abstand von D (1 < = D < = 7) von jedem der anderen Codewörter entfernt ist. Die Hamming-Distanz zwischen einem Paar von Codewörtern ist die Anzahl von binären Bits, die sich in ihrer binären Schreibweise unterscheiden. Betrachten Sie die zwei Codewörter 0x554 und 0x234 und deren Unterschiede (0x554 bedeutet die hexadezimale Zahl mit hexadezimalen Ziffern 5, 5 und 4):

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

Bit Unterschiede: xxx xx Seit fünf Bits verschieden waren, die Hamming-Distanz ist 5.

Beispiel

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

I alle Codeworte (Binärstring) der Länge B und versucht, jede Teilmenge der Größe N Kommissionierung und sehen, ob sie mit anderer Nummer in der Untergruppe jede Zahl in dem aufgenommenen Teilmenge erzeugen kann, ist mindestens D Schinken ming auseinander, aber das wird Zeit erfordern nCk

(2**B) C N 

die im schlimmsten Fall schrecklich sein kann. Wie kann ich die Nummern effizient generieren?

Answer 1

This ist eine ähnliche Frage und die Antworten/Kommentare erwähnen, dass eine effiziente Konstruktion ein offenes Problem ist! Hier

ist ein kompakten Ansatz Verwendung Integer Programming (die NP-hard ist), modelliert mit cvxpy in 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) 

Output:

.... (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: Ein früherer Ansatz (verschiedene Solver-p Arams) benötigt 48 Minuten, jetzt dauerte es nur ~ 8 Sekunden. Ich benutzte einen kommerziellen Löser (nicht frei für nicht-akademischen Gebrauch)!

Ich denke, ein SAT-Lösungsansatz könnte schneller sein, aber es scheint, dass dies ein sehr schweres Problem ist (wie in meinem Link oben erwähnt)!