資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究列印給定字串的所有排列
列印給定字串的所有排列是回溯問題的示例。我們將減小子字串的大小以解決子問題，然後再回溯以從該部分中獲得另一個排列。
例如，如果字串為 ABC，則所有排列將為 ABC、ACB、BAC、BCA、CAB、CBA。
此演算法的複雜性為 O(n!)。這是一個非常高的複雜性。當字串大小增加時，完成任務所需的時間就更長。
輸入和輸出
Input: A string “ABC” Output: All permutations of ABC is: ABC ACB BAC BCA CBA CAB
演算法
stringPermutation(str, left, right)
輸入：字元的字串和左右索引。
輸出：列印字串的所有排列。
Begin if left = right, then display str else for i := left to right, do swap str[left] and str[i] stringPermutation(str, left+1, right) swap str[left] and str[i] //for backtrack done End
示例
#include<iostream>
using namespace std;
void stringPermutation(string str, int left, int right) {
if(left == right)
cout << str << endl;
else {
for(int i = left; i<= right; i++) {
swap(str[left], str[i]);
stringPermutation(str, left + 1, right);
swap(str[left], str[i]); //swap back for backtracking
}
}
}
int main() {
string str = "ABC";
cout << "All permutations of " << str << " is: " <<endl<<endl;
stringPermutation(str, 0, str.size()-1);
}
輸出
All permutations of ABC is: ABC ACB BAC BCA CBA CAB
更新於： 2020 年 6 月 17 日
2K+ 瀏覽量
廣告