首语
首先要知道，什么是全排列
百度百科上定义：
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
公式：全排列数f(n)=n!(定义0!=1)
基本操作步骤
最基本的全排列
看了b站up 的视频，了解大概基础
我手动敲一下这个代码哈
#include<stdio.h>
void swap(int A[],int i,int j)
{
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
void printArray(int A[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
}
void perm(int A[],int p,int q)
{
if(p==q)
{
printArray(A,q+1);
}
else{
int i;
for(i=p;i<=q;i++)
{
swap(A,p,i);
perm(A,p+1,q);
swap(A,p,i);
}
}
}
int main()
{
int A[3]={1,2,3};
perm(A,0,2);
}
如果想要去重
思路：在进行交换前进行判断，若是重复就跳过这种情况。（另写一段代码来操作）
代码：
#include<stdio.h>
void swap(int A[],int i,int j)
{
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
void printArray(int A[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
}
bool ifsame(int A[],int p,int q)
{
for(int i=p;i<q;i++)
if(A[i]==A[q])
return false;
return true;
}
void perm(int A[],int p,int q)
{
if(p==q)
{
printArray(A,q+1);
}
else{
int i;
for(i=p;i<=q;i++)
if(ifsame(A,p,i))
{
swap(A,p,i);
perm(A,p+1,q);
swap(A,p,i);
}
}
}
int main()
{
int A[4]={1,2,3,3};
perm(A,0,2);
}
算法分类
全排列算法有四种
分别为：
- 字典序法
- 递增进位制数法
- 递减进位制数法
- 邻位对换法