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


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)


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

Expected output:

[0, 1, 3, 4]


  • 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)
  • 2
    \$\begingroup\$ Wow, ok, your question is poorly worded. You want to SELECT the least number of rows to have unique values in each row for all columns. I definitely did not get that from your Question. \$\endgroup\$ Sep 10, 2019 at 19:59
  • \$\begingroup\$ Your example is really confusing because you're saying 2 columns, but the example contains 3 columns. Please don't copy/paste from Pandas and consider re-writing the question using pure Python. \$\endgroup\$
    – mmla
    Sep 11, 2019 at 13:17
  • \$\begingroup\$ Your own question states "all the values in each column occur..." If all columns don't matter, then this statement is wrong. \$\endgroup\$ Sep 11, 2019 at 13:22
  • \$\begingroup\$ @mmla The "first" column is the row index. It's not part of the data set. Which is why there's a blank spot on the first row/first column area. \$\endgroup\$ Sep 11, 2019 at 13:23
  • \$\begingroup\$ @Draco18s Yes, I know. It adds nothing to the problem statement. Why include it? \$\endgroup\$
    – mmla
    Sep 11, 2019 at 14:14

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

  • \$\begingroup\$ I am not sure what transformation is expected from the DataFrame example to be taken as input for opt? \$\endgroup\$ Sep 27, 2019 at 6:51
  • \$\begingroup\$ @PascalVKooten The function takes an ordinary list of lists, so the small example is computed like this: opt([[1,1],[2,2],[3,4],[3,3],[4,4]]). \$\endgroup\$ Sep 27, 2019 at 7:26
  • \$\begingroup\$ Thanks! It is very slow but it is a solution that gets an optimal result. The alternative of doing a greedy solution is much faster, but at the cost of not giving an optimal solution. \$\endgroup\$ Sep 27, 2019 at 8:23
  • \$\begingroup\$ I was not able to find an optimizer that gave me a faster solution than 1 minute. \$\endgroup\$ Sep 27, 2019 at 8:23
  • \$\begingroup\$ You asked for a minimal set, not a small one. I don't think you can do that much faster. Asking for the best solution one can get in a fixed time would have been another interesting challenge. What input sizes did you use in your tests? \$\endgroup\$ Sep 27, 2019 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.