matrix nxn with verify

[Angela Santoro]

hello guys.
I have created an n × n matrix. I have created a bool to verify that every nonzero element less than n appears only once time in each row and column of the matrix.
For example

1 2 3
3 1 2
0 0 0

1 2 3
2 0 1
3 0 2

1 2 3
3 1 2
2 3 1

this matrixs are ok.
Insted

1 1 2
2 3 1
0 2 3

it is not ok because 1 appear two times in row 1, and

0 0 0
1 2 3
0 2 1

it is not ok because 2 appear two times in column 1.

To do this I have created a counter "nr_times" that is incremented each time that the element will appear on the same column (row). If it is 1, the verify it's OK!. Each time that the rows and the columns are formed by only zero, nr_times is 1. There are no mistakes, but verification does not do what I want.

This is the code:

#include <iostream>
#include <vector>
using namespace std;
 
typedef vector< vector<int> >  TwoDArray;

// bool to verify if it is a latin square
bool verifyL(TwoDArray &B){
    int n = B[0].size();  
    int sr[n];
    int sc[n];
    int nr_times;
     for(int i = 0; i < n; ++i) {    
            int sum = 0;
            for(int j = 0; j < n; ++j) 
                sum = sum + B[i][j];
                sr[i] = sum;
            }
    
        // check that s appears n times in each row
        for(int i = 0; i < n; ++i) {
            if (sr[i] == 0)
            nr_times = 1;
            else{    
        for(int s = 1; s <= n; ++s) {    
            nr_times=0;
            for(int j = 0; j < n; ++j) 
                        if (B[i][j] == s)
                        nr_times++;
            }
    }
            if (nr_times != 1) return false;
        }
        
    
      for(int j = 0; j < n; ++j) {
            int sum = 0;
            for(int i = 0; i < n; ++i) 
                sum = sum + B[i][j];
                sc[j] = sum;
            }

        // check that s appears n times in each column
        for(int j = 0; j < n; ++j) {
            if (sc[j] == 0)
            nr_times = 1;
            else{
            for(int s = 1; s <= n; ++s) {
            nr_times = 0;
            for(int i = 0; i < n; ++i) 
                        if (B[i][j] == s)
                        nr_times++;
            }
            }
            
            if (nr_times != 1) return false;
        }
    
  
    return true;
}
 
// bool to verify if it is a k-latin square

int main() {
    
// input order
    int n;
    cout << "Enter the order: n=";
    cin >> n;
 
 // 2D array costruction     
          TwoDArray B;
    B.resize(n);
    for (int i = 0; i < n; i++) {
        B[i].resize(n);
    }
   

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++){
                cout << "Enter the entrie in row ["<<i<<"], coloumn ["<<j<<"]";
                cin >> B[i][j];
            }
            cout<<"\nYou entered the following square \n";
            cout<<"\n";
            

// print latin square B  
        for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << '|';
                cout << B[i][j] << ' ';
        }
        cout << "|\n";
    } 
    
 //check if B is a latin square
        if (verifyL(B))
        cout << "This isn't a matrix of order "<<n<<" ok";
    else
        cout << "This is a matrix of order "<<n<<" ok";
         
    return 0;
}

in fact for
0 1
1 2
and
0 0
1 2
verify fail, but it is incorrect
can you help me please?

[Aslaville]

hello guys.
I have created an n × n matrix. I have created a bool to verify that every nonzero element less than n appears only once time in each row and column of the matrix.

You mean a function ?

Anyway, your code looks really complicated. Anyone trying to read through it would probably have to pick up a pencil and do some math.

You might want to look at std::map. Its a data structure provided by the C++ library which you can use to keep track of how many times a certain value(key) occurs. You can have something like this.

std::map<int, int> data;

//have some code looping through rows here
data[value_for_the_current_row]++;

At the end of the loop, check that none of the value for any key in the map is greater than 1.

for(auto it = data.begin(); it < data.end(); it++)
{
    if (it->second > 1) 
    //this value occurred more than once
}

[Angela Santoro]

i do it:

bool verifyL(TwoDArray &B) {
    int n = B[0].size();  
    int nr_times;
    for(int s = 1; s < n; ++s) {
        // check that s appears 1 times in each row
        for(int i = 0; i <= n; ++i) {
            nr_times = 0;
            for(int j = 0; j < n; ++j) {
                std::map<int,int>::iterator iter = B[i][j].find(s);

                if (iter != B[i][j].end()) {
                    nr_times += iter->second;
                }
            }

            if (nr_times != 1) return false;
        }
    }

    for(int s = 1; s <= n; ++s) {
        // check that s appears 1 times in each column
        for(int j = 0; j < n; ++j) {
            nr_times = 0;

            for(int i = 0; i < n; ++i) {
                std::map<int,int>::iterator iter = B[i][j].find(s);

                if (iter != B[i][j].end()) {
                    nr_times += iter->second;
                }
            }

            if (nr_times != 1) return false;
        }
    }

    return true;
}

but don't work

[Aslaville]

This code seems to work, am not even sure am looping through the columns correctly, I wrote it in hurry.

#include <vector>
#include <iostream>
#include <map>


using namespace std;


int main()
{
    vector<vector<int> > v = {{6, 1, 0},
                              {3, 0, 1},
                              {3, 4, 5}
                             };
    map<int, int> values;
    bool k_latin = true;


    //check the rows
    for (size_t i = 0; i < v.size(); i++){
        for (size_t j = 0; j < v[i].size();j++)
        {
            values[v[i][j]]++;
        }
        //ensure no key in the map has a value of >1
        for (auto it = values.begin(); it != values.end(); it++)
        {
            if(it->second > 1)
                k_latin = false;
        }


        values.clear();


        if(k_latin == false)
            break;


    }


    //check the columns
    for (size_t i = 0; i < v.size(); i++){
        for (size_t j = 0; j < v[i].size();j++)
        {
            values[v[j][i]]++;
        }
        //ensure no key in the map has a value of >1
        for (auto it = values.begin(); it != values.end(); it++)
        {
            if(it->second > 1)
                k_latin = false;
        }


        values.clear();


        if(k_latin == false)
            break;


    }


    if(k_latin)
        cout<<"Correct" <<endl;
    else 
        cout<<"not correct " <<endl;


    return 0;
}

[Guest]

i do it: (...) but don't work

As a sidenote, I recommend you make extensive use of const qualifiers to ensure that you're not accidentally modifying your input.

bool verifyL(const TwoDArray &B) {
...
std::map<int, int>::const_iterator iter = B[i][j].find(s);
if(iter != B[i][j].cend()) {
   ...
}

[Angela Santoro]

This code seems to work, am not even sure am looping through the columns correctly, I wrote it in hurry.

#include <vector>
#include <iostream>
#include <map>


using namespace std;


int main()
{
    vector<vector<int> > v = {{6, 1, 0},
                              {3, 0, 1},
                              {3, 4, 5}
                             };
    map<int, int> values;
    bool k_latin = true;


    //check the rows
    for (size_t i = 0; i < v.size(); i++){
        for (size_t j = 0; j < v[i].size();j++)
        {
            values[v[i][j]]++;
        }
        //ensure no key in the map has a value of >1
        for (auto it = values.begin(); it != values.end(); it++)
        {
            if(it->second > 1)
                k_latin = false;
        }


        values.clear();


        if(k_latin == false)
            break;


    }


    //check the columns
    for (size_t i = 0; i < v.size(); i++){
        for (size_t j = 0; j < v[i].size();j++)
        {
            values[v[j][i]]++;
        }
        //ensure no key in the map has a value of >1
        for (auto it = values.begin(); it != values.end(); it++)
        {
            if(it->second > 1)
                k_latin = false;
        }


        values.clear();


        if(k_latin == false)
            break;


    }


    if(k_latin)
        cout<<"Correct" <<endl;
    else 
        cout<<"not correct " <<endl;


    return 0;
}

it tell me: [Error] 'it' does not name a type

[MutantJohn]

The best advice I can give in a hurry is, write small functions that only do one thing then compose other functions out of those building blocks. This will help you manage complexity.

[jimblumberg]

Also here.

[Angela Santoro]

Or this?

bool verify(int m[N][N])
{
	int sr[N+1];

	for(int r=0; r<N; r++)
	{
		for(int i=0; i<N+1; i++) sr[i]=0;
		
		for(int c=0; c<N; c++)
			sr[m[r][c]]++;

		for(int i=1; i<N+1; i++)
			if(sr[i]>1)
				return false;
	}

	for(int c=0; c<N; c++)
	{
		for(int i=0; i<N+1; i++) sr[i]=0;
		
		for(int r=0; r<N; r++)
			sr[m[r][c]]++;

		for(int i=1; i<N+1; i++)
			if(sr[i]>1)
				return false;
	}

	return true;
}

[Aslaville]

it tell me: [Error] 'it' does not name a type

You're probably using an old compiler or you didn't switch C++11 on.

Or this?

bool verify(int m[N][N])
{
    int sr[N+1];

    for(int r=0; r<N; r++)
    {
        for(int i=0; i<N+1; i++) sr[i]=0;
        
        for(int c=0; c<N; c++)
            sr[m[r][c]]++;

        for(int i=1; i<N+1; i++)
            if(sr[i]>1)
                return false;
    }

Yes, I guess that should work too.

[Angela Santoro]

ok it's work, but it must do verify only for the non-zero values.

This code seems to work, am not even sure am looping through the columns correctly, I wrote it in hurry.

#include <vector>
#include <iostream>
#include <map>


using namespace std;


int main()
{
    vector<vector<int> > v = {{6, 1, 0},
                              {3, 0, 1},
                              {3, 4, 5}
                             };
    map<int, int> values;
    bool k_latin = true;


    //check the rows
    for (size_t i = 0; i < v.size(); i++){
        for (size_t j = 0; j < v[i].size();j++)
        {
            values[v[i][j]]++;
        }
        //ensure no key in the map has a value of >1
        for (auto it = values.begin(); it != values.end(); it++)
        {
            if(it->second > 1)
                k_latin = false;
        }


        values.clear();


        if(k_latin == false)
            break;


    }


    //check the columns
    for (size_t i = 0; i < v.size(); i++){
        for (size_t j = 0; j < v[i].size();j++)
        {
            values[v[j][i]]++;
        }
        //ensure no key in the map has a value of >1
        for (auto it = values.begin(); it != values.end(); it++)
        {
            if(it->second > 1)
                k_latin = false;
        }


        values.clear();


        if(k_latin == false)
            break;

Instead , this code does only occurs with non-zero elements:

bool verify(int m[N][N])
{
    int sr[N+1];
 
    for(int r=0; r<N; r++)
    {
        for(int i=0; i<N+1; i++) sr[i]=0;
         
        for(int c=0; c<N; c++)
            sr[m[r][c]]++;
 
        for(int i=1; i<N+1; i++)
            if(sr[i]>1)
                return false;
    }
 
    for(int c=0; c<N; c++)
    {
        for(int i=0; i<N+1; i++) sr[i]=0;
         
        for(int r=0; r<N; r++)
            sr[m[r][c]]++;
 
        for(int i=1; i<N+1; i++)
            if(sr[i]>1)
                return false;
    }
 
    return true;
}

Do you think I can adapt this code to a 3D matrix nxnxk size ?

[Angela Santoro]

i do it to verify that in a nxnxk array each nonzero element appears at most k times:

bool verifyK(ThreeDArray &A) {
    int n = A.size();
    int k = A[0][0].size();
    int sr[n*k+1];


    for(int r=0; r<n; r++)
    {
        for(int i=0; i<n+1; i++) sr[i]=0;
        
        for(int c=0; c<n; c++)
        for(int t=0; t<k; t++)
            sr[A[r][c][t]]++;

        for(int i=1; i<n+1; i++)
            if(sr[i]>k)
                return false;
    }

    for(int c=0; c<n; c++)
    {
        for(int i=0; i<n+1; i++) sr[i]=0;
        
        for(int r=0; r<n; r++)
        for(int t=0; t<k; t++)
            sr[A[r][c][t]]++;

        for(int i=1; i<n+1; i++)
            if(sr[i]>k)
                return false;
    }

    return true;
}

[Aslaville]

i do it to verify that in a nxnxk array each nonzero element appears at most k times:

Using braces in 'for' loops makes your code more readable. It's just a matter of time and even you, yourself will not be able to follow it.

Anyway, Am going to assume your code is correct so far except that it also catches zero elements (which are not supposed to be caught)

You just need to skip the zero elements.

    for(int r=0; r<n; r++)
    {
        for(int i=0; i<n+1; i++) sr[i]=0;
        
        for(int c=0; c<n; c++)
        for(int t=0; t<k; t++){
        if (A[r][c][t] == 0)
           continue;
            //otherwise count the occurrence.
            sr[A[r][c][t]]++;
         }

        for(int i=1; i<n+1; i++)
            if(sr[i]>k)
                return false;
    }

You get the idea, I hope.

[Aslaville]

Ooh, right, I note you already corrected the code not to catch zero element with another trick!

[Angela Santoro]

thanks a lot anyway even your solution is still interesting