3
\$\begingroup\$

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)
\$\endgroup\$
  • 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\$ – Draco18s Sep 10 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 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\$ – Draco18s Sep 11 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\$ – Draco18s Sep 11 at 13:23
  • \$\begingroup\$ @Draco18s Yes, I know. It adds nothing to the problem statement. Why include it? \$\endgroup\$ – mmla Sep 11 at 14:14
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I am not sure what transformation is expected from the DataFrame example to be taken as input for opt? \$\endgroup\$ – PascalVKooten Sep 27 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\$ – Christian Sievers Sep 27 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\$ – PascalVKooten Sep 27 at 8:23
  • \$\begingroup\$ I was not able to find an optimizer that gave me a faster solution than 1 minute. \$\endgroup\$ – PascalVKooten Sep 27 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\$ – Christian Sievers Sep 27 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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