使用STL實作給定字串的C++全排列

當給定字串的字元以任意形式重新排列時，就形成了字串的排列。例如，在本教程中，我們將討論如何使用C 的標準模板庫列印給定字串的所有排列

Input : s = “ADT”

Output : “ADT”, “ATD”, “DAT”, “DTA”, “TAD”, “TDA”

Explanation : In the given output as you can see all the string are made up of same three character present in our string and are just rearranged thus they fit in the definition of a permutation of a string now there is one more thing to note these are all the permutations possible of string s.

有兩種方法可以列印給定字串的所有排列

#Rotate()

我們要使用的第一個方法是使用旋轉方法。在此方法中，我們將使用 STL 的旋轉函數，該函數用於旋轉字串，並且我們將使用遞歸來列印排列。

範例

上述方法的C 程式碼

#include<bits/stdc++.h>
using namespace std;
void permutations(string s, string ans){
    if(s.size() == 0) {
// when our string which needs to
//be rotated becomes empty then it means
//that our permutation is stored in ans
        cout << ans << "\n";
        return ;
    }
    for(int i = 0; i < s.size(); i++){
        permutations(s.substr(1), ans + s[0]);
        // we are adding the
        // first character in our ans
        // passing all elements from index 1 in our
        // rotate string for next function.
        rotate(s.begin(), s.begin()+1, s.end());
        //rotating such that our second element becomes first
    }
}
int main(){
    string s = "ADT"; // given string
    permutations(s, "");
    return 0;
}

輸出

ADT
ATD
DTA
DAT
TAD
TDA

Next_Permutation

現在我們將使用STL的另一個函數，即next_Permutation，顧名思義，該函數的傳回值是該字串的下一個排列是否存在。如果不是，則傳回 false。

如您所知，此函數會檢查下一個排列；因此，我們首先需要按字典順序對字串進行排序，以便獲得所有可能的排列。

範例

上述方法的C 程式碼

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s = "ADT"; // given string
    sort(s.begin(), s.end()); // sorting the string
    do{
        cout << s << "\n"; // printing the permutations
    }while(next_permutation(s.begin(), s.end())); // till next_permutations returns false
    return 0;
}

輸出

ADT
ATD
DAT
DTA
TAD
TDA

在上面的程式中，我們對字串進行排序，然後在next_permutation 函數的幫助下，我們列印所有可能的排列。

結論

在本教程中，我們藉助 C 中的 STL 列印給定字串的所有可能排列。我們也學習了該問題的C 程式以及一些基本的STL函數及其使用。我們希望本教學對您有所幫助。

以上是使用STL實作給定字串的C++全排列的詳細內容。更多資訊請關注PHP中文網其他相關文章！