A greedy solution for matrix rearrangement

Question

I am working on something that I feel is NP-hard problem. So, I'm not looking for the optimal solution, but I'm looking for the best heuristic. As input, an integer input matrix is ​​entered (matrix A in the following example), and I should get an integer output matrix (matrix B in the following example), the number of rows of which is less than the input matrix and must obey the following two conditions:

1) Each column of the output matrix must contain integers in the same order as in the input matrix. (In the example below, the first column of matrix A and matrix B has the same numbers 1,3 in the same order.)

2) The same integers should not appear on the same line (in the example below, the first row of matrix B contains integers 1,3 and 2 that are different from each other.)

Note that the input matrix always obeys the second condition.

What does a greedy algorithm look like to solve this problem?

Example:

In this example, the output matrix "Matrix B" contains all the integers as they appear in the input matrix "Matrix A", but the output matrix has 5 rows and the input matrix has 6 rows. Thus, the output of 'Matrix B' is a valid solution for entering 'Matrix A'.

Answer 1

. , , , , , , , . , , .

, . , , , . , k-, , k .

, , , , , . , , .

, , , F > 1. , . , , F , , , F.

Answer 2

, , .

:

For each column c in A:
   r = 0 // row index of next element in A
   nextRow = 0 // row index of next element to be placed in B
   while r < A.NumRows()
      while r < A.NumRows() && A[r, c] is null:
         r++ // increment row to check in A
      if r < A.NumRows() // we found a non-null entry in A
         while nextRow < A.NumRows() && ~CheckConstraints(A[r,c], B[nextRow, c]):
            nextRow++ // increment output row in B
         if 'nextRow' >= A.NumRows()
            return unsolvable // couldn't find valid position in B
         B[nextRow, c] = v // successfully found position in B
          ++nextRow  // increment output row in B

, "" B , . , , B. , .

CheckConstraints B, , .

, B <= A, , B , A .