昨天遇到一个题，求n数组的m组合情况(m<n)
08 Nov 2013
设数组为A(a0,a1,a2,...an),用分治策略：
所有组合情况分两类，要么包含数组第一个元素a0，要么不包含a0.
包含a0的组合的其余m-1个数相当于数组A(a1,a2,...an)的m-1组合；
不包含a0的组合相当于数组A(a1,a2,...an)的m组合。
递归。
递归的结束条件有两种情况：一是m等于1了，二是n等于m了。
1 ;;;;
2 (defun test-combination (n m)
3 (let ((lst NIL))
4 (dotimes (i n)
5 (push (1+ i) lst))
6 (combination-r lst m NIL)))
7
8 (defun combination-r (lst m prefix)
9 (cond
10 ((<= m 1)
11 (loop for x in lst
12 collecting (append prefix (cons x NIL)))))
13 ((= (length lst) m)
14 (cons (append prefix lst) NIL))
15 (t
16 (append (combination-r (cdr lst) (1- m) (append prefix (cons (car lst) NIL)))
17 (combination-r (cdr lst) m prefix)))))
18 ;;;;