Determining if two vectors contain two adjacent items the same

Question

I have a problem that concerns determining if two vectors contain two elements the same. The elements may be anywhere in the vector, but they must be adjacent.

EDITED FOR MORE EXAMPLES

For example the following two vectors, when compared, would return false.

Vector 1 = [ 0, 1, 2, 3, 4, 6 ]

Vector 2 = [ 1, 4, 2, 0, 5, 3 ]

But the following two would return true:

Vector 1 = [ 0, 1, 2, 3, 4, 5 ]

Vector 2 = [ 4, 2, 1, 5, 0, 3 ]

because the 1,2 in the first vector would correspond to the 2,1 in the second vector.

True:

Vector 1 = [ 0, 1, 2, 3, 4, 5 ]

Vector 2 = [ 1, 4, 2, 0, 5, 3 ]

{5,0} is a pair, despite looping around the vector (I originally said this was false, thanks for spotting that 'Vlad from Moscow').

True:

Vector 1 = [ 0, 1, 2, 3, 4, 5 ]

Vector 2 = [ 4, 8, 6, 2, 1, 5, 0, 3 ]

{2,1} is still a pair, even though they are not in the same position

The actual application is that I have a polygon (face) with N points stored in a vector. To determine if a set of polygons completely enclose a 3D volume, I test each face to ensure that each edge is shared by another face (where an edge is defined by two adjacent points).

Thus, Face contains a vector of pointers to Points...

std::vector<Point*> points_;

and to check if a Face is surrounded, Face contains a member function...

bool isSurrounded(std::vector<Face*> * neighbours)
{
    int count = 0;
    for(auto&& i : *neighbours)     // for each potential face
        if (i != this)              // that is not this face
            for (int j = 0; j < nPoints(); j++) // and for each point in this face
                for (int k = 0; k < i->nPoints(); k++ ) // check if the neighbour has a shared point, and that the next point (backwards or forwards) is also shared
                    if ( ( this->at(j) == i->at(k) )        // Points are the same, check the next and previous point too to make a pair
                       && (    ( this->at((j+1)%nPoints()) == i->at((k+1)%(i->nPoints())) )
                            || ( this->at((j+1)%nPoints()) == i->at((k+i->nPoints()-1)%(i->nPoints())) )))
                        { count++; }
    if (count > nPoints() - 1) // number of egdes = nPoints -1
        return true;
    else
        return false;
}

Now, obviously this code is horrible. If I come back to this in 2 weeks, I probably won't understand it. So faced with the original problem, how would you neatly check the two vectors?

Note that if you are trying to decipher the provided code. at(int) returns the Point in a face and nPoints() returns the number of points in a face.

Many thanks.

Answer 1

Here is way if your element are same set of elements then assign index for each. (Didnt mention corner cases in pseudo ) :-

for(int i=0;i<vect1.size;i++) {

   adj[vect1[i]][0] = vect1[i-1];
   adj[vect2[i]][1] = vect2[i+1];
}

for(int j=0;j<vect2.size();j++) {

    if(arr[vect2[i]][0]==(vect2[j-1] or vect[j+1]))
       return true
    if(arr[vect2[i]][1]==(vect2[j-1] or vect[j+1]))
       return true

}

Answer 2

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

using namespace std;
class AdjacentSort
{
public:
    AdjacentSort(const vector<int>& ref);
    ~AdjacentSort();

    bool operator()(int e1,int e2) const;
private:
    const vector<int>& ref_;
};

AdjacentSort::AdjacentSort(const vector<int>& ref):
    ref_(ref)
{
}

bool AdjacentSort::operator()(int e1, int e2) const
{
    auto it1 = find(ref_.begin(),ref_.end(),e1);
    auto it2 = find(ref_.begin(),ref_.end(),e2);

    return distance(it1,it2) == 1;
}

AdjacentSort::~AdjacentSort()
{
}

int main()
{
    vector<int> vec {1,2,3,4,5};
    vector<int> vec2 {1,3,5,4,2};

    AdjacentSort func(vec);
    auto it = adjacent_find(vec2.begin(),vec2.end(),func);

    cout << *it << endl;

    return 0;
}

It returns the first element where two adjacent numbers are found, else it returns the end iterator.