全排列问题（详细介绍加图解）

Valarie ·

更新时间:2024-09-21

· 833 次阅读

全排列算法（详细介绍图解）

1.全排列的定义
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

2.解决全排列的方法
如求[A,B,C]的全排列
首先保持A不变，对[B,C]进行全排列，同样的，我们先保持B不变，对[C]求全排列，由于C只有一个，它的排列只有一种: C .然后输出得到[A,B,C]
接下来[B,C]不能以B开头了，B,C交换位置(即C,B)，求B的全排列,输出得到[A,C,B]
即 [A,B,C]= =>A,[B,C]= =>A,B,[C]
交换B,C = =>A,C,[B]
将顺序换成原样[A,B,C]
交换A,B==>B,[A,C]= =>B,A,[C]
交换A,C==>B,C,[A]
将顺序换成原样[A,B,C]
交换A,C==>C,[B,A]= =>C,B,[A]
交换B,A==>C,A,[B]
如下图（本图来自网络）：
在这里插入图片描述

对于算法的设计，我们可以创建一个数组，它保存了原始的数据，而且我们在每次交换后再交换回来，再变回原来的数组，这样的程序在遍历时就不会出错。

那我们该如何实现呢，这里用到了递归
规范的流程大致为
1.开始for循环
2.将数组的第一个元素与自身交换，相等于什么都没做
3.求第二个元素到第n个元素的全排列
4.递归的求第三个元素到第n个元素的全排列
…
5.直到递归到第n个元素，递归出口
6.交换位置，将改变的数组变回。
7.交换第一个元素与第二个元素
8.重复3.4.5.6
9.不断让第一个元素与数组其他元素交换，直至for循环结束
直接上代码

private static void fullSort(int[] arr, int start, int end) {
  //递归出口
  if(start==end) {
   for(int i:arr) {
    System.out.print(i);
   }
   System.out.println();
  }
  //对应第一步
  for(int i=start;i<=arr.length-1;i++) {
   //对应第2，7，9步
   swap(arr,i,start);
   //递归调用，对应3-5步
   fullSort(arr, start+1, end);
   //交换位置换成原样，对应第六步
   swap(arr,i,start);
  }
 }
 private static void swap(int[] arr, int i, int j) {
  int temp=arr[i];
  arr[i]=arr[j];
  arr[j]=temp;
 }
 public static void main(String[] args) {
  int[] arr= {1,2,3,4};
     System.out.println("{1,2,3,4}的全排列有：");
     fullSort(arr,0,arr.length-1);
 }

运行结果为

在这里插入图片描述