C++矢量旋轉所有組合

我想查找給定矢量的所有可能的矢量旋轉組合。我的代碼在一個向量中依次找到一個特定的元素，然後圍繞這個元素進行旋轉，但是當兩個相同的元素連續出現時會失敗，如{1,1,2} 下面是代碼片段，有人可以幫我規避問題，最好通過讓我說for循環內的if else循環。C++矢量旋轉所有組合

#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 + +。

來源

2016-09-13 Akshay M

如果這不是一個家庭作業，並且您需要它作爲一個程序，請考慮[std :: next_permutation]（http：//en.cppreference。com/w/cpp/algorithm/next_permutation） –

在C++中，數組（和std :: vector）中的索引是從0開始的。 Apropos'for（int i = 1; i <= a.size（）; i ++）'and next'auto pivot = std :: find（a.begin（），a.end（），** a [i] **）;' –

@AdrianColomitchi，我覺得所有的排列和所有的旋轉是非常不同的。（即有'n'旋轉，但'n！'排列）。 –

我認爲問題在於行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位置我們並不需要找到它。雖然，因爲我們只需要迭代器，我只是迭代輸入中的每個元素並基於該元素進行旋轉。

要考慮的另一個邊界情況是每個元素都是相同的。如果矢量的所有元素都相同，則只有一個不同的旋轉。

來源

2016-09-13 23:52:33

如果需求是「全部*不同*旋轉」，則算法不會很小：考慮{0,1,0,1,0,1} - 當只有2個不同時，您將生成6。 –

的確如此。我會解決它。 –

首先，你的代碼有可能的分割故障：

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

由於std::vector指數是從0開始的，i = a.size()是出界。

對於實際問題：請注意，如果你只需要不同的旋轉，你只需要旋轉初始向量直到重複它自己的點 - 那將是它的週期，從那一刻起，就不會有新的區別了旋轉。

這段時間可能是1到a.size()之間的任何值，它總是存在以至於它應該是你的停止狀態。

可能的算法將是

使初始向量a
推b的臨時副本b到所得的載體
旋轉b由1
比較b到a。如果相等，則返回你得到的載體，否則返回到步驟2

向量比較（最後一步）是有些計算繁重的，並且可以被優化，例如期間將永遠是a.size()的除數，因此您可以跳過基於此的一些步驟。

至少對於處理實際旋轉的對象，您也可能希望切換到更多旋轉友好的數據結構，如std::list或std::deque。

來源

2016-09-14 01:08:01 Ap31

「，例如句號永遠是a.size（）的一個除數，所以你可以跳過一些基於此的步驟。」 +輝煌 –

C++矢量旋轉所有組合

回答

相關問題