排列和组合的实现

jdin043

　　版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址　　 http://www.cnblogs.com/Colin-Cai/p/10629908.html　　作者：窗户　　QQ/微信：6679072　　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}{\{<x,y>|y\in p(s-{x},n-1)\}} $
       也就是，当$n \ne 0$时$p(s,n)$分为以$s$各个元素为首元素的序列集合的并集，
       于是用Haskell直接可以如下写
perm::[a] -> Int -> [[a]]
--表示并集bigcup = foldl (++) []perm _ 0 = [[]]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]]
       用Scheme描述可以如下
(define (perm s n)  (define (put-each-to-head s)    (let it ((left s)             (right '())             (r '()))      (if (null? left)          r          (it            (cdr left)            (cons (car left) right)            (cons (append left right) r)))))  (if (zero? n)      '(())      (apply append             (map               (lambda (s2)                 (map                   (lambda (n) (cons (car s2) n))                   (perm (cdr s2) (- n 1))))               (put-each-to-head s)))))
 
　　组合的递归
       组合的递归完成理论上也一样可以有无限多种递归方式。
       假如我们考虑以下的递归方式:
               当$n = 0$时，$c(s,n)=\{\emptyset\}$
               当$n \ne 0 \land s = \emptyset$时，$c(s,n)=\emptyset$
               其他时候，任意取一个$a\in s$，有$c(s,n)=c(s-\{a\},n)\cup \{x\cup\{a\}|x\in c(s-\{a\},n-1)\}$
       用Haskell写作
comb::[a] -> Int -> [[a]]comb _ 0 = [[]]comb [] _ = []comb s n = comb (tail s) n ++ [(head s:x)|x<-comb (tail s) (n - 1)]
       用Scheme可以写作
(define (comb s n)  (cond    ((zero? n)      '(()))    ((null? s)     '())    (else      (append        (map (lambda (x) (cons (car s) x)) (comb (cdr s) (- n 1)))        (comb (cdr s) n)))))
 
　　排列的字典顺序
       字典顺序输出，依次输出的各序列，其每个元素在原来集合(我们用list表示)中的位置(list中的序号)所构成的序列满足字典顺序。
       比如$[1,2,3,4]$,取2个元素构成的排序按字典顺序为$[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]$
       $c(s,n)$第一个序列肯定是序号序列$[0,1...n]$依次所对应的元素组成的序列，问题的关键就在于如何根据当前序列找到下一个序列。
       其实只需要按照从右向左，一个接一个找有没有可以升高的可能，只要有可能，就找到了下一个序列。
       比如我们要从$[a,b,c,d]$中找3个元素的排列：
       最开始，序号序列是$[0,1,2]$，
       要找下一个序号序列时，我们从右往左找，发现最后一个2改成3就可以实现最小的字典顺序跨越，
       所以接下来的序号序列是$[0,1,3]$，
       再从右往左找时,我们发现3时找不到更大的替代了，于是轮到$[0,1]$找，1可以替代为2，得到$[0,2]$，然后最靠前的补全3个的序列，
       得到接下来的序号序列是$[0,2,1]$，
       ......
       字典输出，Scheme可以引入lambda进行惰性计算，R5RS中有delay和force，当然它们可以都是利用lambda进行惰性计算的宏，这样的好处还是不需要生成。而Haskell自身就是惰性的，以下为Haskell的实现，因为计算next用反序比较方便，所以其中next'是反序的，最后生成真实排列的序列才把序列反过来。
perm::[a] -> Int -> [[a]]perm _ 0 = [[]]perm s n = map (\x -> map (s!!) (reverse x)) (dict_seq_rev (length s - 1) n)  where   dict_seq_rev max_index n =     s : remains s       where         s = reverse [0..n-1]         next' s = if null s                   then []                   else                     if null s'                     then                       let s'' = next' (tail s) in                        if null s''                        then []                        else head [x|x<-[0..max_index], not (elem x s'')] : s''                     else head s' : tail s                        where s' = [x|x<-[0..max_index],x>head s,not (elem x s)]         remains s = (\x -> if null x then [] else x : remains x) (next' s)
      最终用小写字母的全排列来演示一下
main = print $perm ['a'..'z'] 26
　　 编译之后可运行，说明了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'的实现有一点区别：
comb::[a] -> Int -> [[a]]comb _ 0 = [[]]comb [] _ = []comb s n = map (\x -> map (s!!) (reverse x)) (dict_seq_rev (length s - 1) n)  where   dict_seq_rev max_index n =     s : remains s       where         s = reverse [0..n-1]         next' s = if null s                   then []                   else                     if head s < max_index - n + length s                     then head s + 1 : tail s                     else let s' = next' (tail s) in                            if null s'                            then []                            else head s' + 1 : s'         remains s = (\x -> if null x then [] else x : remains x) (next' s)
　　Scheme或者其他语言的字典顺序排列可以读者自己实现。
 
　　排列组合的应用
       Python属于很常用的语言，用来做胶水再好不过，从而发展很迅猛，现在被当作是一种很“通俗”的编程语言。我时常会使用里面自带的itertools库。当然，其他语言也可以找到该有的库，没有的话也可以自己来造，以上递归的方式并非唯一，发挥想象可以继续挖掘，但要注意，先生成排列组合的整体再处理很多时候并不现实，因为需要大量的内存，而最终等价于遍历排列组合的每一个结果依次处理价值要大得多。
       有了排列组合，某些题目可以暴力完成。比如这样一个题目，给出平面上一堆点，找出距离最近的2个点。
       一个很自然的想法就是遍历所有的2点组合，然后找出距离最小的情况，Python代码如下:
import itertools as itimport mathdef find_shortest_distance(points):    def distance(p1, p2):        s = (p2[0] - p1[0], p2[1] - p1[1])        return math.sqrt(s[0] ** 2 + s[1] ** 2)    min_distance = None    min_distance_two_points = None    for two_points in it.combinations(points, 2):        d = distance(*two_points)        if min_distance is None or min_distance > d:            min_distance = d            min_distance_two_points = two_points    return (min_distance_two_points, min_distance)
　　以上就是利用排列、组合做的暴力算法，很多时候这样的暴力算法都是一个选择，它意味着遍历所有可能，往往复杂度较大，所以根据数据规模量力而行。另外，以上寻找最短距离的一对点存在$O(n\log (n))$时间的算法，不过不在本篇讨论范围之内。