アルゴリズム練習問題53:文字列全配列問題

ソース:http://bbs.csdn.net/topics/350118968
文字列の配置.
タイトル:1文字入力
文字列、文字列内のすべての文字の配置を印刷します.
例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが出力される.
分析:これは再帰的な理解に対するプログラミング問題をよく調べています.
そのため、この1年間、大手企業の面接や筆記試験問題に頻繁に登場した.
--------------------------------------------------
この問題は確かに少し難しいですが、再帰を使うことを知っていますが、再帰はできません.
肝心なのは、単語の順序を交換することで、並べ替えることです.
次は一般的なアルゴリズムです

/**
 * by author@ylf
 * using template
 * permutation
 */
#include <iostream>
using namespace std;

template<class T>
void Permutation(T *arr, int n, int idx);

template<class T>
void Print(T *arr, int n);

template<class T>
void Swap(T* arr, int i, int j);

int main() {
	int n;
	cin>>n;
	char* arr = new char[n];
	int i = 0;
	for(i=0;i<n;i++)
		cin>>arr[i];

	Permutation(arr,n,0);

	delete []arr;
	return 0;
}

template<class T>
void Permutation(T *arr, int n, int idx){
	if(idx >= n){
		Print(arr, n);
		return;
	}
	int i = idx;
	for(i=idx;i<n;i++){
		Swap(arr,i,idx);
		Permutation(arr,n,idx+1);
		Swap(arr,i,idx);
	}
}

template<class T>
void Swap(T* arr, int i, int j){
	T temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

template<class T>
void Print(T *arr, int n){
	int i = 0;
	for(i=0;i<n;i++)
		cout<<arr[i];
	cout<<endl;
}

4
abcd
abcd
abdc
acbd
acdb
adcb
adbc
bacd
badc
bcad
bcda
bdca
bdac
cbad
cbda
cabd
cadb
cdab
cdba
dbca
dbac
dcba
dcab
dacb
dabc