个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
26
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章全排列算法-递归与字典序的实现方法(Java)由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
全排列算法-递归与字典序的实现方法(Java) 。
全排列:
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 例如:
1 、2 、3三个元素的全排列为:
{1，2，3}，{1，3，2}，{2，1，3}，{2，3，1}，{3，1，2}，{3，2，1}.
------------------------------------------------------ 。
解法1（递归） 。
如下图：要对1、2、3、4进行排序，第一个位置上的元素有四种可能：1或2或3或4，假如已经确定了第一个元素为4，剩下的第二个位置上可以是1、2、3，很显然这具有递归结构，如果原始要排列的数组顺序为1、2、3、4，现在只要分别交换1、2，1、3，1、4然后对剩下的3个元素进行递归的排列.
代码:
----------------------------------------------- 。
|
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
|
public
void
Permutation(
char
chs[],
int
start )
{
if
(start==chs.length-
1
)
{
Arrays.toString(chs);
//如果已经到了数组的最后一个元素，前面的元素已经排好，输出。
}
for
(
int
i=start;i<=chs.length-
1
;i++)
{
//把第一个元素分别与后面的元素进行交换，递归的调用其子数组进行排序
Swap(chs,i,start);
Permutation(chs,start+
1
);
Swap(chs,i,start);
//子数组排序返回后要将第一个元素交换回来。
//如果不交换回来会出错，比如说第一次1、2交换，第一个位置为2，子数组排序返回后如果不将1、2
//交换回来第二次交换的时候就会将2、3交换，因此必须将1、2交换使1还是在第一个位置
}
}
public
void
Swap(
char
chs[],
int
i,
int
j)
{
char
temp;
temp=chs[i];
chs[i]=chs[j];
chs[j]=temp;
}
|
递归方法会对重复元素进行交换比如使用递归对{1，1}进行全排序会输出：{1，1}，{1，1}两个重复的结果。要在排序的时候去掉重复结果，可以修改一下代码如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public
static
void
Permutation(
char
chs[],
int
start)
{
if
(start==end)
{
list.add(
new
String(chs));
}
for
(
int
i=start;i<=chs.length-
1
;i++)
{
if
(i==start||chs[i]!=chs[start])
{
//在排列的时候进行判断如果后面的元素与start相同时就不进行排序。
//这样就可以避免对重复元素进行排序
Swap(chs,i,start);
Permutation(chs,start+
1
);
Swap(chs,i,start);
}
}
}
|
解法2（字典序法） 。
字典序法 。
对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后.
列如：对a、b、c进行排序的结果是{a,b,c}、{a,c,b}、{b,a,c}、{b,c,a}、{c,a,b}、{c,b,a} 。
字典序法的优点是排列的结果按照顺序输出并且对于重复的元素不进行重复排序.
字典排序法的思想:
例如：对元素1，2，3，4进行排序，假设默认的数组顺序为{1，2，3，4}，先输出第一个排列：1、2、3、4。然后从右向左找到第一个非递增的数，4，3，因为3比4小，交换3、4，并且对3后面的数进行逆序排列，第二个排列为{1，2，4，3}，再从右向左3，4，2，发现2比4小，交换从右向左第一个比2大的数，交换后{1，3，4，2}再对3后面的数进行逆序排列第三个序列为：{1，3，2，4} 。
依次循环直到数组成为完全递减数组结束1、2、3、4字典排序的最大序列为{4，3，2，1}.
-------------------------------------------- 。
代码 。
------------------------------------------- 。
|
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
|
public
void
PermutationWithDictionary(
char
chs[])
{
Arrays.sort(chs);
//先对数组的元素进行依次排序
while
(
true
)
{
System.out.println(chs);
int
j=chs.length-
1
;
int
index=
0
;
for
(j=chs.length-
2
;j>=
0
;j--)
{
if
(chs[j]<chs[j+
1
])
{
index=j;
break
;
//从右向左找到第一个非递增的元素
}
else
if
(j==
0
){
return
;
}
}
for
(j=chs.length-
1
;j>=
0
;j--)
{
if
(chs[j]>chs[index])
break
;
//从右向左找到第一个比非递增元素大的元素
}
Swap(chs,index,j);
//交换找到的两个元素
Reverse(chs,index+
1
);
//对非递增元素位置后面的数组进行逆序排列
}
}
public
static
void
Reverse(
char
chs[],
int
i)
{
int
k=i,j=chs.length-
1
;
while
(k<j)
{
Swap(chs,k,j);
k++;
j--;
}
}
public
static
void
Swap(
char
chs[],
int
i,
int
j)
{
char
temp;
temp=chs[i];
chs[i]=chs[j];
chs[j]=temp;
}
|
以上这篇全排列算法-递归与字典序的实现方法(Java) 就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我.
最后此篇关于全排列算法-递归与字典序的实现方法(Java)的文章就讲到这里了,如果你想了解更多关于全排列算法-递归与字典序的实现方法(Java)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
26
4
0
序 大家好呀，我是summo，这次来写写我在上班空闲(摸鱼)的时候做的一个小网站的事。去年阿里云不是推出了个活动嘛，2核2G的云服务器一年只要99块钱，懂行的人应该知道这个价格在业界已经是非常良心了
我尝试根据给定的级别顺序(BFS 顺序)构造 BST。我知道这是可能的，但我不知道我该怎么写。问题是我必须使用 BFS 序列。所以，我不能在这里使用递归，我必须迭代地编写我的程序......我发现这有
我是一名优秀的程序员,十分优秀！