Поиск минимального подмножества столбцов, которые делают строки в матрице уникальными

На самом деле, моя первоначальная формулировка была не очень хороша. Это лучше в качестве обложки набора.

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

Наблюдение: если M имеет уникальные строки без обоих столбцов i и j, то оно имеет уникальные строки без столбца i и без столбца j независимо друг от друга (другими словами, добавление столбца к матрице с уникальными строками не может сделать строки не уникальными). Следовательно, вы должны быть в состоянии найти минимальное (не просто минимальное) решение, используя поиск в глубину.

def has_unique_rows(M):
    return len(set([tuple(i) for i in M])) == len(M)

def remove_cols(M, cols):
    ret = []
    for row in M:
        new_row = []
        for i in range(len(row)):
            if i in cols:
                continue
            new_row.append(row[i])
        ret.append(new_row)
    return ret


def minimum_unique_rows(M):
    if not has_unique_rows(M):
        raise ValueError("M must have unique rows")

    cols = list(range(len(M[0])))

    def _cols_to_remove(M, removed_cols=(), max_removed_cols=()):
        for i in set(cols) - set(removed_cols):
            new_removed_cols = removed_cols + (i,)
            new_M = remove_cols(M, new_removed_cols)
            if not has_unique_rows(new_M):
                continue
            if len(new_removed_cols) > len(max_removed_cols):
                max_removed_cols = new_removed_cols
            return _cols_to_remove(M, new_removed_cols, max_removed_cols)
        return max_removed_cols

    removed_cols = _cols_to_remove(M)
    return remove_cols(M, removed_cols), removed_cols

(обратите внимание, что мои имена переменных ужасны)

Вот это на твоей матрице

In [172]: rows = [
   .....:     [2, 1, 0, 0],
   .....:     [2, 0, 0, 0],
   .....:     [2, 1, 2, 2],
   .....:     [1, 2, 2, 2],
   .....:     [2, 1, 1, 0]
   .....: ]

In [173]: minimum_unique_rows(rows)
Out[173]: ([[1, 0], [0, 0], [1, 2], [2, 2], [1, 1]], (0, 3))

Я сгенерировал случайную матрицу (используя sympy.randMatrix), которая показана ниже.

⎡0  1  0  1  0  1  1⎤
⎢                   ⎥
⎢0  1  1  2  0  0  2⎥
⎢                   ⎥
⎢1  0  1  1  1  0  0⎥
⎢                   ⎥
⎢1  2  2  1  1  2  2⎥
⎢                   ⎥
⎢2  0  0  0  0  1  1⎥
⎢                   ⎥
⎢2  0  2  2  1  1  0⎥
⎢                   ⎥
⎢2  1  2  1  1  0  1⎥
⎢                   ⎥
⎢2  2  1  2  1  0  1⎥
⎢                   ⎥
⎣2  2  2  1  1  2  1⎦

(обратите внимание, что сортировка строк M очень помогает при проверке этих вещей вручную)

In [224]: M1 = [[0, 1, 0, 1, 0, 1, 1], [0, 1, 1, 2, 0, 0, 2], [1, 0, 1, 1, 1, 0, 0], [1, 2, 2, 1, 1, 2, 2], [2, 0, 0, 0, 0, 1, 1], [2, 0, 2, 2, 1, 1, 0], [2, 1, 2, 1, 1, 0
, 1], [2, 2, 1, 2, 1, 0, 1], [2, 2, 2, 1, 1, 2, 1]]

In [225]: minimum_unique_rows(M1)
Out[225]: ([[1, 1, 1], [2, 0, 2], [1, 0, 0], [1, 2, 2], [0, 1, 1], [2, 1, 0], [1, 0, 1], [2, 0, 1], [1, 2, 1]], (0, 1, 2, 4))

Вот грубая проверка, что это минимальный ответ (на самом деле минимумов довольно много).

In [229]: from itertools import combinations

In [230]: print([has_unique_rows(remove_cols(M1, r)) for r in combinations(range(7), 6)])
[False, False, False, False, False, False, False]

In [231]: print([has_unique_rows(remove_cols(M1, r)) for r in combinations(range(7), 5)])
[False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False]

In [232]: print([has_unique_rows(remove_cols(M1, r)) for r in combinations(range(7), 4)])
[False, True, False, False, False, False, False, False, False, False, True, False, False, False, False, False, True, False, False, False, False, False, False, False, True, False, False, True, False, False, False, False, False, True, True]

Вот мое жадное решение. (Да, это не соответствует вашему «оптимальному» критерию.) Случайным образом выберите строку, которую можно безопасно выбросить, и выбросьте ее. Продолжайте, пока не закончатся такие ряды. Я уверен, что is_valid можно оптимизировать.

rows = [
    [2, 1, 0, 0],
    [2, 0, 0, 0],
    [2, 1, 2, 2],
    [1, 2, 2, 2],
    [2, 1, 1, 0]
]

col_names = [0, 1, 2, 3]

def is_valid(rows, col_names):
    # it's valid if every row has a distinct "signature"
    signatures = { tuple(row[col] for col in col_names) for row in rows }
    return len(signatures) == len(rows)

import random    
def minimal_distinct_columns(rows, col_names):
    col_names = col_names[:]
    random.shuffle(col_names)
    for i, col in enumerate(col_names):
        fewer_col_names = col_names[:i] + col_names[(i+1):]
        if is_valid(rows, fewer_col_names):
            return minimal_distinct_columns(rows, fewer_col_names)
    return col_names        

Поскольку он жадный, он не всегда получает лучший ответ, но он должен быть относительно быстрым (и простым).

Хотя я уверен, что есть лучшие подходы, это напомнило мне о некоторых генетических алгоритмах, которые я делал в 90-х. Я написал быструю версию, используя пакет R GA.

library(GA)

matrix_to_minimize <- matrix(c(2,2,1,1,2, 
                               1,0,1,2,1,
                               0,0,2,2,1,
                               0,0,2,2,0), ncol=4)

evaluate <- function(indices) {
  if(all(indices == 0)) {
    return(0)
  }
  selected_cols <- matrix_to_minimize[, as.logical(indices), drop=FALSE]

  are_unique <- nrow(selected_cols) == nrow(unique(selected_cols))
  if (are_unique == FALSE) {
    return(0)
  }

  retval <- (1/sum(as.logical(indices)))
  return(retval)
}

ga_results <- ga("binary", evaluate, 
             nBits=ncol(matrix_to_minimize), 
             popSize=10 * ncol(matrix_to_minimize), #why not
             maxiter=1000,
             run=10) #probably want to play with this

print("Best Solution: ")
print(ga_results@solution)

Я не знаю, хорош он или оптимален, но могу поспорить, что он даст достаточно хороший ответ за разумное время? :)