Unique data in reverse C++

Question

Not sure how to phrase this the best way but I am wanting to get unique data in reverse. It'll be better if I give an example

If I have the data

0 1
0 3
0 4
1 0
1 2
1 5
3 0

how could I get rid of the data that is a reverse of itself? For example: 0 1 and 1 0 and I would like to get rid of 1 0 because I already saw 0 1. Another example: 0 3 and 3 0 and I would like to get rid of 3 0 because I already saw 0 3.

So the data would instead be this:

0 1
0 3
0 4
1 2
1 5

Here is the code I have for how the data is coming out.

int temp;
    int tn;
    for (int i=0; i < n-1; i++)
    {
        for (int j=0; j< 4; j++)
        {
            temp = grid[i].neighbor[j];
            tn = get_neighbor(j);

            cout << i << " " << grid[i].neighbor[j] <<endl; //index

        }

    }

Note that it is i and grid[i].neighbor[j] that are producing the two numbers.

Answer 1

If you may not to change the order of elements of the original vector then the straightforward approach is the following

std::vector<std::vector<int>> v;

int a[][2] = { { 0, 1 }, { 0, 3 }, { 0, 4 }, { 1, 0 }, { 1, 2 }, { 1, 5 }, { 3, 0 } };

std::transform( std::begin( a ), std::end( a ), std::back_inserter( v ),
                []( const int ( &row )[2] ) 
                { 
                    return std::vector<int>( std::begin( row ), std::end( row ) );
                } );

for ( const std::vector<int> &row : v )
{
    for ( int x : row ) std::cout << x << ' ';
    std::cout << std::endl;
}

std::cout << std::endl;

std::function<bool( const std::vector<int> &, const std::vector<int> & )>  identical = 
[]( const std::vector<int> &v1, const std::vector<int> &v2 )
{
    return ( v1.size() == v2.size() && v1.size() == 2 &&
        ( v1[0] == v2[0] && v1[1] == v2[1] || v1[0] == v2[1] && v1[1] == v2[0] ) );
};

auto last = v.begin();

for ( auto first = v.begin(); first != v.end(); ++first )
{
    using namespace std::placeholders;
    if ( std::find_if( v.begin(), last, std::bind( identical, _1, *first ) ) == last )
    {
        if ( first != last ) *last = *first;
        ++last;
    }
}

v.erase( last, v.end() );

for ( const std::vector<int> &row : v )
{
    for ( int x : row ) std::cout << x << ' ';
    std::cout << std::endl;
}

Of course there was no any need to define intermediate array a that to initialize the vector. You can initialize it using initializer list.

The output is

0 1
0 3
0 4
1 0
1 2
1 5
3 0

0 1
0 3
0 4
1 2
1 5

Answer 2

1) Sort the dataset

2) Check for duplicates (just normally, not in reverse)

3) Remove any duplicates found

4) Loop through and check each item against the reverse of each item (two for loops)

Steps 1/2/3 can be combined into step 4 for less iteration, or they can be seperated into a set. A set in C++ will automatically remove duplicates for steps 2 and 3 as well as sort your values and is a good chance to check out some STL stuff (Standard Template Library).

Answer 3

I have an idea on how to implement this, just for share, please do not vote down my answer..

The key point here is how to recognize two reverse pair, of course we can compare each of them, but there are surely more elegant way to do this.

If your numbers are in some fixed range integer, for example 0..10, then you can define a prime number array like this prime_arr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31], now we can see if two pairs <x. y> and <a, b> are the same or in reverse, we can just compare prime_arr[x] * prime_arr[y] and prime_arr[a] * prime_arr[b].

Oh, it is just a sample, if your number is not in fixed range, but all non negative integer, you can consider x^2 + y^2, if two pairs <x, y> and <a, b> are the same or in reverse, compare x^2 + y^2 and a^2 + b^2.

Here is a demo implementation, hope it is useful for you...

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<pair<int, int>> v = { { 0, 1 }, { 0, 3 }, { 0, 4 },
        { 1, 0 }, { 1, 2 }, { 1, 5 }, { 3, 0 }};
    vector<int> flagv;
    for (auto p : v) {
        int flag = p.first * p.first + p.second * p.second;
        if (find(flagv.begin(), flagv.end(), flag) == flagv.end()) {
            cout << p.first << " " << p.second << endl;
            flagv.push_back(flag);
        }
    }
    return 0;
}

Just one look for scanning the pair list..

Anyway, it is an advice from me, and limited usage(non negative integer), but you can figure out more proper computation to recognize two pair whether they are in reverse or the same.

Answer 4

just use comparator that normalize pair:

typedef std::pair<int,int> ipair;
typedef std::vector<ipair> ipvector;

inline
ipair norm( const ipair &p )
{
    return ipair{ std::min( p.first, p.second ), std::max( p.first, p.second ) };
}

struct norm_cmp {
    bool operator()( const ipair &p1, const ipair &p2 )
    {
        return norm( p1 ) < norm( p2 );
    }
};

int main()
{
    ipvector v = { { 0, 1 }, { 0, 3 }, { 0, 4 },
                { 1, 0 }, { 1, 2 }, { 1, 5 }, { 3, 0 }};

    std::set<ipair, norm_cmp> s( v.begin(), v.end() );
    for( const ipair &p : s )
        std::cout << '{' << p.first << ',' << p.second << '}' << std::endl;
}

run on ideone