は、それらの間のハミング距離が少なくともD

Question

となるようにN個の数字を生成する.N、B、およびDが与えられた場合、長さBビット（1 < = B < = 8）であり、各符号語は、他の符号語のそれぞれからD（1 < = D < = 7）のハミング距離以上離れている。一対の符号語間のハミング距離は、その2進表記が異なる2進ビットの数である。

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

ビット差：5ビットが異なっていたので、xxxは は、ハミング距離であるXX（0x554が進数字5,5と16進数を意味し、および4）2つのコードワード0x554と0x234とその違いを考慮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 

Iは、サブセット内の他の数を持つピックアップサブセット内の各数値を長さBの全てのコードワード（バイナリ文字列）を生成し、サイズNのすべてのサブセットを選んで試してみて、それかどうかを確認することができ少なくともDハムですしかし、これは時間が必要です。これは時間を必要とします。最悪のケースでは恐ろしいことがありますnCk

番号を効率的に生成するにはどうすればよいですか？

Answer 1

Thisも同様の質問です。効率的な建設は未解決の問題であるとの回答/コメントにも言及しています。

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.]] 

ここ

はのpython3にcvxpyでモデル化（NP困難である）整数プログラミングを用いコンパクトアプローチあります編集：以前のアプローチ（別のソルバー-pアラム）は48分必要でしたが、現在は〜8秒しかかかりませんでした。私は商用ソルバーを使用しました（非学業用では無料ではありません）！

私はSAT解決のアプローチがより速くなると思いますが、これは本当に（上記の私のリンクで言及されているように）非常に難しい問題です！