C++ вектор вращения все комбинации

Question

Я хочу найти все возможные комбинации вращения вектора для заданного вектора. Мой код находит определенный элемент последовательно в векторе и затем вращается вокруг него, но эта логика терпит неудачу, когда два одинаковых элемента происходят последовательно, как в {1,1,2} Ниже приведен фрагмент кода, может ли кто-нибудь помочь мне обойти это вопрос, желательно, чтобы разрешить использовать цикл if else внутри цикла for.

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

using namespace std; 
vector<vector<int> > allrot(const vector<int>& a); 

int main() 
{ 
     int myints[] = { 1, 1, 2 }; 
     std::vector<int> a (myints, myints + sizeof(myints)/sizeof(int)); 
     std::vector<vector<int> > b; 
     b = allrot(a); 
} 

vector<vector<int> > allrot(const vector<int>& a) { 
     std::vector<vector<int> > b; 
     for(int i = 1; i <= a.size(); i++) { 
       //int k; 
       //if (a[i] == a[i+1]) 
        //k = a [i+1]; 
       //else 
        //k = a[i]; 

       auto pivot = std::find(a.begin(), a.end(), a[i]); 
       std::vector<int> dest(a.size()); 
       std::rotate_copy(a.begin(), pivot, a.end(), dest.begin()); 
       for (const auto &i : dest) { 
        std::cout << i << ' '; 
       } 
       std::cout << '\n'; 
       b.push_back(dest); 
     } 
     return b; 
} 

Извинения, если вопрос выглядит наивным, я новичок в C++.

Answer 1

Я думаю, что проблема связана с линией auto pivot = std::find(a.begin(), a.end(), a[i]);. Это первый экземпляр, который имеет значение в a[i].

Вместо этого рассмотрите следующую реализацию.

vector<vector<int>> all_rot(const vector<int>& a){ 
    vector<vector<int>> b; 
    for (auto it = a.begin(); it != a.end(); ++it){ 
    vector<int> dest(a.size()); 
    dest = std::rotate_copy(a.begin(), it, a.end(), dest.begin()); 
    if (b.size() != 0 && dest == b[0]){ return b; } // checks to see if you have repetition in cycles. 
    b.push_back(dest); 
    for (const auto item& : dest){ 
     std::cout << item << " "; 
    } 
    std::cout << endl; 
    } 
    return b; 
} 

Поскольку вы знаете, что pivot (я назвал его it выше) находится в ith месте нам не нужно, чтобы найти его. Хотя, поскольку нам нужны только итераторы, я просто перебирал каждый элемент ввода и вращался на основе этого элемента.

Еще один пример края, который необходимо учитывать, когда каждый элемент является одним и тем же. Если все элементы вектора совпадают, то существует ровно 1 отличный поворот.

Answer 2

Прежде всего, ваш код имеет потенциальную ошибку сегментации:

for(int i = 1; i <= a.size(); i++) 

Поскольку индекс std::vector является 0 на основе i = a.size() находится вне границ.

За актуальный вопрос: обратите внимание, что если вы хотите только отдельные вращения, вам нужно только поворачивать начальный вектор до точки, когда он повторяется, - это будет его период, и с этого момента не будет никаких новых отличительных севообороты.

Этот период может быть от 1 до a.size(), и он всегда существует, поэтому его достижение должно быть вашим условием остановки.

Возможный алгоритм будет

• сделать временную копию b исходного вектора a
• нажимного b в результате вектора
• вращается b по 1
• сравнить b с a. Если равно, верните полученный вектор, в противном случае вернитесь к его результату, в противном случае вернитесь к шагу 2.

Сравнение в векторном сравнении (последний шаг) является несколько вычислительно тяжелым и может быть оптимизировано, например. период всегда будет делителем a.size(), поэтому вы можете пропустить некоторые шаги на этом основании.

Также вы можете переключиться на более дружественную к вращению структуру данных, такую ​​как std::list или std::deque, по крайней мере, для объекта, который обрабатывает фактические вращения.