V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
venson999
V2EX  ›  程序员

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

  •  
  •   venson999 · 2013-09-05 13:52:04 +08:00 · 3869 次点击
    这是一个创建于 4096 天前的主题,其中的信息可能已经有所发展或是发生改变。
    以下是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);
    }
    }
    }
    7 条回复    1970-01-01 08:00:00 +08:00
    freeznet
        1
    freeznet  
       2013-09-05 14:24:05 +08:00   ❤️ 1
    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
        2
    venson999  
    OP
       2013-09-05 14:42:59 +08:00
    @freeznet 呵呵,问的当然不是语法问题,我是不明白为什么递归以后以这样的规则进行交换可以生成全排列?
    KMHook
        3
    KMHook  
       2013-09-06 09:49:22 +08:00   ❤️ 2
    http://blog.csdn.net/honpey/article/details/6904118

    注意到:
    当n为偶数时,permute()输出全排列后数组元素循环右移一位。
    当n为奇数时,permute()输出全排列后数组元素顺序保持不变。
    venson999
        4
    venson999  
    OP
       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
        5
    byelims  
       2013-09-06 16:49:05 +08:00   ❤️ 1
    关于如何生成全排列我是这么想的。

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

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

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

    http://comjnl.oxfordjournals.org/content/6/3/293.full.pdf
    venson999
        6
    venson999  
    OP
       2013-09-06 17:10:23 +08:00
    @byelims 你说的算法需要两次交换,而Heap的算法只需要一次交换,论文我之前已经看过了,里面好像也并没有说为什么会采用这种区分奇偶的交换方法。我想可能是通过对IndexTable方法优化得来的,但是还是想不明白。
    venson999
        7
    venson999  
    OP
       2013-09-06 17:14:32 +08:00
    @byelims 另外能不能把gist代码去掉呢,github访问不稳定,很影响这个主题的访问速度啊。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2825 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 13:02 · PVG 21:02 · LAX 05:02 · JFK 08:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.