Index filter

[newuser12]

int n[5][5][5] = {0}; //initializing all my values to zero

//setting values of n i'm interested in
// This are just example values I actually have a lot of n and I don't necessarily know the indexes until I look at the values.
n[1][2][0] = 3;
n[2][0][2] = 4;
n[2][2][2] = 5;
n[3][0][4] = 6;

What I want to do is filter only values that do not share any index. for example 3 and 4 do not share any index while (4 & 5),(3 & 5),(4 & 6) etc do. so how can i write a general code that goes through all indexes and output only 3 & 6 (no shared index)

Thanks

[Marcus Aseth]

like this maybe?

	for (size_t A = 0; A < 5; A++)
	{

		for (size_t B = 0; B < 5; B++)
		{

			for (size_t C = 0; C < 5; C++)
			{
				if (C == B || C == A || B == C)
				{
					continue;
				}
				else
				{
					//store n[A][B][C] value in another container of "good" values
				}
			}
		}
	}

//Print all value in the "good" container 

And then you can improve it, like if(A==B) then you can already "continue;" at the B loop without need to perform 5 checks on the C that we already know will fail

Edit: ignore my reply, I thought you meant you didn't wanted values that had an index repeated within that triplet of index of that value.

[newuser12]

Thanks for your replay. yea I wanted store values that don't share any index. sorry if I wasn't clear.

[Marcus Aseth]

I may have overcomplicated it a bit, but it gets the job done.

#include <iostream>
#include <vector>
#include <memory>
#include <string>
#include <map>
#include <algorithm>
#include <sstream>
using namespace std;


bool CompareIndexes(string &lhs, string &rhs, int size = 3)
{
	stringstream first(lhs), second(rhs);
	string tempA, tempB;

	for (size_t i = 0; i < size; i++)
	{
		first >> tempA;
		second >> tempB;
		if (tempA == tempB) { return true; }
	}
	return false;
}

int main()
{

	int n[5][5][5] = { 0 };
	n[1][2][0] = 3;
	n[2][0][2] = 4;
	n[2][2][2] = 5;
	n[3][0][4] = 6;



	map<int *, string> mapped_vals;
        //SORT
	for (size_t A = 0; A < 5; A++)
	{
		for (size_t B = 0; B < 5; B++)
		{
			for (size_t C = 0; C < 5; C++)
			{
				if (n[A][B][C] != 0)//DISCARD ALL 0 VALUES
				{
					mapped_vals[&n[A][B][C]] = to_string(A) + " " + to_string(B) + " " + to_string(C);
				}
			}
		}
	}
       
        //SELECT
	vector<vector <int*>> good_vals;
	for (auto current : mapped_vals)
	{
		good_vals.push_back(vector<int*>{current.first});
		for (auto &other : mapped_vals)
		{
			bool isDuplicate = false;
			if (!CompareIndexes(current.second, other.second) && current.first != other.first)
			{
				for (size_t i = 0; i < good_vals.back().size(); i++)
				{
					if (CompareIndexes(mapped_vals[good_vals.back()[i]], other.second)) { isDuplicate = true; }
				}

				if (!isDuplicate) 
				{ 
					good_vals.back().push_back(other.first); 
				}
			}
		}
	}
      
        //PRINT
	int ID{ 1 };
	for (auto &v : good_vals)
	{
		cout << "Pair " << ID++ << ": ";
		for (auto &e : v)
		{
			cout << *e << " ";
		}
		cout << endl;
	}


	return 0;
}

Output:

Pair 1: 3 4
Pair 2: 4 3
Pair 3: 5 6
Pair 4: 6 3

As you can see Pair 4: 6 3 actually could have been Pair 4: 6 3 5 because 3 can pair with 6 and 5 can pair with 6, but as in your example, 6 3 get selected and 5 which is "incompatible" with 3 get discarded.

[newuser12]

Thanks a lot Marcus. It looks a bit advanced for me to follow but I will study each line and try to understand.
What if I had something like this:

n[1][2][0] = 3;
n[2][0][2] = 4;
n[2][1][2] = 5;
n[3][0][4] = 6;
and i want to do the same except this time the output will be like this:

pair 1: 3 4 6
pair 2: 3 5 6

Thanks again

[newuser12]

Hi Marcus,
Never mind my last question. Your code does that too.
I have two more question though.
1)
pair 1: 3 4
pair2: 4 3
Since pair1 & pair2 are the same, how can I just take one pair?

2) I still want to access the corresponding indexes for each number in each set to get other variable with those indexes. Let me explain more:

let's say I have

n[1][2][0] = 3;
n[2][0][2] = 4;
n[2][2][2] = 5;
n[3][0][4] = 6;
In addition, I have another set of data like this

z[1][2][0] = a;
z[2][0][2] = b;
z[2][2][2] = v; // let's stick to a,b,v,d,f be numbers
z[3][0][4] = d;
z[0][3][4] = f
z[[][].........more such values

when I run your code, I get
set1: 3 4
set2: 4 3
set3: 5 6

now what I want to do is have output like

set1:
3 a because a = z[1][2][0] & 3= n[1][2][0]
4 b because b = z[2][0][2] & 4 = n[2][0][2] ....etc..
set2
the same....

I appreciate the help

[Marcus Aseth]

Answer 1): Those pair stored in "vector<vector <int*>> good_vals" are nothing else than pointer to int inside the array n, therefore they store an address. If you where to print them without the dereference using this call

 //PRINT
	int ID{ 1 };
	for (auto &v : good_vals)
	{
		cout << "Pair " << ID++ << ": ";
		for (auto &e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

then you would get something like this

Pair 1: 012FFC70 012FFCB4
Pair 2: 012FFCB4 012FFC70

Now you can easily see we have 2 address that are the same, therefore you could have a loop that check each vector<int*> inside good_vals against each other vector<int*> of the same size() . To make your life easier, you also want to sort the pointers first, so 3-4 actually appear twice in that exact order (not sure if matters).
Example:

	//SORT
	for (auto &v : good_vals)
	{
		sort(v.begin(), v.end());
	}
	//ReMOVE DUPLICATES
	for (size_t currentV = 0; currentV < good_vals.size(); currentV++)
	{
		for (size_t otherV = 0; otherV < good_vals.size(); otherV++)
		{
			//Don't check against itself
			if (&good_vals[currentV] == &good_vals[otherV])
			{
				continue;
			}
			// == should check for equal size and equal elements inside the vectors
			if (good_vals[currentV] == good_vals[otherV])
			{
				good_vals.erase(good_vals.begin() + otherV);
			}

		}
	}

If you run that before the print, a pair of 3-4 will be gone.

Answer 2) Just pretty much the same thing from my previous example, but maybe instead of storing in a vector<vector<int*>> you use a map<vector<int*>, vector<string>> and this has a vector<string> inside because you'll keep the string with the 3 index for each element,maybe even better if you build a struct that associate the pointer and the string into a single object , so in the "//SELECT" phase I show you yesterday you also store the string generated from

mapped_vals[&n[A][B][C]] = to_string(A) + " " + to_string(B) + " " + to_string(C);

for each number in the pair , so basically you end up with a second "mapped_vals" kind of structure that hold the good vals pairs and all the string representing their indexes.

So now you only need a stringstream to extract the 3 pieces of information into 3 strings and convert them to int using std::stoi() and you use this A B C ints to access your other array in a loop.
Well, if I knew this was the thing you wanted to do, probably we could just have a struct storing the 3 indexes int in the beggining, without this super weird string workaround... xD

[Marcus Aseth]

Like this, though probably can be done in a less complex way:

#include <iostream>
#include <vector>
#include <memory>
#include <string>
#include <map>
#include <algorithm>
#include <sstream>
#include <functional>
using namespace std;


struct Element
{
	Element(unsigned a, unsigned b, unsigned c, int *p) :A{ a }, B{ b }, C{ c }, ptr(p){}

	bool operator<(const Element &rhs) { return ptr < rhs.ptr; }
	bool operator>(const Element &rhs) { return ptr > rhs.ptr; }
	//Data
	int *ptr;
	unsigned A, B, C;
};

bool operator==(const Element &lhs, const Element &rhs)
{
	return (lhs.ptr == rhs.ptr && lhs.A == rhs.A && lhs.B == rhs.B && lhs.C == rhs.C);
}
bool operator!=(const Element &lhs, const Element &rhs)
{
	return !(lhs == rhs);
}
bool ShareIndex(Element &lhs, Element &rhs)
{
	return (lhs.A == rhs.A || lhs.B == rhs.B || lhs.C == rhs.C);
}

int main()
{
	int n[5][5][5] = { 0 };
	n[1][2][0] = 3;
	n[2][0][2] = 4;
	n[2][2][2] = 5;
	n[3][0][4] = 6;

	char z[5][5][5] = { '0' };
	z[1][2][0] = 'a';
	z[2][0][2] = 'b';
	z[2][2][2] = 'v';
	z[3][0][4] = 'd';
	z[0][3][4] = 'f';

	vector<Element> vals;
	for (size_t A = 0; A < 5; A++)
	{
		for (size_t B = 0; B < 5; B++)
		{
			for (size_t C = 0; C < 5; C++)
			{
				if (n[A][B][C] != 0)
				{
					vals.push_back(std::move(Element(A, B, C, &n[A][B][C])));
				}
			}
		}
	}

	vector<vector<Element>> good_vals;
	for (auto &currentE : vals)
	{
		good_vals.push_back(vector<Element>{ currentE });
		for (auto &otherE : vals)
		{
			bool hasCommonIndex = false;
			if (!ShareIndex(currentE, otherE) && currentE != otherE)
			{
				for (size_t i = 0; i < good_vals.back().size(); i++)
				{
					if (ShareIndex(otherE, good_vals.back()[i])) { hasCommonIndex = true; }
				}
				if (!hasCommonIndex)
				{
					good_vals.back().push_back(otherE);
				}
			}
		}
		if (good_vals.back().size() == 1) { good_vals.pop_back(); }
	}

	//SORT
	for (auto &v : good_vals)
	{
		sort(v.begin(), v.end());
	}
	//REMOVE DUPLICATES
	for (size_t currentV = 0; currentV < good_vals.size(); currentV++)
	{
		for (size_t otherV = 0; otherV < good_vals.size(); otherV++)
		{
			//Don't check against itself
			if (&good_vals[currentV] == &good_vals[otherV])
			{
				continue;
			}
			// == should check for equal size and equal elements inside the vectors
			if (good_vals[currentV] == good_vals[otherV])
			{
				good_vals.erase(good_vals.begin() + otherV);
			}
		}
	}

	//PRINT
	int ID{ 1 };
	for (auto &v : good_vals)
	{
		cout << "Pair " << ID++ << ": ";
		for (auto &e : v)
		{
			cout << n[e.A][e.B][e.C] << " ";
			cout << z[e.A][e.B][e.C] << "| ";
		}
		cout << endl;
	}

	return 0;
}

Output:

Pair 1: 3 a| 4 b|
Pair 2: 3 a| 6 d|
Pair 3: 5 v| 6 d|

[newuser12]

Thanks a lot Marcus. That works perfectly.

1) On my laptop (ubuntu 16) with g++ version 5+ I have to use g++ -std=c++11 test.cxx -o test or g++
-std=c++0x test.cxx -o test to compile.
2) But I want to run job on a server (redhat) with g++ 4.4.7 but I can't compile. g++ test.cxx -o test will give the following error

test.cc: In constructor ‘Element::Element(unsigned int, unsigned int, unsigned int, int*)’:
test.cc:14: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x
test.cc:14: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x
test.cc:14: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x
test.cc: In function ‘int main()’:
test.cc:51: error: ‘move’ is not a member of ‘std’
test.cc:57: error: ‘good_vals’ was not declared in this scope
test.cc:57: error: ‘>>’ should be ‘> >’ within a nested template argument list
test.cc:58: error: expected initializer before ‘:’ token
test.cc:125: error: expected primary-expression at end of input
test.cc:125: error: expected ‘;’ at end of input
test.cc:125: error: expected primary-expression at end of input
test.cc:125: error: expected ‘)’ at end of input
test.cc:125: error: expected statement at end of input
test.cc:125: error: expected ‘}’ at end of input

I tried g++
-std=c++0x test.cxx -o test and got the following error.

expected initializer before ‘:’ token
error: expected primary-expression at end of input
error: expected ‘;’ at end of input
error: expected primary-expression at end of input
error: expected ‘)’ at end of input
error: expected statement at end of input
error: expected ‘}’ at end of input

what should I change or include to compile successfully?

Thanks

[Marcus Aseth]

no idea, can't help with that :\
Maybe try to remove the braced initializer list I used all over the place, like in
vector<Element>{ currentE }
and replace with ()
And also try to get rid of
std::move()

Why do you need this code for anyway?

[newuser12]

I needed this code for educational purpose. I wanted to use your code as example in order to write my own and incorporate it into my original code. I needed to see if it compiles on server I run my scripts on.

[Marcus Aseth]

Well, then I hope someone else posts an example, all my code is known for often doing the simplest things in the hardest ways xD

[newuser12]

Thanks. I figured the problem is with the keyword auto like in:

for (auto &currentE : vals)
This works only for c++11 (g++ 4.6 and up versions). I have to find another way to compile with g++ 4.4.

[mbozzi]

It's a compiler support problem. C++11 is supported since G++ 4.7. No braced init lists are available in G++'s "C++0x" version, nor is move.

I edited Markus Aseth's code to compile with C++03. I didn't refactor it at all, just made the mechanical changes to get it to compile.
http://cpp.sh/2vcxx

In general, you are trying to solve an exact cover problem. The solutions are the sets of entries which
-- Have a value
-- Do not share any corresponding indices. (If I understand the problem correctly).
By "sets", I mean "sets" as in the mathematical object.
There are algorithms to quickly solve this sort of problem (e.g., https://arxiv.org/pdf/cs/0011047v1.pdf ), but in this case with small input it's possibly overkill to implement something like this. The paper is given as a reference in-case you need it.

@Marcus Aseth
P.S.: Your use of std::move on line 59 is redundant. The result of the sub-expression is already a prvalue.

Prefer emplace_back() to take advantage of perfect forwarding:

/* Instead of */
vals.push_back(std::move(Element(A, B, C, &n[A][B][C])));
/* prefer emplace_back over push_back */
vals.emplace_back(A, B, C, &n[A][B][C]);
/* ...Even in cases where you can't use perfect forwarding. */
auto elt = Element{A, B, C, &n[A][B][C]}; /* ...use elt... */
vals.emplace_back(std::move(elt)); /* Move needed since elt is an lvalue. */

[newuser12]

Thanks Mbozzi. It runs perfectly on my machine but when I try to compile it on other machine, I get the following.

In file included from /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/algorithm:62,
from test.cxx:6:
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h: In function ‘const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&) [with _Tp = Element]’:
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h:2268: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Element*, std::vector<Element, std::allocator<Element> > >, _Size = long int]’
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h:5220: instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Element*, std::vector<Element, std::allocator<Element> > >]’
test.cxx:92: instantiated from here
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h:89: error: passing ‘const Element’ as ‘this’ argument of ‘bool Element::operator<(const Element&)’ discards qualifiers
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h:90: error: passing ‘const Element’ as ‘this’ argument of ‘bool Element::operator<(const Element&)’ discards qualifiers
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h:92: error: passing ‘const Element’ as ‘this’ argument of ‘bool Element::operator<(const Element&)’ discards qualifiers
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h:96: error: passing ‘const Element’ as ‘this’ argument of ‘bool Element::operator<(const Element&)’ discards qualifiers
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/bits/stl_algo.h:98: error: passing ‘const Element’ as ‘this’ argument of ‘bool Element::operator<(const Element&)’ discards qualifiers

[keskiverto]

But I want to run job on a server (redhat) with g++ 4.4.7

That server is thus RHEL-6?

Red Hat has introduced Software Collections -- a way to install more than one version of some packages.
https://access.redhat.com/documentation/en-US/Red_Hat_Developer_Toolset/1/html/Software_Collections_Guide/sect-What_Are_Software_Collections.html
https://access.redhat.com/support/policy/updates/rhscl
https://access.redhat.com/solutions/472793
https://www.softwarecollections.org/en/

The Red Hat Developer Toolset 4.0 includes GCC 5.3


In other words it should be technically possible to install suitable g++ to the server in simple, managed fashion.

[Marcus Aseth]

thanks @mbozzi, I'll try to avoid the same mistakes in the future :)

[mbozzi]

error: passing ‘const Element’ as ‘this’ argument of ‘bool Element::operator<(const Element&)’ discards qualifiers

Huh. I made a few changes. This (still) compiles w/ C++98 and later under GCC and LLVM/Clang with strict compatibility options, but it should fix the error:

http://coliru.stacked-crooked.com/a/bf7d29901fd08852

[newuser12]

Marcus,Mbozzi and Keskiverto you guys have been incredibly helpful. Thanks for the last changes Mbozzi it is working perfectly now!

Thanks a lot again all.