ค้นหาการรวมกันขององค์ประกอบตรงกลางในเวกเตอร์

ฉันมีเวกเตอร์ vector<Points>list_of_points; ที่มีจุด A B C D A ฉันต้องการค้นหาชุดค่าผสมที่เป็นไปได้ทั้งหมดของเวกเตอร์โดยทำให้องค์ประกอบด้านนอกทั้งสองอยู่ในตำแหน่งเดียวกัน ตัวอย่างเช่น 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 มีคำแนะนำว่าจะทำอย่างไร

ฉันทำสิ่งนี้เพราะแต่ละจุดมีพิกัด x,y ฉันกำลังพยายามหาระยะทางที่สั้นที่สุดเพื่อไปยังองค์ประกอบทั้งหมดและกลับสู่องค์ประกอบดั้งเดิม ฉันกำลังคิดที่จะตั้งค่าระยะห่างขั้นต่ำเท่ากับชุดค่าผสมแรก A B C D A และเปรียบเทียบชุดค่าผสมอื่นๆ ทั้งหมด

//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
}

หากจำเป็น นี่คือการดำเนินการของฉัน

#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;
}

c++ algorithm vector traveling-salesman
person CS_12319    schedule 06.12.2020    source แหล่งที่มา
comment
จะมีจำนวนผลลัพธ์ nPn : โดยที่ n คือขนาดของเวกเตอร์ - 2 และ nPn หมายถึงการเรียงสับเปลี่ยน คุณอาจต้องหาวิธีจำกัดมัน ไม่เช่นนั้นก็จะได้ผลลัพธ์มากมาย   -  person WARhead    schedule 06.12.2020
comment
ไลบรารีมาตรฐานมีฟังก์ชันสำหรับการค้นหาการเรียงสับเปลี่ยนที่เรียกว่า std::next_permutation คุณสามารถให้ตัววนซ้ำกับองค์ประกอบที่สองและสุดท้ายเป็นช่วงที่จะเปลี่ยนรูป จากนั้นจึงเพิ่มค่าแรกและค่าสุดท้ายด้วยตนเอง   -  person nick    schedule 06.12.2020
comment
softwareengineering.stackexchange.com/questions/315836/ ดูสิ่งนี้เพื่อหาอัลกอริธึมที่ดีกว่า เนื่องจากการบังคับแบบเดรัจฉานอาจไม่สามารถทำได้สำหรับเวกเตอร์ที่ยาวกว่า การบังคับแบบเดรัจฉานมีความซับซ้อน O(n!)   -  person WARhead    schedule 06.12.2020

คำตอบ (1)


arrow_upward
1
arrow_downward

ตามคำอธิบายของคุณ โปรแกรมต่อไปนี้จะสาธิตสิ่งที่คุณพยายามทำให้สำเร็จโดยใช้ std::next_permutation:

#include <algorithm>
#include <string>
#include <iostream>

int main()
{
    std::string test = "ABCDA";

    // sort the items after the beginning and before the end of the sequence
    std::sort(test.begin() + 1, std::prev(test.end()));
    do
    {
        std::cout << test << "\n";
      // permute the middle elements
    } while (std::next_permutation(test.begin() + 1, std::prev(test.end())));
}

เอาท์พุท:

ABCDA
ABDCA
ACBDA
ACDBA
ADBCA
ADCBA

หากต้องการขยายสิ่งนี้ไปยังคลาส Point คุณจะต้องเรียงลำดับจุดกึ่งกลางด้วยวิธีใดวิธีหนึ่ง จากนั้นจึงใช้ตรรกะเดียวกันโดยใช้ std::next_permutation

นี่เป็นตัวอย่างเล็กๆ น้อยๆ:

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

struct Point
{
    int m_x;
    int m_y;
    int get_x() const { return m_x; }
    int get_y() const { return m_y; }
    Point(int x = 0, int y = 0) : m_x(x), m_y(y) {}
};
    
int main()
{
    std::vector<Point> test = {{0,0},{1,2},{2,1},{3,6},{2,7},{10,10}};
    std::vector<std::vector<Point>> results;
    auto sorter = [](const Point& p1, const Point& p2) { return std::tie(p1.m_x, p1.m_y) < std::tie(p2.m_x, p2.m_y); };
    
    // sort the items after the beginning and before the end of the sequence
    std::sort(test.begin() + 1, std::prev(test.end()), sorter);
    do
    {
        results.push_back(test);
    } while (std::next_permutation(test.begin() + 1, std::prev(test.end()), sorter));
    
    for (auto& r : results)
    {
        for (auto& p : r)
           std::cout << "{" << p.get_x() << "," << p.get_y() << ") ";
        std::cout << "\n";
    }
}

เอาท์พุท:

{0,0) {1,2) {2,1) {2,7) {3,6) {10,10) 
{0,0) {1,2) {2,1) {3,6) {2,7) {10,10) 
{0,0) {1,2) {2,7) {2,1) {3,6) {10,10) 
{0,0) {1,2) {2,7) {3,6) {2,1) {10,10) 
{0,0) {1,2) {3,6) {2,1) {2,7) {10,10) 
{0,0) {1,2) {3,6) {2,7) {2,1) {10,10) 
{0,0) {2,1) {1,2) {2,7) {3,6) {10,10) 
{0,0) {2,1) {1,2) {3,6) {2,7) {10,10) 
{0,0) {2,1) {2,7) {1,2) {3,6) {10,10) 
{0,0) {2,1) {2,7) {3,6) {1,2) {10,10) 
{0,0) {2,1) {3,6) {1,2) {2,7) {10,10) 
{0,0) {2,1) {3,6) {2,7) {1,2) {10,10) 
{0,0) {2,7) {1,2) {2,1) {3,6) {10,10) 
{0,0) {2,7) {1,2) {3,6) {2,1) {10,10) 
{0,0) {2,7) {2,1) {1,2) {3,6) {10,10) 
{0,0) {2,7) {2,1) {3,6) {1,2) {10,10) 
{0,0) {2,7) {3,6) {1,2) {2,1) {10,10) 
{0,0) {2,7) {3,6) {2,1) {1,2) {10,10) 
{0,0) {3,6) {1,2) {2,1) {2,7) {10,10) 
{0,0) {3,6) {1,2) {2,7) {2,1) {10,10) 
{0,0) {3,6) {2,1) {1,2) {2,7) {10,10) 
{0,0) {3,6) {2,1) {2,7) {1,2) {10,10) 
{0,0) {3,6) {2,7) {1,2) {2,1) {10,10) 
{0,0) {3,6) {2,7) {2,1) {1,2) {10,10)

ฉันเลือกเกณฑ์การเรียงลำดับตามค่า x และ y โดยเปรียบเทียบค่า x ก่อน

person PaulMcKenzie    schedule 06.12.2020
comment
ฉันสับสนเล็กน้อย คุณหมายถึงอะไรโดยเรียงลำดับ ฉันจะรู้ได้อย่างไรว่าต้องเรียงลำดับตามเกณฑ์ใด std::next_permuatation ไม่ต้องการเกณฑ์บางประเภทใช่ไหม ฉันพยายามและได้รับรายการข้อผิดพลาดจำนวนมาก - person CS_12319; 06.12.2020
comment
เรียงตาม x แล้วก็ y ดูการแก้ไข - person PaulMcKenzie; 06.12.2020