Saya memiliki vektor vector<Points>list_of_points;
yang berisi titik A B C D A. Saya ingin mencari semua kemungkinan kombinasi vektor yang menjaga dua elemen terluar di tempat yang sama. Misalnya, A B C D A -- A B D C A -- A C B D A -- A C D B A -- A D B C A -- A D C B A. Ada saran bagaimana saya bisa melakukan ini?
Saya melakukan ini karena setiap titik memiliki koordinat x,y. Saya mencoba mencari jarak terpendek untuk pergi ke semua elemen dan kembali ke elemen aslinya. Saya berpikir untuk menetapkan jarak minimum sama dengan kombinasi pertama A B C D A, dan membandingkan semua kombinasi lainnya
//pseudocode
min distance = distance of A B C D A
while(there are still combinations){
find another combinations of the vector.
if that distance is smaller than min distance, make it the new min distance
save the path in a vector
}
Jika diperlukan, inilah implementasi saya
#include <cmath>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
class Point
{
private:
int m_x;
int m_y;
string m_name;
public:
Point(int x, int y, string name)
: m_x(x), m_y(y), m_name(name)
{}
Point(){};
int getX() const {return m_x;}
void setX(int x) {m_x=x;}
int getY() const {return m_y;}
void setY(int y) {m_y=y;}
string getName() const {return m_name;}
float getDistance(Point &other);
string toString() const;
void printPoint() const;
// used for printing Point using << operator. For example:
// Point p(1,2,"A");
// cout << p << endl;
friend ostream& operator<<(ostream &os, const Point &p);
};
class ListOfPoints
{
private:
int elements;
public:
vector<Point>sorted_list;
vector<Point>unsorted_list;
void Unsorted_add(Point &newPt);
void Sorted_add(Point &newPt);
void Create_unsorted();
void Sort_list();
void set_elements(int n);
int get_elements();
ListOfPoints();
// adds a new point to the end of the list
void addPoint(Point &newPt);
// prints the list of points
void printList() const;
// draws the points
void draw() const;
};
string Point::toString() const{
// examples how to create string from small parts
string str(m_name);
str += " = (";
str += std::to_string(m_x);
str.append(",").append(std::to_string(m_y)).append(")");
return str;
}
float Point::getDistance(Point &other){
float x1 = float(this->getX());
cout << "this->x = "<< this->getX() <<endl;
cout << "this->y = "<<this->getY() <<endl;
float y1 = float(this->getY());
float x2 = float(other.getX());
float y2 = float(other.getY());
//cout << "x = " << x2 << endl;
//cout << "y = " << y2 << endl;
float dist = sqrt( pow(x2-x1,2) + pow(y2-y1,2) );
cout << "dist = " << dist << endl;
return dist;
}
void Point::printPoint() const{
cout << toString() << endl;
}
// used for printing Point using << operator.
// For example, the following code will work
// Point origin(0,0,'O');
// cout << origin;
ostream& operator<<(ostream &os, const Point &p) {
return os << p.toString();
}
ListOfPoints::ListOfPoints() {
}
void ListOfPoints::Sorted_add(Point &newPt) {
sorted_list.push_back(newPt);
}
void ListOfPoints::Unsorted_add(Point &newPt) {
unsorted_list.push_back(newPt);
}
void ListOfPoints::set_elements(int n){
elements = n;
}
int ListOfPoints::get_elements(){
return this->elements;
}
void ListOfPoints::Create_unsorted(){
int x;
int y;
string name;
cout << "Enter the Number of elements" << endl;
cin >> elements;
for(int i = 0; i<elements; i++){
cout << "Enter the name of the element: " << endl;
cin >> name;
cout <<"Enter the x value" << endl;
cin >> x;
cout <<"Enter they y vlaue" << endl;
cin >> y;
Point p(x,y,name);
unsorted_list.push_back(p);
}
cout << elements << endl;
return;
}