計算機算法設計與分析——求解全排列問題（C++）

【問題描述】

對于給定的正整數n(n>=1)，求1~n的所有全排列。

【問題求解】

【算法實作（C++）】

void Insert(vector<int> s, int i, vector<vector<int>>&ps1)
//在每個集合元素中間插入i得到ps1
{
	vector<int> s1;
	vector<int>::iterator it;
	for (int j = 0; j < i; j++)//在s(含i-1個整數)的每個位置插入i
	{
		s1 = s;
		it = s1.begin() + j;//求出插入位置
		s1.insert(it, i);//插入整數i
		ps1.push_back(s1);//添加到ps1中
	}
}

void Perm(int n)//求1～ｎ的所有全排列
{
	vector<vector<int>>ps1;//臨時存放子排列
	vector<vector<int>>::iterator it;//全排列疊代器
	vector<int> s, s1;
	s.push_back(1);
	ps.push_back(s);//添加{1}集合元素
	for (int i = 2; i <= n; i++)//循環添加1～ｎ
	{
		ps1.clear();//ps1存放插入i的結果
		for (it = ps.begin(); it != ps.end(); ++it)
			Insert(*it, i, ps1);//在每個集合元素中間插入i得到平時ps1
		ps = ps1;
	}
}