CODEWITHSUNDEEP
c++algorithmpermutation
Wallace Mogerty
Wallace Mogerty

Reputation: 335

Generate All Possible Permutations of Vector of Objects

Given a vector of coordinates corresponding to city locations on a grid, how can I generate every permutation of these point objects? I suspect there is a problem with using a user-defined class (Point, in my case) with the predefined function next_permutation.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Point
{
public:
double x, y;
Point(int x, int y);
friend ostream& operator<< (ostream &out, const Point &p);
};

Point::Point(int xCoord, int yCoord)
{
x = xCoord;
y = yCoord;
}

ostream& operator<< (ostream &out, const Point &p)
{
out << "(" << p.x << ", " << p.y << ")";
return out;
}

int main()
{
vector<Point> points = { {3,5}, {10,1}, {2,6} };

do
{
    for (Point pt : points)
    {
        cout << pt << " ";
    }
    cout << endl;
} while (next_permutation(points.begin(), points.end()));
}

Upvotes: 1

Views: 2312

Answers (2)

tinstaafl
tinstaafl

Reputation: 6948

A couple of things,

first to use next_permutations the container must be sorted.

second to compare two custom objects for sort and next_permutations, you need to overload the < operator.

something like this should work:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Coords
{
 public:
    int x = 0;
    int y = 0;
    //This uses a simple lexicographical ordering, modify to suit your needs.
    bool operator <( const Coords& rhs )
    {
        if ( x == rhs.x )
        {
            return y < rhs.y;
        }
        else
        {
            return x < rhs.x;
        }
    }
};
vector<vector<Coords>> GetPermutaions( vector<Coords>& vec )
{
    vector < vector<Coords>> outVal ;
    //if you can guarantee vec will be sorted this can be omitted
    sort( vec.begin() , vec.end() );
    do
    {
        outVal.emplace_back( vec );
    } while ( next_permutation( vec.begin() , vec.end() ) );
    return outVal;
}

One thing to remember, this function will leave vec in a sorted state. If you need the original state, create a copy of vec to do the permutations.

Upvotes: 1

MSD
MSD

Reputation: 1407

Ex snippet:

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

int main()
{
      typedef std::vector<int> V; //<or_any_class>
      V v;

      for(int i=1;i<=5;++i)
        v.push_back(i*10);

      do{
         std::cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<" "<<v[3]<<" "<<v[4]<<std::endl;
        }while(std::next_permutation(v.begin(),v.end()));
      return 0;
    }

Upvotes: 1

Related Questions