C++ベクトル回転すべての組み合わせ

Question

特定のベクトルに対して可能なすべてのベクトル回転の組み合わせを検索したい。私のコードは、特定の要素をベクトル内で逐次見つけ、その周りを回転しますが、この論理は{1,1,2}のように連続して発生すると失敗します 以下はコードスニペットです。問題は、できれば、私のforループの中にif elseループと言うことができます。

#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インデックスがi = a.size()が範囲外である、0ベースであるため。

実際の質問の場合：別個の回転のみを必要とする場合は、それ自体を繰り返す点まで初期ベクトルを回転する必要があることに注意してください。それは周期であり、その点からは新しい個別の回転。

この期間は1からa.size()までの任意の値にすることができ、それが到達すると常に到達して停止状態になるはずです。

可能なアルゴリズムが

• 初期ベクトルの一時的なコピーbを行うa
• プッシュb
得られたベクターになり、1
• によってbがaにbを比較回転します。等しい場合は結果のベクトルを返し、そうでない場合は手順2に戻ります。

ベクターの比較（最後のステップ）はやや計算量が多く、最適化することができます。期間は常にa.size()の約数になるので、それに基づいていくつかの手順をスキップすることができます。

また、少なくとも実際の回転を処理するオブジェクトの場合、std::listやstd::dequeなど、より多くのローテーションフレンドリなデータ構造に切り替えることもできます。