資料結構
網路
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+ 檢視
廣告