打印给定字符串的所有排列

打印给定字符串的所有排列是回溯问题的一个示例。我们将减小子字符串的大小以解决子问题，然后再次回溯以从该部分获得另一个排列。

例如，如果字符串是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