Mach de Bagua    

全排列算法.

遇到一个小问题，需要打印出N（N是变量）个数的全排列。我会的只有递归算法，觉得太土了，就上网找。找到一个号称最经典算法，空间复杂度为O(n), 时间复杂度为O(n2)的:
http://bbs.orsc.edu.cn/bbs/viewthread.php?tid=257&sid=Yksdr1Ps
这个算法根本看不懂。顺便说，最后的那个swap不应该用+-操作来做，安全的做法是用异或(^)，要知道加减法是会溢出的。

我隐隐约约觉得可以用类似把index(从0到N!)转换成类似二进制数的方式来解决，但没想明白，继续搜。

最后在Chinese Python Wiki网站上找到这篇看了很舒服的文章：
http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_ce_cf_b7_bf_aa_ca_bc
："我可以设计这样一个数, ...xyz, 其中个位数 z 是二进位的, 也就是放第二个数的两个位置; 十位数 y 是三进位的, 代表放第三个数字的三个位子, 然后百位数是四进位, 千位数是五进位的, 依以类推." 没错, 这样设计的话, 如果 0 表示放於最左面的话, 则 "2021" 这个数就代表了排列五个元素 (abcde), 取一个 a, 然后第二个 b 放在 a 的右面成 ab, 取 c 放到最右面成为 abc, 取 d 放到最左面成 dabc; 最后 e 放到中间去成为 daebc. 至於 "2021" 这个特别的设计的数可以用 ..+ x*4 + y*3 + z*2 这样的计算来映对到自然数的数列上去."－－真是绝妙！

posted 2004.03.31 Wednesday