这个问题的提出来源于leetcode上一个经典题型

全排列.png

那么问题来了 这么一个题 我们怎么做
好了 有人说了 for循环遍历啊
我凑 兄弟你是真的low 这种暴力算法的时间复杂度是多少呢
3个的时候就是3个for每个for里面3个数
4个的时候就是4个for每个for里面4个数
里面3个分别是111 222 333去除后一共6个情况 这是人脑算的
3个for*每个for3个数也就是O(n^n)的时间复杂度
比指数还快 要命
这个时候势必要提出一种新的想法去解决这种问题

其实就如啊哈算法里面说的一样
这个问题的模型就是
(为了好理解这里以3个数为例)
这3个数其实就是三张扑克牌
桌子上摆着3个盒子(盒子有先后顺序之分 不如把盒子编号为ABC)
好了 现在的问题就是 盒子和纸牌一共有多少种组合情况
这里不如把盒子abc这么一摆
好了 我手里123三张牌我也按大小顺序往里发
我们用nowlist代表盒子 nowlist的下标是盒子的编号 值是盒子里的牌
book这个数组用来记录手里的牌 1是没有 0 是有
注意 游戏规则是这样的：
1、牌就一张，发过的牌自然就没了(和原来的题里没有重复的数是一样的)
2、牌越发越少，手里没牌的时候自然就是一种情况(在这里我们使用了数组的实际长度flag来判断)
3、要记得擦屁股，一种情况完成后，从盒子里把牌收回来，盒子清空，手里又有牌了。

好了 贴代码之前必须再啰嗦一句
为啥使用递归呢
因为递归的时候每一层函数都有自己的变量 比如for里面的i 这样保证了我们按照顺序去遍历牌
且 每一层都是独立的 既不会少也不会漏 唯一的注意点就是这不是尾递归 一定记得擦屁股
// 全排列.cpp : 定义控制台应用程序的入口点。
//

include "stdafx.h"

include "stdio.h"

include "stdlib.h"

define length 7

int total=0;
int book[length];
int nowlist[length];//nowlist存储纸牌的箱子
int flag=0;
bool islast();
void sort();
void sort()
{
int i=0;
int j=0;
if (flag == length)
{
for (j = 0; j<length; j++)
printf("%d ", nowlist[j]);
printf("\n");
total++;
return;
}
for(i=0;i<length;i++)
{
if(book[i]==0)
{
book[i] = 1;
nowlist[flag] = i+1;//放纸牌
flag++;
sort();
flag--;
nowlist[flag] = 0;
book[i] = 0;
}
}
}
int main()
{
sort();
printf("all==%d\n", total);
system("pause");
return 0;
}