Transform a boolean matrix into rows where none of the entries are superset of the other

user_11710380 0
Viewed 82

I have a matrix of boolean values where the columns are unique actions and the rows are all possible solutions, so each row uses 1 to indicate whether this solution requires the associated unique action. I want to eliminate all rows that are a superset of any other row in the set and return a matrix where none of the rows are supersets of any other row.

Is there any way to efficiently do this in less than n^2 time?

Tried graph algorithms (failed) and general sets manipulations but that's not efficient enough.

algorithm
1 Answers

One Solution that I can think of right now will work if you have the rows sorted according to the number of 1s.

  1. Loop over rows in ascending order of number of 1s

  2. For each 1, store the row indices for rows that:

    • have a 1 in the same column
    • are below the current row (i.e. have more 1s)
  3. when you are finished reading for all ones in the current row, take an intersect of the row index lists and remove the before starting the step 2 for the next iteration.

This way, the complexity will be O(N^2).

user_114467210
Related