a469 - 10063 - Knuth's Permutation

🔗 前往 ZeroJudge 原題

題目描述

題目要求生成給定字符串的所有排列，並按照特定的順序輸出。這個順序是通過遞迴地插入字符來決定的，每次插入字符時，嘗試將其插入到所有可能的位置。

解題思路

使用遞迴（DFS）來生成所有排列。遞迴函數 dfs 接受當前已生成的字符串 tmp 和剩餘未處理字符的起始索引 s 作為參數。

1. 基本情況：如果 s 等於字符串的長度，則表示已經生成了一個完整的排列，將其輸出。
2. 遞迴步驟：
   • 將當前字符 in[s] 添加到 tmp 的最前面。
   • 從 i = 1 到 s + 1 遍歷所有可能的插入位置。
   • 在每次迭代中，遞迴調用 dfs，生成下一個排列。
   • 在遞迴調用返回後，將 tmp[i] 和 tmp[i-1] 交換，以恢復原始狀態，以便嘗試下一個插入位置。

複雜度分析

• 時間複雜度: O(n!)，其中 n 是字符串的長度。因為需要生成所有可能的排列。
• 空間複雜度: O(n)，主要用於遞迴調用堆疊和存儲當前排列的字符串。

程式碼

#include <iostream>
using namespace std;
string in;
int il;
inline void dfs(int s,string tmp){
	if(s==il){
		cout << tmp << "\n";
		return;
	}
	tmp=in[s]+tmp;
	for(int i=1;i<=s+1;++i){
		dfs(s+1,tmp);
		swap(tmp[i],tmp[i-1]);
	}
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int s=0;
	while(cin >> in){
		if(s)cout << "\n";
		s=1;
		il=in.length();
		string st;
		st+=in[0];
		dfs(1,st);
	}
}