C语言-全排列

C语言-全排列

本当迷

2021 年 08 月 06 日

1025 次浏览

暂无评论

1770字数

学习语言

主要是那个递归，有点烦人！！！

## 思路：

比如

1，2，3

1，3，2

2，1，3

2，3，1

3，2，1

3，1，2

我们会发现所以数字都会出现在第一位，我们可以写一个for循环，使每一个数字都有机会出现在第一位；
</div>

怎么使每一个数字都出现在第一位呢？
</div>

我们可以利用交换两元素的位置，达到我们的目的！
</div>

其实每一次递归我们可以只看两个元素，原因是，交换也只是交换两个元素（核心操作）
</div>

什么时候递归结束呢？
</div>

当交换只有一个元素时，代表我们递归结束，这是我们也就可以输出数组了!
</div>

每一次交换后，我们还要交换回来，原因是，避免没有重复元素出现。
</div>

## 代码：

```cpp
#include<stdio.h>

void print(int array[], int x)//输出交换元素后的数组 
{
	int i;
	for(i = 0; i < x; i++)
	{
		printf("%d", array[i]);
	}
	printf("\n");

}

void swap(int array[], int n, int m)//交换数组中下标为 n, m 的元素 位置 
{
	int temp;
	temp = array[n];
	array[n] = array[m];
	array[m] = temp;
	 
}

void prem(int array[], int a, int b)
{
	int i;
	if(a == b)//当只有一个元素时，我们输出数组 
	{
		print(array, b);
	}
	for(i = a; i < b; i++) //利用for循环使每一个元素都有机会出现在第一位 
	{
		swap(array, a, i);//交换元素 位置

prem(array, a + 1, b);//递归实现循环交换元素操作

swap(array, a, i);//还原交换后的元素位置 
	}
}

int main()
{
	int array[] = {1, 2, 3};
	int size;
	size = sizeof(array) / sizeof(array[0]);//求数组的元素个数 
	prem(array, 0, size);
	return 0;
}
```

。

## 规律深搜：

```cpp
#include<stdio.h>            
using namespace std;
 
/*全局变量:*/ 
int n;         //全排列的长度
int answer[100];   //最后输出的答案
bool visit[100];   //储存每个数是否用过,true用过,false没用过
 
/*深度优先搜索*/
void DFS(int s)                                    //搜索,s是当前枚举的位数(因为数组是从0开始的所以s调用的时候需要+1),表示的是到此为止,已经确定的全部排列的数的个数
{
    if (s == n)//判断是否已经枚举完了,若枚举完，就输出
    {
        for (int i = 0; i < n; i++)               //输出第i个数
        {
            printf("%d", answer[i]);               //输出，若用cpp形式：cout<<answer[i];
        }
        puts("");//相当于printf("\n");             //换行
    }
    else
    {
        for (int i = 0; i < n; i++) //枚举,看到此为止有哪些数没用过
        {
            if (!visit[i])     //判断这个数是否被用过
            {
                visit[i] = true;  //标记这个数用过了
                answer[s] = i+1;      //标记第s个数是多少
                DFS(s + 1);       //进行下一层搜索
                visit[i] = false; //取消标记(回溯)
            }
        }
    }
    return;//若打印完就直接回溯，若for枚举完就直接回溯
}
 
int main()
{
    scanf("%d", &n);    //输入
    DFS(0);             //调用深搜
    return 0;
}
```

最后修改：2022 年 02 月 12 日