全排列的递归与非递归及c++11的lambda, for_each, sort初见

一直说着STL终于开始接触了，作为新特性还是挺好上手的。
具体实现直接写在代码里了（这大概是一篇只留给自己看的manual..)

使用clang编译

$ clang -std=c++11 -stdlib=libc++ permutation_1.cpp -o test
注意这样一来就一定要加using namespace std;

具体还有什么坑等更新的时候想起来再写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<stdio.h>
#include<algorithm>
using namespace std; // -std=c++11 需要这句不然error
void swap(int &a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
}
void permutation(int array[], int start, int end)  //recursive
{
	if (array == NULL) return;
	if (start == end)
	{
		// for (int i = 0; i <= end; i++)
		// {
		//     printf("%d ",array[i]);
		// }
		// printf("\n");
		for_each(array, array+end+1, [] (int i)-> void { printf("%d",i); }); //使用for_each 和 lambda表达式
		printf("\n");
	}
	for (int j = start; j <= end; j++)
	{
		int k;//添加标志位k，第k位与j位相等
		for (k = 0; k < j; k++) //如果之前的值一样则不用交换
		{
			if (array[k] == array[j])
				break;
		}
		if (k<j) continue;
		swap(array[j],array[start]);
		permutation(array, start+1, end);
		swap(array[j],array[start]);
	}
}
void reverse(int array[], int start, int end)
{
	while( start < end )
	{
		swap( array[start++], array[end--] );
	}
}
void permutation2(int array[],int length) //iterative
{
	sort(array,array+length,[](int x, int y ) -> bool {return x<y;});  //最后的函数是定义greater,默认升序排列（从小到大）
	while (true)
	{
		for (int j = 0; j < length; j++)
		{
			printf("%d",array[j]);
		}
		printf("\n");
		int i = length - 2;//第一步找最后的递增序列头节点
		for (;i >= 0 && array[i] >= array[i+1]; i--);  //只写for不写{}来控制变量大小  //注意这个等于号啊我去
		if (i < 0) return;
		int k = length-1; //第二步找到从右向左第一个比i大的节点
		for (;k > i && array[k] <= array[i]; k--);
		swap(array[i],array[k]);// 第三步交换
		reverse(array, i+1, length-1);//第四步对i之后的节点逆序(交换后k之后的数字都比i小且一定是从大到小排列（i是最后的递增头），逆序变为顺序)
		//现在的array为之前的字典序的后一位
	}
}
void permutation3(int array[], int length)
{
	sort(array,array+length,[](int x, int y ) -> bool {return x<y;});  //最后的函数是定义greater,默认升序排列（从小到大）
	do
	{
		for_each(array,array+length,[](int x) -> void{ printf("%d",x); });
		printf("\n");
	}while(next_permutation(array, array+length)); //通过c++11自带的next_permutation实现
}
int main()
{
	int array[] = {2,1,4,3};
	// permutation(array,0,3);
	permutation3(array, 4);
	return 0;
}