0
$\begingroup$

I am looking for an efficient method to find all unique combinations of $n$ rows in a matrix.

For example, if $n=6$, then I want to find all sets of 6 rows from the input set C in which the columns have only unique values.

Input:

C =
[[ 3.031  3.392  2.987  4.248  3.364  3.354]
 [ 3.031  3.392  2.987  3.975  2.911  3.354]
 [ 3.476  3.756  3.759  4.248  3.364  4.241]
 [ 3.476  3.756  3.759  3.661  2.911  4.241]
 [ 3.476  3.756  3.759  3.975  3.364  4.241]
 [ 3.476  3.756  3.759  3.975  3.364  4.418]
 [ 3.476  3.899  3.759  4.248  3.364  4.241]
 [ 3.476  3.899  3.759  3.661  3.364  4.241]
 [ 3.476  3.899  3.759  3.661  3.364  4.418]
 [ 3.476  3.899  3.759  3.661  2.911  4.241]
 [ 3.476  3.899  3.759  3.975  3.364  4.241]
 [ 3.476  3.899  3.759  3.975  3.364  4.418]
 [ 5.409  6.222  5.866  4.248  4.907  6.193]
 [ 5.409  6.222  5.866  3.975  4.907  6.193]
 [ 5.409  6.057  5.866  4.248  4.907  6.193]
 [ 4.725  3.899  4.196  7.183  5.255  4.241]
 [ 4.725  3.899  4.196  7.183  5.255  4.418]
 [ 7.421  6.057  7.19   8.916  5.768  5.096]
 [ 6.711  8.405  7.117  5.344  8.285  9.298]]

Desired Output:

result =
 [[ 3.031  3.392  2.987  4.248  3.364  3.354]
 [ 3.476  3.756  3.759  3.661  2.911  4.241]
 [ 5.409  6.222  5.866  3.975  4.907  6.193]
 [ 4.725  3.899  4.196  7.183  5.255  4.418]
 [ 7.421  6.057  7.19   8.916  5.768  5.096]
 [ 6.711  8.405  7.117  5.344  8.285  9.298]]

This is easy for a small dataset like this, however I find it hard to find a solution that scales well (when C has more than 150 rows).

Current solution

Iterator It loops over all combinations of $n$ rows. for $n=6$, It starts with indices [0,1,2,3,4,5]. These indices are used to select rows from C.

Until iterator It is done:

  1. Find rows that have duplicate entries. e.g. rows 2,3 and 3,4 have duplicate entries. So duplicate indices = [2,3,4,5]
  2. get lowest index of rows with. In this case: s = 2
  3. Skip index at place s. In this case s = 2 so that It.indices = [0,1,3,4,5,6]
  4. if no duplicate entries are found, add current combination to solutions

In this way we don't have to check all combinations, because we skip all combinations of which we know have non-unique entries. However the computation time still rises exponentially with size of C.

$\endgroup$
  • $\begingroup$ So you want largest sets of rows so that each columns contains no value twice? What have you tried and where did you get stuck? $\endgroup$ – Raphael Jul 14 '15 at 14:14
  • 1
    $\begingroup$ Hint: if you model each row by a node in a graph and connect nodes iff the rows share at least one value, you are searching for maximum independent sets. That's an NP-hard problem in general. Finding maximal independent sets, on the other hand, can be solved in polynomial time. I don't see off the top of my head if your problem is easier. $\endgroup$ – Raphael Jul 14 '15 at 14:19
  • $\begingroup$ @Raphael I do not per se want the largest set, rather a set of n rows. However if a solution for the largest set is easier, then that is also great. I will add my current solution, which works but is too slow. $\endgroup$ – Jager Jul 14 '15 at 15:01
  • $\begingroup$ No, largest is hard. Maximal solutions are such that are not a proper subset of another solution. Finding these is "easy" for Independent Set; cf Wikipedia. You should clarify in the question what exactly your input and desired output are. $\endgroup$ – Raphael Jul 14 '15 at 15:10

Your Answer

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

Browse other questions tagged or ask your own question.