c++ - Find the maximum possible mex (minimal excluded) number from a square matrix - Stack Overflow

admin管理员组

文章数量:1417070

I have a question about the following challenge:

Given a n by n square matrix of positive integers, select n cells that do not share rows or columns. The goal is to select cells that maximize the lowest positive integer that is not selected.

Example

For the matrix

[ 21  13  21* 4
  19   4  16  2*
  17   1* 11  1
   0*  0   0  0
]

Select the marked cells. The smallest positive integer not selected is 3.

I was thinking of some dynamic programming approach, but could not do it.

What is the an efficient approach to solve this problem?

I have a question about the following challenge:

Given a n by n square matrix of positive integers, select n cells that do not share rows or columns. The goal is to select cells that maximize the lowest positive integer that is not selected.

Example

For the matrix

[ 21  13  21* 4
  19   4  16  2*
  17   1* 11  1
   0*  0   0  0
]

Select the marked cells. The smallest positive integer not selected is 3.

I was thinking of some dynamic programming approach, but could not do it.

What is the an efficient approach to solve this problem?

• c++
• algorithm
• optimization

Share Improve this question Follow edited Feb 3 at 19:38 trincot 353k3737 gold badges273273 silver badges328328 bronze badges asked Feb 2 at 20:29 OXENOXEN 1333 bronze badges 16

• from the matrix i have selected the number 0,1,2,21 as highlighted with constraint as they don't have same row or column, now if you find the mex of the sequence you will get 3, what i want is to make the mex of the sequence maximum. mex reference - en.wikipedia./wiki/Mex_(mathematics) – OXEN Commented Feb 2 at 20:53
• 1 The 'excluded' number is from the set of natural numbers, not the matrix? – ravenspoint Commented Feb 2 at 20:58
• 1 Can you give an example of what you mean by making the mex of the sequence maximum?? – Onyambu Commented Feb 2 at 21:00
• 1 "I was thinking of some dynamic programming approach but could not do it" -- If you mean you could not do dynamic programming in general, that is too broad a subject for a Stack Overflow question. If you mean your attempt had an error, then your question should show that attempt and the error. – JaMiT Commented Feb 2 at 21:06
• 1 For a n by n matrix, the maximum possible unselected integer is n. If any of 0 ... n are missing, then the max possible unselected is the smallest of 0 ... n that is missing. If any of 0 ... n share a row or column, then the largest shared integer is the maximum not selected. – ravenspoint Commented Feb 3 at 0:16

 |  Show 11 more comments

1 Answer 1

Sorted by: Reset to default 1

Well, I asked for a reopen, so I had better have a go. This is basically testing all feasible routes via backtracking.

It first stores all the (row,column) positions of the 0's, then the 1's, then 2's, etc. up to N-1.

It then tests the placements of the 0's, 1's, 2's etc in turn.

At the end it outputs the first excluded non-negative integer (same length as the fittable sequence) and the (row,column) positions of what it has managed to fit. You can take what you like from the remaining rows and columns; they won't change the Max-Mex.

#include <iostream>
#include <vector>
using namespace std;

using sequence = vector<pair<int,int>>;

//----------------------------------------------------------------------

void optimise( int level, const vector<sequence> &locations, sequence &best, sequence &current, vector<bool> &rowUsed, vector<bool> &colUsed )
{
   if ( level == locations.size() ) return;

   for ( auto pr : locations[level] )                                          // all possibilities at this level
   {
      int i = pr.first, j = pr.second;
      if ( !( rowUsed[i] || colUsed[j] ) )
      {
         rowUsed[i] = colUsed[j] = true;
         current.push_back( { i, j } );                                        // next route to try

         if ( current.size() > best.size() ) best = current;

         optimise( level + 1, locations, best, current, rowUsed, colUsed );    // go to next level

         current.pop_back();                                                   // clean up for next route
         rowUsed[i] = colUsed[j] = false;
      }
   }
}

//----------------------------------------------------------------------

sequence maxMex( const vector<vector<int>> &A )
{
   int N = A.size();        // The best possible would be N
   // Locate all the x=0, 1, ... (N-1) and store them in locations[x]
   vector<sequence> locations( N );
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) if ( A[i][j] < N ) locations[A[i][j]].push_back( { i, j } );
   }

   sequence best, current;
   vector<bool> rowUsed( N, false ), colUsed( N, false );
   optimise( 0, locations, best, current, rowUsed, colUsed );
   return best;
}

//----------------------------------------------------------------------

int main()
{
   vector<vector<int>> A = { { 21, 13, 21, 4 },
                             { 19,  4, 16, 2 },
                             { 17,  1, 11, 1 },
                             {  0,  0,  0, 0 } };

   sequence best = maxMex( A );
   cout << "Max Mex = " << best.size() << "\n\n";
   cout << "Value" << '\t' << "Row" << '\t' << "Column" << '\n';
   for ( int n = 0; n < best.size(); n++ ) cout << n << '\t' << best[n].first << '\t' << best[n].second << '\n';
}

Output:

Max Mex = 3

Value   Row     Column
0       3       0
1       2       1
2       1       3

本文标签： cFind the maximum possible mex (minimal excluded) number from a square matrixStack Overflow