本文主要是介绍算法练习：排列组合之全排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
输入一个不含相同数字的序列，输出所有可能的排列。
问题分析
与之前的“求解子集合”类似，使用递归方法：典型的在for循环内调用递归函数。不同的是，必须等到所有的数字均在集合里才能输出。为了记录每个数字的使用情况，还需一个辅助数组记录每个数字的使用情况。详见代码部分的FullPermutation函数。
扩展问题
如果数列中含有重复的数字，并且输出的结果不含重复组合，那么怎么处理？比如，输入{1，1，2}，输出{1，1，2}， {1，2，2}， {2， 1， 1}。我们在挑选数字的时候，除了考虑当前使用情况外，还需要判断前一个相同元素的使用情况。如果前一个相同元素还未被使用，那么当前元素也不应该被使用，确保输出是唯一的。详见代码部分的FullPermutationEx函数。
实现代码
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;typedef vector<int> IntArray;
typedef vector<bool> BoolArray;
typedef vector<vector<int>> ResultSet;ResultSet gResultSet; //结果集合//递归求解全排列(源序列中不含有相同的元素)
void FullPermutation( const IntArray& mSrcArray, IntArray& mDstArrayTemp, BoolArray& bUseFlag )
{if ( mDstArrayTemp.size() >= mSrcArray.size() ){//求得一个结果gResultSet.push_back( mDstArrayTemp );}else{for( int i = 0; i < mSrcArray.size(); ++i ){//已经被使用if ( bUseFlag[i] ) continue;mDstArrayTemp.push_back( mSrcArray[i] );bUseFlag[i] = true;//递归处理FullPermutation( mSrcArray, mDstArrayTemp, bUseFlag );//重置，即回溯mDstArrayTemp.pop_back();bUseFlag[i] = false;}}
}//递归求解全排列(源序列中含有相同的元素)
void FullPermutationEx( const IntArray& mSrcArray, IntArray& mDstArrayTemp, BoolArray& bUseFlag )
{if ( mDstArrayTemp.size() >= mSrcArray.size() ){//求得一个结果gResultSet.push_back( mDstArrayTemp );}else{for( int i = 0; i < mSrcArray.size(); ++i ){
// //已经被使用
// if ( bUseFlag[i] ) continue;//除了考虑当前使得情况外，还需判断是否为重复元素的第一个//如果前一个相同元素还未被使用，那么当前元素也不应该被使用，确保输出唯一if( bUseFlag[i] || ( i > 0 && !bUseFlag[i-1] && mSrcArray[i] == mSrcArray[i-1]) )continue;mDstArrayTemp.push_back( mSrcArray[i] );bUseFlag[i] = true;//递归处理FullPermutationEx( mSrcArray, mDstArrayTemp, bUseFlag );//重置，即回溯mDstArrayTemp.pop_back();bUseFlag[i] = false;}}
}//输出结果集
void OutPutResultSet()
{if ( gResultSet.size() <= 20 ) { for( ResultSet::iterator it = gResultSet.begin(); it != gResultSet.end(); ++it ) { for( IntArray::iterator itTemp = it->begin(); itTemp != it->end(); ++itTemp ) { cout << *itTemp << " "; } cout << endl; } } cout << "总共结果数：" << gResultSet.size() << endl; cout << "---------------------------------------" << endl;
}int main()
{IntArray mSrcArray; IntArray mDstArrayTemp; BoolArray bUseFlag;while( true ) { //构造源数据 int nTemp = 0; mSrcArray.clear(); bUseFlag.clear();while( cin >> nTemp ) { if ( nTemp == 0 ) break; mSrcArray.push_back( nTemp ); bUseFlag.push_back( false );} //从小到大排序 sort( mSrcArray.begin(), mSrcArray.end() ); mDstArrayTemp.clear(); gResultSet.clear(); //递归求解全排列//FullPermutation( mSrcArray, mDstArrayTemp, bUseFlag );FullPermutationEx( mSrcArray, mDstArrayTemp, bUseFlag );//输出结果 OutPutResultSet(); } return 0;
}
系列文章说明:
1.本系列文章[算法练习],仅仅是本人学习过程的一个记录以及自我激励,没有什么说教的意思。如果能给读者带来些许知识及感悟，那是我的荣幸。
2.本系列文章是本人学习陈东锋老师《进军硅谷，程序员面试揭秘》一书而写的一些心得体会，文章大多数观点均来自此书，特此说明！
3.文章之中,难免有诸多的错误与不足,欢迎读者批评指正,谢谢.
作者：山丘儿
转载请标明出处，谢谢。原文地址：http://blog.csdn.net/s634772208/article/details/46712519
这篇关于算法练习：排列组合之全排列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
