查找使矩阵中的行唯一的列的最小子集

Question

什么是通用、有效的算法来查找离散值矩阵中使行唯一的列的最小子集。

例如，考虑这个矩阵（带有命名列）：

A B C D
 2 1 0 0
 2 0 0 0
 2 1 2 2
 1 2 2 2
 2 1 1 0

矩阵中的每一行都是唯一的。但是，如果我们删除列a并d保持相同的属性。

我可以枚举所有可能的列组合，但是，随着矩阵的增长，这很快就会变得棘手。有没有更快、最优的算法来做到这一点？

Answer 1

其实我原来的配方不太好。这更适合用作套装封面。

import pulp

# Input data
A = [
    [2, 1, 0, 0],
    [2, 0, 0, 0],
    [2, 1, 2, 2],
    [1, 2, 2, 2],
    [2, 1, 1, 0]
]

# Preprocess the data a bit.
# Bikj = 1 if Aij != Akj, 0 otherwise
B = []
for i in range(len(A)):
    Bi = []
    for k in range(len(A)):
        Bik = [int(A[i][j] != A[k][j]) for j in range(len(A[i]))]
        Bi.append(Bik)
    B.append(Bi)

model = pulp.LpProblem('Tim', pulp.LpMinimize)

# Variables turn on and off columns.
x = [pulp.LpVariable('x_%d' % j, cat=pulp.LpBinary) for j in range(len(A[0]))]

# The sum of elementwise absolute difference per element and row.
for i in range(len(A)):
    for k in range(i + 1, len(A)):
        model += sum(B[i][k][j] * x[j] for j in range(len(A[i]))) >= 1

model.setObjective(pulp.lpSum(x))
assert model.solve() == pulp.LpStatusOptimal
print([xi.value() for xi in x])