# Find all sets of n unique rows in matrix

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.

• 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? – Raphael Jul 14 '15 at 14:14
• 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. – Raphael Jul 14 '15 at 14:19
• @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. – Jager Jul 14 '15 at 15:01
• 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. – Raphael Jul 14 '15 at 15:10