排列和组合的实现
版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址http://www.cnblogs.com/Colin-Cai/p/10629908.html
作者：窗户
QQ/微信：6679072
E-mail：6679072@qq.com 每当学一门计算机语言，质数表、汉诺塔可以作为早期测试的话题之一。随着深入，都很想快速提高一下对这个语言的把握。这个时候，我觉得排列、组合是合适的。不仅排列、组合的程序相对复杂一些，而且在很多问题的解决上，排列、组合往往是解决中的一部分。以下我们的讨论都是针对有限集。
排列
排列，我们这里可以记为$p(s, n)$，代表从一个有限集$s$中选择$n$个元素组成的序列，所有的这样的序列组成的集合。注意，序列在于其有序性，$$和$$就是不同的序列。例如，$p({1,2,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直接可以如下写
perm:: -> Int -> []<br>--表示并集
bigcup = foldl (++) []
perm _ 0 = [[]]
perm s n = bigcup [[(s!!index:e)|e<-perm , k/=index] (n - 1)] | index<-] 最终用小写字母的全排列来演示一下
(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))))) 编译之后可运行，说明了Haskell的惰性计算，否则26个元素的全排列是不可能装的下去，更不可能瞬间计算出来。
Scheme或者其他语言的字典顺序排列可以读者自己实现。
组合的字典顺序
组合的字典顺序依旧问题在如何设计这个next函数。每个下标集合按升序的序列来表示。
那么也是从右往左来找下一个元素，
比如$$选择4个来组合
最开始，序号序列是$$，
....(过程中省略)
再来找$$的下一个
最右边的8无法找到下一个，倒数第二个的7也无法找到下一个，倒数第三个的4找到下一个为5，
最后两个再依次加1补全，得到结果为$$。
还是用Haskell来表示，其他地方都可一致，唯独next'的实现有一点区别：
comb:: -> Int -> []
comb _ 0 = [[]]
comb [] _ = []
comb s n = comb (tail s) n ++ [(head s:x)|x<-comb (tail s) (n - 1)] Scheme或者其他语言的字典顺序排列可以读者自己实现。
排列组合的应用
Python属于很常用的语言，用来做胶水再好不过，从而发展很迅猛，现在被当作是一种很“通俗”的编程语言。我时常会使用里面自带的itertools库。当然，其他语言也可以找到该有的库，没有的话也可以自己来造，以上递归的方式并非唯一，发挥想象可以继续挖掘，但要注意，先生成排列组合的整体再处理很多时候并不现实，因为需要大量的内存，而最终等价于遍历排列组合的每一个结果依次处理价值要大得多。
有了排列组合，某些题目可以暴力完成。比如这样一个题目，给出平面上一堆点，找出距离最近的2个点。
一个很自然的想法就是遍历所有的2点组合，然后找出距离最小的情况，Python代码如下:
(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))))) 以上就是利用排列、组合做的暴力算法，很多时候这样的暴力算法都是一个选择，它意味着遍历所有可能，往往复杂度较大，所以根据数据规模量力而行。另外，以上寻找最短距离的一对点存在$O(n\log (n))$时间的算法，不过不在本篇讨论范围之内。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]