C++

Forum

 
matrix with verify

sangi89 (6)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
#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 and index
	cout << "This program print a latin square of order n by your data \n \n";
    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 is a latin square of order "<<n<<".";
    else
        cout << "This is not a latin square of order "<<n<<".";
		 
    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?

Last edited on
coder777 (8439)
The easiest way to check for duplicates is a map. E.g. for column:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
     for(int i = 0; i < n; ++i)
     {	
            std::map<int, bool> col_map;
            bool failed = false;
            for(int j = 0; j < n; ++j) 
            {
            	if(col_map[B[i][j]])
            	{
            	  failed = true;
            	  break;
            	}
            }
            if(failed)
              break;
     }
For row just use another map and swapped loops. Not tested!
sangi89 (6)
It should be inserted instead of the bool ? I have never used a map
coder777 (8439)
hmm, I see my example was wrong (setting to true was missing). But you don't need a map. Here is the example using set
1
2
3
4
5
6
7
8
9
10
11
 
     for(int i = 0; i < n; ++i)
     {	
            std::set<int> col_set;
            for(int j = 0; j < n; ++j) 
            {
            	if(col_set.find(B[i][j]) != col_set.end())
            	  return false;
            	else
            	  col_set.insert(B[i][j]);
            }
     }


The trick is that the key in both container is unique.

However you can do this with vector:
1
2
3
4
5
6
7
8
9
10
11
 
     for(int i = 0; i < n; ++i)
     {	
            std::vector<int> col_vector;
            for(int j = 0; j < n; ++j) 
            {
            	if(std::find(col_vector.begin(), col_vector.end(), B[i][j]) != col_vector.end())
            	  return false;
            	else
            	  col_vector.push_back(B[i][j]);
            }
     }



For find() see:
http://www.cplusplus.com/reference/algorithm/find/?kw=find

For set see:
http://www.cplusplus.com/reference/set/set/?kw=set

For map see:
http://www.cplusplus.com/reference/map/map/?kw=map
sangi89 (6)
ok , so I have a carrier before its reporting col_vector of elements including 1 to n ?
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
#include <iostream>
#include <vector>
#include <set>

bool verify_row( const std::vector<int>& row )
{
    std::set<int> unique ;
    for( int v : row )
        if( v != 0 && unique.insert(v).second == false ) return false ; // duplicate non-zero value in row

    return true ;
}

bool verify_col( const std::vector< std::vector<int> >& matrix, std::size_t col_no )
{
    std::set<int> unique ;
    for( const auto& row : matrix )
        if( col_no < row.size() && row[col_no] != 0 && unique.insert( row[col_no] ).second == false ) return false ;

    return true ;
}

bool verify_values( const std::vector< std::vector<int> >& matrix )
{
    const std::size_t n = matrix.size() ;

    for( const auto& row : matrix )
    {
        if( row.size() != n ) return false ; // not a square matrix
        for( int v : row ) if( v < 0 || v > int(n) ) return false ; // value not in [0,n]
    }

    return true ;
}

bool verify( const std::vector< std::vector<int> >& matrix )
{
    if( !verify_values(matrix) ) return false ;

    for( const auto& row : matrix ) if( !verify_row(row) ) return false ;

    for( std::size_t col_no = 0 ; col_no < matrix.front().size() ; ++col_no )
        if( !verify_col( matrix, col_no ) ) return false ;

    return true ;
}

int main()
{
    std::cout << std::boolalpha
              << verify( { { 1, 2, 3 }, { 3, 1, 2 }, { 0, 0, 0 } } ) << '\n' // true
              << verify( { { 0, 0, 0 }, { 1, 2, 3 }, { 0, 2, 1 } } ) << '\n' ; // false
}

http://coliru.stacked-crooked.com/a/7f281bf2ff5e941e
coder777 (8439)
You don't need another container for colums (if the first dimension is column):
1
2
3
4
5
6
7
8
 
     for(int i = 0; i < n; ++i)
     {	
            for(int j = 0; j < n; ++j) 
            {
            	if(std::find(B[i].begin(), B[i].begin() + j, B[i][j]) != (B[i].begin() + j))
            	  return false;
            }
     }
For the rows you cannot use find() because that wouldn't be continuous. You'd need a third loop like

for(int k = 0; k < j; ++k)

In any case you can (and should) return false; as soon the first duplicate is found.
sangi89 (6)

#include <iostream>
#include <vector>
#include <set>

bool verify_row( const std::vector<int>& row )
{
std::set<int> unique ;
for( int v : row )
if( v != 0 && unique.insert(v).second == false ) return false ; // duplicate non-zero value in row

return true ;
}

bool verify_col( const std::vector< std::vector<int> >& matrix, std::size_t col_no )
{
std::set<int> unique ;
for( const auto& row : matrix )
if( col_no < row.size() && row[col_no] != 0 && unique.insert( row[col_no] ).second == false ) return false ;

return true ;

can it woork with dev++?
sangi89 (6)
You don't need another container for colums (if the first dimension is column):

it's hard to me
JLBorges (13770)
> can it woork with dev++?

It is C++11. Should work with a current version of Dev C++.

For instance, Orwel Dev C++ http://sourceforge.net/projects/orwelldevcpp/files/Setup%20Releases/Dev-Cpp%205.11%20TDM-GCC%204.9.2%20Setup.exe/download

To enable C++11: http://www.cplusplus.com/doc/tutorial/introduction/devcpp/
sangi89 (6)
It is C++11. Should work with a current version of Dev C++.

For instance, Orwel Dev C++ http://sourceforge.net/projects/orwelldevcpp/files/Setup%20Releases/Dev-Cpp%205.11%20TDM-GCC%204.9.2%20Setup.exe/download

To enable C++11: http://www.cplusplus.com/doc/tutorial/introduction/devcpp/


ok thank you , I'm trying to understand the code written by you
Topic archived. No new replies allowed.