排列组合

以你之姓@ 2021-10-16 00:14 528阅读 0赞

## 1.引言 ##

pku的OJ平台1731题，就是求一个输入字符串的全排列。在STL中有两个和排列相关的算法，next\_permutation和prev\_permutation。

## 2.next\_permutation ##

这个算法的返回值为bool类型，如果能找到下一个排列的话就返回true，否则为false。有两个版本，第一个版本就是采用元素型别所提供的less-than操作符来决定下一个排列组合。

算法的思想是：首先从最尾端向前寻找连个相邻元素，第一个元素为\*（i-1），第二个元素为\*i，且满足\*(i-1)<\*i。然后再从尾端向前寻找一个元素\*j，使得\*j>\*(i-1);然后将\*(i-1)与\*j对调，之后对\*i（包括\*i）之后的元素翻。

template <class BidirectionalIterator>
    bool next_permutation (BidirectionalIterator first, BidirectionalIterator last)
    {
        if (first == last) return false;
        BidirectionalIterator i = first;
        ++i;
        if (i == last) return false;           //元素个数为0，或者1，返回false
        i = last;
        --i;
        for (;;)
        {
          BidirectionalIterator ii = i--;     //锁定两个相邻元素
          if (*i < *ii)                        
          {
            BidirectionalIterator j = last;
            while (!(*i < *--j));          //向后寻找*j
            iter_swap(i, j);				//交换
            reverse(ii, last);				//翻转
            return true;
          }
          if (i == first)					//没有下一个排列
          {
            reverse(first, last);
            return false;
          }
        }
    }

做到这里就可以对pku1731题进行解答了，代码如下：

#include <stdio.h>
    #include <string>
    #include <algorithm>
    using namespace std;
    void swap(char &a,char &b)
    {
    	char c=a;
    	a=b;
    	b=c;
    }
    void rever(char *str,int len)
    {
    	int i=0;
    	int j=len-1;
    	while (i<j)
    	{
    		swap(str[i],str[j]);
    		i++;
    		j--;
    	}
    }
    bool find(char* str,int len)
    {
    	if (str==NULL||len<2)
    		return false;
    	int i=len;
    	do 
    	{
    		i--;
    	}while (i>0&&str[i-1]>=str[i]);       //注意相等元素不符条件
    	if (i==0)
    		return false;
    	int j=len;
    	do 
    	{
    		j--;
    	} while (j>0&&str[j]<=str[i-1]);
    	swap(str[i-1],str[j]);
    	rever(str+i,len-i);
    	return true;
    }
    
    int main()
    {
    	char str[200];
    	scanf("%s",str);
    	int len=strlen(str);
    	sort(str,str+len);
    	printf("%s\n",str);
    	//这里如果不是自己编写排列算法的话，那么直接调用next_permutation即可。
    	//while (next_permutation(str,str+len))   
    	while (find(str,len))
    		printf("%s\n",str);
    	return 0;
    }

## 3.prev\_permutation ##

prev\_permutation是寻找上一个全排列。其思想和next\_permutation类似。也是从最后端寻找相邻对，只是和next\_permutation的判定条件正好相反：\*(i-1)>\*i，\*j<\*(i-1)，之后的对调和翻转操作都一样。

template <class BidirectionalIterator>
    bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last)
    {
        if (first == last) return false;
        BidirectionalIterator i = first;
        ++i;
        if (i == last) return false;
        i = last;
        --i;
        for (;;)
        {
          BidirectionalIterator ii = i--;
          if (*ii < *i)
          {
            BidirectionalIterator j = last;
            while (!(*--j < *i))
              ;
            iter_swap(i, j);
            reverse(ii, last);
            return true;
          }
          if (i == first)
          {
            reverse(first, last);
            return false;
          }
       }
    }

### 4.递归解法 ###

对于排列，递归的解法更加为人所知。上述的排列算法去除了重复，但是有的时候需要保留重复。此时递归解法就能排上用尝，并且递归算法也可以设置为去除重复，只要增加一个判定函数即可。

#### 4.1字符串版本 ####

void permutation(char str[],char* begin)
    {
    	if(*begin==’\0’)
    		printf(“%s\n”,str);
    	else
    	{
    		for(char *p=begin;*p!=’\0’;++p)
    		{
    			swap(*p,*begin);
    			permutation(str,begin+1);
    			swap(*p,*begin);
    		}
    	}
    }

#### 4.2数字数组版本 ####

//因为字符串有’\0’作为结束标志，而数组是没有的，所以多加一个长度参数表示结束
    void permutation(int a[],int begin,int len)
    {
    	int i;
    	if(begin==len)
    	{
    		for(i=0;i<len;++i)
    			cout << a[i] <<” ”;
    		cout << endl;
    	}
    	else
    	{
    		for(i=begin;i<lenl;++i)
    		{
    			swap(a[i],a[begin]);
    			permutarion(a,begin+1,len);
    			swap(a[i],a[begin]);
    		}
    	}
    }

#### 4.3递归解法去除重复 ####

去除重复需要加一个判定函数，这个函数是判定交换的两值之间，是否有等于被交换的值，若果有返回false（代表跳过此次交换），没有返回true。并且要注意这个交换是用于下次递归的！！

bool isSwap(int a[],int begin,int end)//begin和end分表前后两个需要交换的值
    {
    	for(int i=begin;i<end;++i)
    		if(a[i]==a[end]) return false;
    	return true;
    }
    //以数字版本为例，将其改为去除重复的版本：
    void permutation(int a[],int begin,int len)
    {
    	int i;
    	if(begin==len)
    	{
    		for(i=0;i<len;++i)
    			cout << a[i] <<” ”;
    		cout << endl;
    	}
    	else
    	{
    		for(i=begin;i<lenl;++i)
    		{
    			if(isSwap(a,begin,i))
    			{
    				swap(a[i],a[begin]);
    				permutarion(a,begin+1,len);
    				swap(a[i],a[begin]);
    			}
    		}
    	}
    }

### 5.应用 ###

如果面试题是按照一定要求摆放若干个数字，我们可以先求出这些数字的所有排列，然后一一判定每个排列恕不是满足题目给出的要求。比如正方体的8顶点，8皇后问题，当然素组分割也能用排列组合暴力解出。

####     ####