matrix manipulation

[haris riaz]

suppose i got a matrix

0 1 0 0 2
0 0 0 4 0
5 0 2 1 3
4 4 5 0 0
0 3 2 0 2
Select a matching by choosing a set of zeros so that each row or column has only one selected. It means that i should have only one zero selected from each row and column!
i implemented several of my logics in mind but there comes a problem in every one! kindly help me! my project is badly stuck at this point just because of this stupid step!
i have to make a new matrix 2d in which the zeros from rows and columns should be selected in a way that they are unique!!

like in this case output should be
1 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 1 0

[Labdabeta]

Perhaps a path finding AI algorithm such as a depth first search (look it up) would be helpful. Basically if you can define this class you can solve any problem:

class Node
{
    private:
    //anything you need
    public:
    vector<Node> getAllPossibleMoves();//in this case it would return all valid selections of 0s in your matrix
    bool isVictory();//return true if this Node represents the goal
};

Hope this helps.

[DeanMSands3]

EDIT: Labdabeta beat me to it! I spent so much time on this one! Darn the luck!

I'd suggest a recursive function with a backtracking mechanism like a stack or a double-ended queue.

deque<yourClass> *myRecursiveFunction(vector< vector< yourClass > > *dataSet){
    deque<yourClass> *dataSelected=new deque<yourClass>();
    if(myRecursiveInnerFunction(currentDataSet, 0, dataSelected))
        return dataSelected;
    else
        return NULL;
}

bool myRecursiveInnerFunction(vector< vector< yourClass > > *dataSet, int indexInDataSet, deque<yourClass> *dataSelected){
    //Have we reached the end yet?
    if((*dataSet)[indexInDataSet].size()>indexInDataSet){ 
        //Nope! Still going. 
        //Let's loop through 
        for(int i=0;i<(*dataSet)[indexInDataSet].size();i++){
            //Push next data piece onto the stack.
            dataSelected->pushBack((*dataSet)[indexInDataSet][i]);
            if(testValidHypothesis(dataSelected)){
                //OK, this will work. So far so good.
                if(myRecursiveInnerFunction(dataSet, indexInDataSet+1, dataSelected)){
                    //Hey! It worked! Ride the returns up back to the top!
                    return true;
                }
            }

            //If we made it here, the data didn't work out. Oops.
            //We remove the last piece.
            dataSelected->pop_back();
            //And we loop again.

        }
        //Looked through all possibilities for this set. An earlier piece of data must be wrong.
        //Going back and trying again.
        return false;
    }
    else{
        //We've come to the end of the line. Everything checked out. We're done.
        return true;
    }
}

[histrungalot]

Using a recursive function as well. I just have one more bug (I think). I thought that function was getting to complex but maybe not.
Got to solve it, it's consuming me now.

[histrungalot]

The trick here is as you move through the matrix, you have to keep track of the zeros that tried before. What I did is as I walk through the matrix looking for zeros I check the candidate zero matrix element to see if the row that the zero is contained in is not in the current answer set.

Algorithm

1. Start at column x
2. Check to see if we have a solution for each column, if so we are done
3. Otherwise, search down each column by the number of rows
4. Keep track if you have seen a zero in the search column
5. Before you check for a zero, check to see if the row you are going to check is not in the current solution set
6. If row is not in set then you can look for a zero in that row, if that row is, then move to next row.
7. Now you can check if this matrix element (row,column) is zero.
8. If zero check to see if the row we are on is not in the do not use list. There is a separate list for each column we are searching.
9. If row not in the list, we can add this matrix element position to the solution set and also add this row to the do not use list for this column
10. Next clear any of the do not use list for all columns larger than the current column
11. Call the function again with the search column set to the current plus 1
12. If you loop through all of the rows for this column and don't have an possible solution then one of two conditions must be true: 1. There are no zeros in the column or 2. The selections from the previous columns make any choose of zero in this column invalided or it was in the do not use list.
13. If no zeros in this column (step 4 kept track) then there is no solution
14. If previous choices caused you to not be able to select a zero from this column then we have to backtrack
15. To backtrack you have to remove the previous columns solution from the solution set
16. Then call the function with the search column equal to the current column minus 1. Now you are back to step 1.

I don't know if I explained it well enough so I'm going to post the code.

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>
using namespace std;

inline void printIt(vector<int> &m, int r,int c){
   for (int i(0); i<r;i++){
     for (int j(0); j<c;j++){
       cout << m.at(i*c+j) << " ";
     }
     cout << endl;
   }
}

void printAns(map<int,int> &ans,int r, int c){
   cout << "Ans:  " << endl;
   for(int i(0);i<r;i++){
     for(int j(0);j<c;j++){
       if ( ans.find(i) != ans.end() && ans[i] == j)
          cout << "1 ";
       else 
          cout << "0 ";
     }
     cout << endl;
   }
} 

inline bool checkOK(int c, int r, map<int,list<int> > &a){
  return (find(a[c].begin(),a[c].end(),r)==a[c].end());
}

inline void removeVal(int c, map<int,int> &ans){
  map<int,int>::iterator pos(ans.begin());
  for (;pos!=ans.end();pos++){
    if ( pos->second == c ){
      ans.erase(pos);
      break;
    }
  }
}

bool findIt(int r, int c, int colSrch, vector<int> &m, map<int,int> &ans, map<int,list<int> > &dontUse){
   bool                   ret(false),zero(false);
   int                    i(0);

   if ( ans.size() != r ) {
      for ( i=0; i < r; i++){
        zero |= !m.at(i*c+colSrch);
        if ( ans.find(i) == ans.end() && !m.at(i*c+colSrch) && checkOK(colSrch,i,dontUse)){
            ans[i] = colSrch;
            dontUse[colSrch].push_back(i);
            dontUse.erase(dontUse.find(colSrch+1),dontUse.end());
            ret = findIt(r,c,colSrch+1,m,ans,dontUse);
            break;
        }
      }
      if ( zero ){
        if (i==r && !ret) {
          if ( colSrch-1 >= 0){
            removeVal(colSrch-1,ans);
            ret = findIt(r,c,colSrch-1,m,ans,dontUse);
          }
        }
      } 
   }
   else {
     ret = true;
   }

   return ret;
}
int main(){
   map<int,list<int> >    dontUse;
   map<int,int>           ans;
   vector<int>            m;
   int                    rows(5),cols(5);
   m.push_back(0),m.push_back(1),m.push_back(0),m.push_back(0),m.push_back(2); 
   m.push_back(0),m.push_back(0),m.push_back(0),m.push_back(4),m.push_back(0); 
   m.push_back(5),m.push_back(0),m.push_back(2),m.push_back(1),m.push_back(3); 
   m.push_back(4),m.push_back(4),m.push_back(5),m.push_back(0),m.push_back(0); 
   m.push_back(0),m.push_back(3),m.push_back(2),m.push_back(0),m.push_back(2); 

   printIt(m,rows,cols);
   if ( rows == cols )
     if (findIt(rows,cols,0,m,ans,dontUse) )
       printAns(ans,rows,cols);
     else
       cout << "No answer!" << endl;
   else  
     cout << "Rows != Cols" << endl;
   return 0;
}