-
算法设计与分析实验报告
学
院
计算机学院
专
业
计算机科学与技术
班
级
200
级
班
学
号
姓
名
指导教师
201
1
年
12
月
计算机
学院
计算机科学与技术
专业
班
学号：
姓名：
协作者：
________
教师评定：
实验题目
__
实验一：
Johnson
-Trotter
< br>算法的实现
一、
实验目的与要求
?
理解
Jo
hnson
-Trotter
算法
的思
想
?
掌握
用
Johnson
-Trotter
算
法
来生成排列的方法
二、
实验内容
Johnson-
Trotter
算法通过移动来生成排列
给每个元素赋一个方向，这可以用一个数组来表示，
0
指向
左，
1
指向右。
。
package
/*
*
实现用来生成排列的
Johnson-
Trotter
算法
*
输入：一个正整数
n
*
输出：
{1,...,n}
的所有排列的列表
*/
import
.*;
public
class
JohnsonTrotter {
static
int
elements
[];
static
int
direaction
[];
static
int
k
;
//
用于保存最大的移动元素在数组中的位置
< br>
static
int
count
=
0;
//
用于保存生成的排列总数
static
void
permutation(
int
n){
elements
=
new
int
[n+1];
direaction
=
new
int
[n+1];
//
表示元素的箭头的指向，
< br>1
表示指向左，
0
表示指
向右
for
(
int
i=1;i<=
elements
.
length
-1;i++){
elements
[i] = i;
direaction
[i] =
1;
//
初始化所有箭头指向左
}
output
(
elements
);
while
(
exitMobileE
lement
(
elements
))
{
//
如果存在移动元素
if
(
direaction
[
k
]==1){
//
如果箭头
向左
if
(
k
>1
&&
elements
[
k
]>
elements
[
k
-1]){
//
交换两个元素的位置
int
temp =
elemen
ts
[
k
];
elements
[
k
] =
elements
[
k
-1];
elements
[
k
-1] = temp;
//
同时，还要交换两个元素的箭头指向位置
temp =
direaction
[
k
];
< br>direaction
[
k
]
=
direaction
[
k
-1];
direaction
[
k
-1] = temp;
output
(
elements
);
k
--;
//
调转所有大于
arr[k]
的元素的方向
for
(
int
i=1;i<=
elements
.
length
-
1;i++){
if
(
elements
[i]>
elements
[
k
]){
direaction
[i] =
1-
direaction
[i];
}
}
}
}
else
{
//
箭头向右
if
(
k
<<
/p>
elements
.
length
-1&&
elements
[
k
]>
elements
[<
/p>
k
+1]){
//
交换两个元素的位置
int
temp =
elemen
ts
[
k
];
elements
[
k
] =
elements
[
k
+1];
elements
[
k
+1] = temp;
//
同时，还要交换两个元素的箭头指向位置
temp =
d
ireaction
[
k
];
direacti
on
[
k
] =
direaction
[
k
+1]
;
dire
action
[
k
+1] =
temp;
output
(
elements
);
k
++;
//
调转所有大于
arr[k]
的元素的方向
for
(
int
i=1;i<=
elements
.
length
-
1;i++){
if
(
elements
[i]>
elements
[
k
]){
direaction
[i] =
1-
direaction
[i];
}
}
}
}
}
//while
}
//Permutation
-
-
-
-
-
-
-
-
-
上一篇：有限元瞬态分析
下一篇：JAVASCRIPT使用map的put问题处理