版权申明：本文为博主窗户(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 it
import math
def find_least_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))$时间的算法，不过不在本篇讨论范围之内。
标签：distance,排列,组合,实现,null,perm,next,序列,comb From： https://www.cnblogs.com/Colin-Cai/p/10629908.html