B.R.Heap全排列算法求教!

2013-09-05 13:52:04 +08:00
 venson999
以下是B.R.Heap的全排列算法代码,swap那句是什么意思,百思不得其解,虚心求教!

public void permute(int[] v, int n) {
if (n == 1) {
System.out.println(Arrays.toString(v));
} else {
for (int i = 0; i < n; i++) {
permute(v, n - 1);
swap(v, n % 2 == 1 ? 0 : i, n - 1);
}
}
}
3736 次点击
所在节点    程序员
7 条回复
freeznet
2013-09-05 14:24:05 +08:00
swap(v, n % 2 == 1 ? 0 : i, n - 1);
可以翻譯成
if( n % 2 == 1 ){
swap(v, 0, n-1)
}else{
swap(v, i ,n-1)
}
不知道你問的是不是這個...
venson999
2013-09-05 14:42:59 +08:00
@freeznet 呵呵,问的当然不是语法问题,我是不明白为什么递归以后以这样的规则进行交换可以生成全排列?
KMHook
2013-09-06 09:49:22 +08:00
http://blog.csdn.net/honpey/article/details/6904118

注意到:
当n为偶数时,permute()输出全排列后数组元素循环右移一位。
当n为奇数时,permute()输出全排列后数组元素顺序保持不变。
venson999
2013-09-06 14:29:27 +08:00
@KMHook 首先感谢你的回复,有一些疑问,为什么当n为奇数时,permute()输出全排列后数组元素顺序保持不变?以输入[1, 2, 3]为例,会得到如下输出:
[1, 2, 3]
[2, 1, 3]
[3, 1, 2]
[1, 3, 2]
[2, 3, 1]
[3, 2, 1]
数组顺序完全变了,是我这样理解有问题吗?
byelims
2013-09-06 16:49:05 +08:00
关于如何生成全排列我是这么想的。

先从数组中“取”出第一个元素,然后对数组里剩下的元素进行递归调用。
接下来取第二个,递归;取第三个,递归;……
所以我想关键在于怎么把数组里的元素不重复地取出来?
我的做法是把目标元素先换到数组里的一个固定位置,递归完成后再换回去,恢复原样。

https://gist.github.com/byelims/6461065

至于为什么可以像顶楼那样做,我想你可以看看原始论文。

http://comjnl.oxfordjournals.org/content/6/3/293.full.pdf
venson999
2013-09-06 17:10:23 +08:00
@byelims 你说的算法需要两次交换,而Heap的算法只需要一次交换,论文我之前已经看过了,里面好像也并没有说为什么会采用这种区分奇偶的交换方法。我想可能是通过对IndexTable方法优化得来的,但是还是想不明白。
venson999
2013-09-06 17:14:32 +08:00
@byelims 另外能不能把gist代码去掉呢,github访问不稳定,很影响这个主题的访问速度啊。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/81407

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX