排列和组合的实现

1. 　　版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址
3. 　　 http://www.cnblogs.com/Colin-Cai/p/10629908.html
5. 　　作者：窗户
7. 　　QQ/微信：6679072
9. 　　E-mail：6679072@qq.com

复制代码

　　每当学一门计算机语言，质数表、汉诺塔可以作为早期测试的话题之一。随着深入，都很想快速提高一下对这个语言的把握。这个时候，我觉得排列、组合是合适的。不仅排列、组合的程序相对复杂一些，而且在很多问题的解决上，排列、组合往往是解决中的一部分。以下我们的讨论都是针对有限集。
 
　　排列
       排列，我们这里可以记为$p(s, n)$，代表从一个有限集$s$中选择$n$个元素组成的序列，所有的这样的序列组成的集合。注意，序列在于其有序性，$[1,2,3]$和$[1,3,2]$就是不同的序列。例如，$p({1,2,3}, 2)$所代表的集合是${[1,2], [2,1], [1,3], [3,1], [2,3],[3,2]}$。
 
　　组合
       组合，我们这里可以记为$c(s, n)$，代表从一个有限集$s$中选择$n$个元素组成的集合，所有的这样的集合组成的集合。例如，$c({1,2,3}, 2)$所代表的集合是${{1,2}, {1, 3}, {2,3}}$。
 
　　递归完成排列
       排列的递归完成理论上可以有无限多种递归方式。
       比如我们可以考虑这样的方式来递归：
               当$n = 0$时，$p(s,n) = \{\emptyset\}$
               当$n \ne 0$时，$p(s,n) = \bigcup_{x\in s}{\{|y\in p(s-{x},n-1)\}} $
       也就是，当$n \ne 0$时$p(s,n)$分为以$s$各个元素为首元素的序列集合的并集，
       于是用Haskell直接可以如下写

1. perm::[a] -> Int -> [[a]]<br>--表示并集
2. bigcup = foldl (++) []
3. perm _ 0 = [[]]
4. perm s n = bigcup [[(s!!index:e)|e<-perm [s!!k|k<-[0..length s - 1], k/=index] (n - 1)] | index<-[0..length s - 1]]

复制代码

      最终用小写字母的全排列来演示一下

1. (define (perm s n)
2.   (define (put-each-to-head s)
3.     (let it ((left s)
4.              (right '())
5.              (r '()))
6.       (if (null? left)
7.           r
8.           (it
9.             (cdr left)
10.             (cons (car left) right)
11.             (cons (append left right) r)))))
12.   (if (zero? n)
13.       '(())
14.       (apply append
15.              (map
16.                (lambda (s2)
17.                  (map
18.                    (lambda (n) (cons (car s2) n))
19.                    (perm (cdr s2) (- n 1))))
20.                (put-each-to-head s)))))

复制代码

　　 编译之后可运行，说明了Haskell的惰性计算，否则26个元素的全排列是不可能装的下去，更不可能瞬间计算出来。
 　　Scheme或者其他语言的字典顺序排列可以读者自己实现。
 
　　组合的字典顺序
       组合的字典顺序依旧问题在如何设计这个next函数。每个下标集合按升序的序列来表示。
       那么也是从右往左来找下一个元素，
       比如$[0..8]$选择4个来组合
       最开始，序号序列是$[0,1,2,3]$，
        ....(过程中省略)
       再来找$[2,4,7,8]$的下一个
       最右边的8无法找到下一个，倒数第二个的7也无法找到下一个，倒数第三个的4找到下一个为5，
       最后两个再依次加1补全，得到结果为$[2,5,6,7]$。
       还是用Haskell来表示，其他地方都可一致，唯独next'的实现有一点区别：

1. comb::[a] -> Int -> [[a]]
2. comb _ 0 = [[]]
3. comb [] _ = []
4. comb s n = comb (tail s) n ++ [(head s:x)|x<-comb (tail s) (n - 1)]

复制代码

　　Scheme或者其他语言的字典顺序排列可以读者自己实现。
 
　　排列组合的应用
       Python属于很常用的语言，用来做胶水再好不过，从而发展很迅猛，现在被当作是一种很“通俗”的编程语言。我时常会使用里面自带的itertools库。当然，其他语言也可以找到该有的库，没有的话也可以自己来造，以上递归的方式并非唯一，发挥想象可以继续挖掘，但要注意，先生成排列组合的整体再处理很多时候并不现实，因为需要大量的内存，而最终等价于遍历排列组合的每一个结果依次处理价值要大得多。
       有了排列组合，某些题目可以暴力完成。比如这样一个题目，给出平面上一堆点，找出距离最近的2个点。
       一个很自然的想法就是遍历所有的2点组合，然后找出距离最小的情况，Python代码如下:

1. (define (comb s n)
2.   (cond
3.     ((zero? n)
4.       '(()))
5.     ((null? s)
6.      '())
7.     (else
8.       (append
9.         (map (lambda (x) (cons (car s) x)) (comb (cdr s) (- n 1)))
10.         (comb (cdr s) n)))))

复制代码

　　以上就是利用排列、组合做的暴力算法，很多时候这样的暴力算法都是一个选择，它意味着遍历所有可能，往往复杂度较大，所以根据数据规模量力而行。另外，以上寻找最短距离的一对点存在$O(n\log (n))$时间的算法，不过不在本篇讨论范围之内。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！