快速代碼，以確定是否列的任意兩個子集具有相同的總和

Question

對於給定的n和m我遍歷由米局部circulant矩陣所有n與是0或1。我想找到，如果有一個條目矩陣，使得不存在給出相同和的列的兩個子集。在這裏，當我們添加列時，我們只是按照元素進行。我目前的代碼通過ortools使用約束編程。然而，它不是我想要的那麼快。對於n = 7和m = 12，它需要3分鐘以上，對於n = 10，m = 18，即使只考慮2^18 = 262144個不同的矩陣，它也不會終止。這是我的代碼。

from scipy.linalg import circulant 
import numpy as np 
import itertools 
from ortools.constraint_solver import pywrapcp as cs 

n = 7 
m = 12 

def isdetecting(matrix): 
    X = np.array([solver.IntVar(values) for i in range(matrix.shape[1])]) 
    X1 = X.tolist() 
    for row in matrix: 
     x = X[row].tolist() 
     solver.Add(solver.Sum(x) == 0) 
    db = solver.Phase(X1, solver.INT_VAR_DEFAULT, solver.INT_VALUE_DEFAULT) 
    solver.NewSearch(db) 
    count = 0 
    while (solver.NextSolution() and count < 2): 
     solution = [x.Value() for x in X1] 
     count += 1 
    solver.EndSearch() 
    if (count < 2): 
     return True 

values = [-1,0,1] 
solver = cs.Solver("scip") 

for row in itertools.product([0,1],repeat = m): 
    M = np.array(circulant(row)[0:n], dtype=bool) 
    if isdetecting(M): 
     print M.astype(int) 
     break 

可這個問題可以解決速度不夠快，使N = 10，M = 18可以解決？

Answer 1

一個問題是，你是全局聲明「求解器」變量，它似乎混淆或工具重複使用很多次。在「isdetecting」內移動它時，（7,12）問題在大約7秒內解決得更快，而原始模型則需要2:51分鐘。儘管如此，我還沒有檢查它是否存在更大的問題。

而且，它可能是測試不同標號L（而不是solver.INT_VAR_DEFAULT和solver.INT_VALUE_DEFAULT）好主意，但二進制值往往是不同的標號L不是很靈敏。查看另一個標籤的代碼。

def isdetecting(matrix): 
    solver = cs.Solver("scip") # <---- 
    X = np.array([solver.IntVar(values) for i in range(matrix.shape[1])]) 
    X1 = X.tolist() 
    for row in matrix: 
     x = X[row].tolist() 
     solver.Add(solver.Sum(x) == 0) 
    # db = solver.Phase(X1, solver.INT_VAR_DEFAULT, solver.INT_VALUE_DEFAULT) 
    db = solver.Phase(X1, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_CENTER_VALUE)  
    solver.NewSearch(db) 
    count = 0 
    while (solver.NextSolution() and count < 2): 
     solution = [x.Value() for x in X1] 
     count += 1 
    solver.EndSearch() 
    if (count < 2): 
     print "FOUND" 
     return True 

編輯：這裏有限制條件來刪除評論中提到的全0解決方案。我所知道的，它需要一個單獨的列表。現在需要更長的時間（10.4s vs 7s）。

X1Abs = [solver.IntVar(values, 'X1Abs[%i]' % i) for i in range(X1_len)] 
for i in range(X1_len): 
    solver.Add(X1Abs[i] == abs(X1[i])) 
solver.Add(solver.Sum(X1Abs) > 0)  

Answer 2

喜歡的東西，這是我的想法。我估計我的機器上少於8小時的命令行參數10 18的運行時間。

public class Search { 
    public static void main(String[] args) { 
     int n = Integer.parseInt(args[0]); 
     int m = Integer.parseInt(args[1]); 
     int row = search(n, m); 
     if (row >= 0) { 
      printRow(m, row); 
     } 
    } 

    private static int search(int n, int m) { 
     if (n < 0 || m < n || m >= 31 || powOverflows(m + 1, n)) { 
      throw new IllegalArgumentException(); 
     } 
     long[] column = new long[m]; 
     long[] sums = new long[1 << m]; 
     int row = 1 << m; 
     while (row-- > 0) { 
      System.err.println(row); 
      for (int j = 0; j < m; j++) { 
       column[j] = 0; 
       for (int i = 0; i < n; i++) { 
        column[j] = (column[j] * (m + 1)) + ((row >> ((i + j) % m)) & 1); 
       } 
      } 
      for (int subset = 0; subset < (1 << m); subset++) { 
       long sum = 0; 
       for (int j = 0; j < m; j++) { 
        if (((subset >> j) & 1) == 1) { 
         sum += column[j]; 
        } 
       } 
       sums[subset] = sum; 
      } 
      java.util.Arrays.sort(sums); 
      boolean duplicate = false; 
      for (int k = 1; k < (1 << m); k++) { 
       if (sums[k - 1] == sums[k]) { 
        duplicate = true; 
        break; 
       } 
      } 
      if (!duplicate) { 
       break; 
      } 
     } 
     return row; 
    } 

    private static boolean powOverflows(long b, int e) { 
     if (b <= 0 || e < 0) { 
      throw new IllegalArgumentException(); 
     } 
     if (e == 0) { 
      return false; 
     } 
     long max = Long.MAX_VALUE; 
     while (e > 1) { 
      if (b > Integer.MAX_VALUE) { 
       return true; 
      } 
      if ((e & 1) == 1) { 
       max /= b; 
      } 
      b *= b; 
      e >>= 1; 
     } 
     return b > max; 
    } 

    private static void printRow(int m, int row) { 
     for (int j = 0; j < m; j++) { 
      System.out.print((row >> j) & 1); 
     } 
     System.out.println(); 
    } 
}