算法练习：排列组合之全排列

问题描述

输入一个不含相同数字的序列，输出所有可能的排列。

问题分析

与之前的“求解子集合”类似，使用递归方法：典型的在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.文章之中,难免有诸多的错误与不足,欢迎读者批评指正,谢谢.

作者：山丘儿