C++

Forum

 
 
Problem with sorting elements from 2D matrix

csi1490 (14)
Hello friends, I'm trying to extract from one matrix : m[21][3] to another a[?][3] all unique elements.
The matrix I have is :
0 0 0
0 0 1
0 1 0
0 1 1
1 1 0
1 1 1
0 0 0
0 0 1
1 1 0
1 1 1
1 1 1
1 1 1
0 0 1
0 0 0
0 1 0
0 1 1
0 1 0
0 1 1
1 1 0
0 0 0
0 1 1
The matrix I need to get:
0 0 0
0 0 1
0 1 0
0 1 1
1 1 0
1 1 1


If you have some ideas I would be very thankful. Thank you in advance.
cubancigar11 (1)
Store everything in a set. Since your matrix consists of only 1s and 0s, you are in luck as you can create a very efficient hash function which converts each row to a single byte.

For example, here is a sample 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
 
#include <iostream>
#include <set>
#include <bitset>
#include <vector>
#include <algorithm>

using namespace std;

struct Row
{
	Row(const int _row_num, const int _val) :
		row_num(_row_num), val(_val)
	{
	}

	int row_num;
	int val;
};

bool operator<(const Row & _row1, const Row & _row2)
{
	return _row1.val < _row2.val;
}
	
ostream& operator<<(ostream & _out, const Row & _row)
{
	_out << _row.row_num << ": ";
	_out << (0x00000001 & (_row.val >> 2));
	_out << (0x00000001 & (_row.val >> 1));
	_out << (0x00000001 & (_row.val >> 0));
	return _out;
}

bool comp_row(const Row & _row1, const Row & _row2)
{
	return _row1.row_num < _row2.row_num;
}

int hash_func(const int _v1, const int _v2, const int _v3)
{
	bitset<3> b(0);
	b.set(2, _v1);
	b.set(1, _v2);
	b.set(0, _v3);
	return b.to_ulong();
}

int main()
{
	set<Row> s;
	s.insert(Row(0, hash_func(0, 0, 0)));
	s.insert(Row(1, hash_func(1, 1, 1)));
	s.insert(Row(2, hash_func(0, 0, 0)));
	s.insert(Row(3, hash_func(0, 0, 1)));
	s.insert(Row(4, hash_func(1, 1, 0)));
	s.insert(Row(5, hash_func(1, 1, 1)));
	s.insert(Row(6, hash_func(0, 0, 1)));
	s.insert(Row(7, hash_func(0, 1, 0)));
	s.insert(Row(8, hash_func(0, 1, 1)));
	s.insert(Row(9, hash_func(1, 1, 0)));
	s.insert(Row(10, hash_func(1, 1, 1)));
	s.insert(Row(11, hash_func(1, 1, 1)));
	s.insert(Row(12, hash_func(0, 0, 1)));
	s.insert(Row(13, hash_func(0, 0, 0)));
	s.insert(Row(14, hash_func(0, 1, 0)));
	s.insert(Row(15, hash_func(0, 1, 1)));
	s.insert(Row(16, hash_func(0, 1, 0)));
	s.insert(Row(17, hash_func(0, 1, 1)));
	s.insert(Row(18, hash_func(1, 1, 0)));
	s.insert(Row(19, hash_func(0, 0, 0)));
	s.insert(Row(20, hash_func(0, 1, 1)));
	vector<Row> v;
	for (set<Row>::const_iterator it = s.begin(); it != s.end(); ++it)
	{
		v.push_back(*it);
	}
	sort(v.begin(), v.end(), comp_row);
	for (vector<Row>::const_iterator it = v.begin(); it != v.end(); ++it)
	{
		cout << *it << "\n";
	}
	return 0;
}

Output:
0: 000
1: 111
3: 001
4: 110
7: 010
8: 011

It is not as optimized as I would have liked, since we are copying stuff from std::set to std::vector just cause set cannot be sorted, but you get the idea.
Last edited on
Topic archived. No new replies allowed.