Find minimal set of rows to retain all unique values in each column

Question

Given a matrix, the goal is to ensure all the values in each column occur at least once, while at the same time doing so requiring the least possible amount of rows. Fastest solution wins.

Note: a value in one column (e.g. 1) is considered different from the same value in another column.

Expected output: an array/list/series of row indices that retain all unique values across all columns.

Example data:

import numpy as np
import pandas as pd

np.random.seed(42)

num_rows = 10000
num_cols = 200
max_uniq_values = 10

data = pd.DataFrame({i: np.random.randint(0, max_uniq_values, num_rows)
                     for i in range(num_cols)})
# or python
# data = [np.random.randint(0, max_uniq_values, num_rows).tolist()
#         for i in range(num_cols)]

Minimal example (num_rows=5, num_cols=2, max_uniq_values=4)

Input:

    | 0  1
  --------
  0 | 1  1
  1 | 2  2
  2 | 3  4
  3 | 3  3
  4 | 4  4

Expected output:

[0, 1, 3, 4]

Additionally:

• Benchmark will happen on a 2015 Macbook Pro with CPU Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz.
• Restricted to use 1 core.
• External libraries allowed
• Blind test will be done on 10 random seeds (the same ones for each solution)

Answer 1

Python3 + PuLP library

This is equivalent to a set covering problem (where the elements are column/value pairs) which can be transformed into an integer linear programming problem.

from pulp import *

def opt(mat):
    num_rows = len(mat)
    covering_rows = {}
    for row_nr, vals in enumerate(mat):
        for pair in enumerate(vals):
            covering_rows.setdefault(pair, []).append(row_nr)
    prob = LpProblem("Minimal Covering Set of Rows", LpMinimize)
    vars = LpVariable.dicts("R", range(num_rows), 0, 1, LpInteger)
    prob += lpSum([vars[i] for i in range(num_rows)])
    for rowlist in covering_rows.values():
        prob += lpSum([vars[r] for r in rowlist]) >= 1
    prob.solve()
    assert prob.status==LpStatusOptimal, "Couldn't solve"
    return [r for r in range(num_rows) if value(vars[r])==1]

On debian, the relevant package is called python3-pulp.

The function handles matrices with 20 columns and 100 rows in about one minute on weak hardware. The best way to substantially improve the speed is probably to use a better solver, which the PuLP library allows by adding an argument to the solve method call.