算法小结-全排列生成算法之字典序法

Algorithm

前言:本篇文章将介绍编程中常用的全排列算法之字典序法,字典序法是全排列生成算法中的一种常见算法


算法定义

全排列生成算法: 是将给定的序列中所有可能的全排列无重复无遗漏地枚举出来。此处全排列的定义是:从n个元素中取出m个元素进行排列,当n=m时这个排列被称为全排列。

字典序法: 就是将元素按照字典的顺序(a-z, 1-9)进行排列。以字典的顺序作为比较的依据,可以比较出两个串的大小。比如 “1” < “13”<”14”<”153”, 就是按每个数字位逐个比较的结果。对于一个串“123456789”, 可以知道最小的串是“123456789”,而最大的串“987654321”。这样针对这个串以字典序法生成全排列生成全排列,就是依次生成“123456789”->“123456798”->……->”987654312”->”987654321”这样的串。字典序法要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。


算法步骤

  • 设一个需要排序的集合为list = {1,2,3},要求该集合为升序集合
  • 步骤一:从右往左,找出第一个左边小于右边的数,记为list[a], 即list[a] = 2;
  • 步骤二:从右往左,找出第一个大于list[a]的数,记为list[b], 即list[b] = 3;
  • 步骤三:将list[a]和list[b]交换位置
  • 步骤四:将list[a]后面的数据(不包括list[a])由小到大排列。重复步骤一,直到执行次数达到该集合的大小的阶乘时,算法结束,输出结果。

算法例子

  • 设现有一个集合为 list={1,2,3} , 则它的全排列输出为:123,132,213,231,312,321。

算法实现

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
public class main {
/**
* 传入全排列数组,进行交换位置
* @param list
* @param a
* @param b
*/
public static void swap(int[] list, int a, int b) {
int temp = list[a];
list[a] = list[b];
list[b] = temp;
}
/**
* 将list区间[a,n]之间的数据由小到大进行排序
* @param list
* @param a
* @param n
*/
public static void sort(int[] list, int a) {
int temp = 0;
int n = list.length;
for(int i = 1; i < n-a; i++) {
for(int j = a+1; j < n-1; j++) {
if (list[j] > list[j+1]) {
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
public static void prim(int[] list) {
int num = 1, a = 0, b = 0;
// 计算算法需要执行的次数,执行的次数等于集合大小的阶乘
for(int i = list.length; i > 0; --i) {
num *= i;
}
while (num-- != 0) {
for(int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
System.out.println();
// 从右到左,找到第一个左边比右边小的数,设为list[a]
for(int i = list.length - 1; i > 0; i--) {
if (list[i-1] < list[i]) {
a = i-1;
break;
}
}
// 从右到左,找到第一个比list[a]大的数,设为list[b]
for(int i = list.length - 1; i > a; i--) {
if (list[i] > list[a]) {
b = i;
break;
}
}
// 将list[a]和list[b]交换
swap(list, a, b);
// 对list[a]之后的数据进行排序
sort(list, a);
}
}
public static void main(String[] args) {
int[] list = {1,2,3};
prim(list);
}
}
  • 输出结果为:

    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1


算法细节

  • 该算法对数据的要求是升序的,否则会出现结果重复的问题
  • 该算法能够对重复的数据进行全排列,比如说集合{1,2,3,3}

算法小结

  • 该算法是全排列算法中的一种常见的方式,上面已经对算法的一些细节问题进行提及,也许这个算法的实现不是最优的方式,如有其它实现方式,可以共同交流~ 晚安

版权声明:本文为博主原创文章,转载请注明出处http://hunterblog.cn/ 和作者:Hunter,谢谢支持。