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

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 4643 days ago, the information mentioned may be changed or developed.

以下是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);
}
}
}

int

Swap

permute

7 replies • 1970-01-01 08:00:00 +08:00

freeznet

Sep 5, 2013

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

Sep 5, 2013

@freeznet 呵呵，问的当然不是语法问题，我是不明白为什么递归以后以这样的规则进行交换可以生成全排列？

KMHook

Sep 6, 2013

http://blog.csdn.net/honpey/article/details/6904118

注意到：
当n为偶数时，permute()输出全排列后数组元素循环右移一位。
当n为奇数时，permute()输出全排列后数组元素顺序保持不变。

venson999

Sep 6, 2013

@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

Sep 6, 2013

关于如何生成全排列我是这么想的。

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

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

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

http://comjnl.oxfordjournals.org/content/6/3/293.full.pdf

venson999

Sep 6, 2013

@byelims 你说的算法需要两次交换，而Heap的算法只需要一次交换，论文我之前已经看过了，里面好像也并没有说为什么会采用这种区分奇偶的交换方法。我想可能是通过对IndexTable方法优化得来的，但是还是想不明白。

venson999

Sep 6, 2013

@byelims 另外能不能把gist代码去掉呢，github访问不稳定，很影响这个主题的访问速度啊。