实现STL中的next_permutation函数

2015-05-16

@(C Plus Plus)

前几天复习一份各大公司的面试笔试资料—题目是《百度、google、微软、MTK经典面试题》，应该是我在考研的时候看过的，为了准备机试，北理工13年计算机学院的硕士生保研题目就有一个是输出一个字符串的全排列。这个题目以前是没见过，所以仔细的研究了一下.

那就还是从这个题目开始：

输出一个字符串的全排列

注意的是，这个题目没有要求按照字典序输出，只要输出所有的排列就行。

STL 函数 next_permutation()

第一种比较容易的方式就是利用STL里面的函数next_oermutation()，这个函数的返回值是bool类型，若按照字典序，字符串还有下一个排列，就改变字符串为下一个排列，并返回true，否则返回false，并且将字符串重置为初始状态。
程序如下：

void printAllPermutation(char *str)
{
	int len = strlen(str);
	char *pend = str + len;
	std::sort(str,pend);
	std::cout<<str<<std::endl;
	while(std::next_permutation(str,pend))
	{
		std::cout<<str<<std::endl;
	}
}

交换的策略

这个算法我一直没真正理解是真么意思，它的基本思想是交换-恢复，遍历所有两个位置的组合，它是无序的，具体的程序如下：

void swap(char *a,char *b)
{
	char t = *a;
	*a = *b;
	*b = t;
}
void printAllPermutation(char *str,char *pbeg)
{
	if(str == NULL)
		return;
	if(*pbeg == '\0')
		std::cout<<str<<std::endl;
	for(char *p = pbeg;*p != '\0';++p)
	{
		swap(p,pbeg);
		printAllPermutation(str,pbeg+1);
		swap(p,pbeg);
	}
}

实现next_permutation()函数

这是前几天在网上找到的，还是网易2014年实习生笔试题目，作者的思路不错，但是就是没有描述清楚。
我来试着描述一下他的思想：

假设当前序列是13542，那么我们可以手动计算出下一个序列是14235；
这个题目的关键点是寻找一个关键位置，观测发现，这样的字符串通过有个性质，其中一个位置，将字符串分成两部分，前半部分没什么规律，后半部分递减（可以为空）。
寻找下一个排列就是，找到这样的一个位置，这个位置以后的字符串是递减的，也就是说后半部分已经没有下一个排列了（下一个排列回归到初始状态），从后半部分找到第一个（从后往前找）比当前位置大的字符，然后交换。
比如上面的例子，关键位置的元素是3，后半部分第一个比3大的元素是4，交换顺序后字符串是14532，当关键位置变大时，其后面的子字符串应该是第一个排列，也就是递增的，因此，下一步就是将后半部分反转（交换后也是递减的，因此直接反转就是递增的），得到字符串是14235。

下面是程序实现：

bool mynext_permutation(char *beg,char *end)
{
	if(beg == NULL || strlen(beg) == 0)
		return false;
	char *k = end -2;
	while(*k > *(k+1))
		--k;
	if(k < beg )  // 字符串已经逆序，最后一个排列
	{
		reverse(beg,end);
		return false;
	}
	char *p = end -1;
	while(*p < *k)
		--p;
	swap(p,k);
	reverse(k+1,end);
	return true;
}

为了验证，给出测试程序：

int main()
{
    char str1[] = "1234";
    char str2[] = "1234";
    cout<<str1<<endl;
    cout<<str2<<endl<<endl;
    while(mynext_permutation(str1))
    {
        std::next_permutation(str2,str2 + strlen(str2));
        cout<<str2<<endl;
        cout<<str2<<endl<<endl;
    }
    return 0;
}

重新实现库函数貌似是面试笔试常考的，就以这个为开始吧，以后继续写写！

参考

网易有道笔试题(2014届，2013.10北邮站)
百度、谷歌、微软、MTK经典面试题