Liuw's Thinkpad

最简单的两种排序方式，不多说。

选择排序的第i次循环中选取对应的第i小的数放在list[i]中。

插入排序第次循环把当前待排序的数插入到适当的位置中。

void selection_sort(int *l, int n)
{
	int i, j, tmp, min;

	for (i = 0; i < n-1; i++) {
		min = i;
		for (j = i+1; j < n; j++)
			if (l[j] < l[min])
				min = j;
		tmp = l[min], l[min] = l[i], l[i] = tmp;
	}
}

void insertion_sort(int *l, int n)
{
	int i, j, next;

	for (i = 1; i < n; i++) {
		next = l[i];
		for (j = i-1; j >= 0 && next < l[j]; j--)
			l[j+1] = l[j];
		l[j+1] = next;
	}
}

最大堆可以用一棵完全二叉树来实现，插入和删除都是O(lgn)的复杂度。

插入的时候先把待插入的元素设为树的最后一个叶子，然后由下往上递归处理，每次都比较子节点（初始为最后一个叶子节点）与父节点的键值大小。若父节点的键值较小，那么父节点下移，直到父节点的键值大于子节点，这就是合适的插入位置。这里可以很容易推导出插入位置前面所有的节点的键值都是大于待插入节点的键值的，而插入位置后面所有的节点的键值都是小于待插入节点的键值的。

删除的时候总是删除树的根。通常情况下删除之后堆还需要用最后一个叶子进行进一步的调整。这个调整是自上而下的。递归地扫描每一层，假如某层节点的子节点的键值小于最后一个叶子的键值，那么这个叶子就应该放在这一层；假如某层节点的子节点键值还大于最后一个叶子的键值，那么就进入下一层进行搜索。最后的结果也是符合最大堆的定义的。

下面给出一个数组树实现的最大堆。我原来在想的时候走入了一个误区，认为删除其实和插入所需要的操作是一样的，反正都会往里面插。但是实际上，插入的时候，节点是“下移”，删除的时候，节点是“上移”。所以这两个操作扫描的方向是不一样的。

typedef struct {
	int key;
	/* other fields */
} element;

#define MAX_ELEMENTS 100
element heap[MAX_ELEMENTS];
int n = 0; 			/* heap[0] is never used */

#define HEAP_FULL()  (n == MAX_ELEMENTS-1)
#define HEAP_EMPTY() (!n)

void insert(element item)
{
	int i;

	if (HEAP_FULL()) {
		printf("Heap full\n");
		exit(-1);
	}

	i = ++n;
	while ((i != 1) && (heap[i].key > heap[i/2].key)) {
		heap[i] = heap[i/2]; /* move down */
		i /= 2;
	}

	heap[i] = item;
}

element delete()
{
	element item, temp;
	int child, parent;

	if (HEAP_EMPTY()) {
		printf("Heap empty\n");
		exit(-1);
	}

	item = heap[1];

	/* adjust heap with last element */
	temp = heap[n--];
	parent = 1, child = 2;	/* start from top level */

	while (child <= n) {
		/* find larger child */
		if ((child < n) && heap[child].key < heap[child+1].key)
			child++;
		if (heap[child].key < temp.key) /* found right position */
			break;
		/* move child up */
		heap[parent] = heap[child];
		/* move down to next level */
		parent = child;
		child  = parent * 2;
	}

	heap[parent] = temp;

	return item;
}

最小堆的实现和最大堆类似。

今天下午花了很久的时候做了一个走迷宫的题目。其实这个题目以前上数据结构课的时候都已经写过了，但是再写却又花了很多时间，虽然代码结构和以前写的不一样，但是这却不是最花时间的地方。大部分的时间都花在Debug一些很低级的bug上面，是我状态不好呢，还是写程序实在太烂了呢 Orz。

近来烦心事很多，确实很影响状态。不过就这次的练习来说，还是可以挖出自己很多不好的编程习惯的。总有来说，我要注意：

1. 训练对问题的抽象能力。看到一个问题时，要能够选择出合适的数据结构去把这个问题转化成计算机可以处理的形式。
2. 加强对数据结构的记忆，写逻辑已经先写出数据结构的定义及其上的操作，以后可以方便直接用。
3. 先把问题分析透，用纸笔或者伪代码先把流程写清楚再编码，急于求成只会引入更多的bug。

下面是代码，可以找出所有的路径，很简单哦。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define Z 0
#define E 1
#define S 2
#define W 3
#define N 4
#define F 5

#define MAX_STACK_SIZE 1000

/* 0 means clear, 1 means blocked */
#define X 5
#define Y 4
int maze[X][Y] = {
	{0, 0, 1, 0},
	{1, 0, 0, 1},
	{1, 0, 1, 1},
	{0, 0, 0, 1},
	{1, 0, 0, 0}
};

typedef struct {
	int x, y;
	int direction;
} coord;

int   top = -1;
coord stack[MAX_STACK_SIZE];

#define PUSH(c)						\
	do {						\
		if (++top > MAX_STACK_SIZE) {		\
			printf("Stack overflowed\n");	\
			exit(-1);			\
		}					\
		stack[top] = c;				\
	} while (0)

#define POP(c)						\
	do {						\
		if (top == -1) {			\
			printf("Stack underflowed\n");	\
			exit(-1);			\
		}					\
		c = stack[--top];			\
	} while (0)

#define EMPTY() (top == -1)

#define EQUAL(c1, c2) (c1.x==c2.x && c1.y==c2.y)

#define EXISTS(c) exists(c)

#define IS_VALID_MOVE(c) \
	( !maze11 && c.x >= 0 && c.x < X && c.y >= 0 && c.y < Y )

int exists(coord c)
{
	int i, res = 0;
	for (i = 0; i <= top; ++i) {
		if (EQUAL(stack[i], c)) {
			res = 1;
			break;
		}
	}
	return res;
}

int main()
{
	coord fini_coord = { 4, 3, 0} , start_coord = { 0, 0, 0 };
	int found = 0;
	coord t, t1;
	int i;

	PUSH(start_coord);
	while (!EMPTY()) {
		t = stack[top];
		t1 = t;
		if ((EQUAL(t, fini_coord))) {
			found++;
			printf("Path %d:\n", found);
			for (i = 0; i <= top; i++)
				printf("(%d, %d)\n", stack[i].x, stack[i].y);
			printf("\n\n");
			POP(t1);
			continue;
		}

		switch (t.direction) {
		case Z:
			t.direction = E;
			stack[top] = t;
			t1 = t;
			t1.y += 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);

			break;

		case E:
			t.direction = S;
			stack[top] = t;
			t1 = t;
			t1.x += 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);
			break;

		case S:
			t.direction = W;
			stack[top] = t;
			t1 = t;
			t1.y -= 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);
			break;
		case W:
			t.direction = N;
			stack[top] = t;
			t1 = t;
			t1.x -= 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);
			break;
		case N:
			t.direction = 5;
			stack[top] = t;
			break;
		case F:
			POP(t1);
			break;
		default:
			printf("BUG: unknown direction\n");
			exit(-1);
		}
	}

	if (!found)
		printf("No path found\n");

	return 0;
}

算法这东西，真是常学常新，常学常有啊。今天花了一个下午去理解KMP算法的精髓所在，先写点感受。

定义等匹配的字符串为S长度为m，模式为P长度为n。双循环匹配算法的最坏时间复杂度是O(m*n)，而KMP算法的复杂度为O(m+n)。

分别设定：

S: abdabcabcd
P: abca

P首先要进行预处理，生成next数组的过程是一个P自匹配的过程。next数组的作用是告诉用户，在当前字符匹配失败的时候，P至少需要回退到哪一个位置，直观地理解，这个next数组表现了P自身的相似程度。其实生成next的过程和匹配过程是极其相似的。

让我们先不去管next是怎么生成的，我们先感性地认识一下S和P的匹配过程。

第一步：

i:  0 1 2 3 4 5 6 7 8 9
S:  a b a b b a b c a d
P:  a b c a
j:  0 1 2 3

在i = 2，j = 2的时候失配。在最笨的办法下面，我们是直接把P右移一个位置，即是说i被设置为1，j又被设置为0，重新开始匹配。

i:  0 1 2 3 4 5 6 7 8 9
S:  a b a b b a b c a d
P:    a b c a
j:    0 1 2 3

很明显，这样一次移动一个位置太慢，i回溯了，效率太低。观察一下S，由于S[2] = P[0]，S[3] = P[1]，我们完全可以把P直接右移两个位置，即是从i = 4，j = 2开始比较。

i:  0 1 2 3 4 5 6 7 8 9
S:  a b a b b a b c a d
P:      a b c a
j:      0 1 2 3

可是计算机不是人，不懂怎么去“观察”。所以我们必须生成next数组，告诉计算机在失配的时候应该把j设置为什么，而i不必回溯。

个人觉得这个生成next的过程是整个算法最精彩的部分。我原来在考虑搜索问题时也想到了i的不回溯，但是j该如何设置还没有很好的想法。看到KMP的next生成方法也没能很好地理解，笨啊。

前面我提到过，生成的next数组其实表示的是P自身的相似程度。形式化地定义一个失配函数f：

记模式P=p0p1...p(n-1)
f(j) = i，i为满足i<j且p0p1...pi=p(j-i)p(j-i+1)...pj的最大整数，i>=0
f(j) = -1，其他情况

这个失配函数还有另外一个表达形式：

f(j) = -1，j=0
f(j) = f^m(j-1) + 1，其中m是满足p(f^k(j-1)+1)=pj的最小整数k
f(j) = -1，其他情况

根据这个表达形式，我们可以得到如下的生成next数组的算法：

int lenp = strlen(p);

next[0] = -1; // 这个很好理解。
for (j = 1; j < lenp; j++) {

    i = next[j-1]; // 首先把前一个next值取出来
    /* 在i=-1时，说明前面一元素并非相似模式一部分。但是这个时候j指向的元素也
     * 可能是模式的开始，所以后面还要再作判断。
     * i>=0，若j指向的元素和i+1指向的元素不同，说明自身的相似性已经结束了。
     * 我们需要回溯到前一个模式去。
     */
    while ((p[j] != p[i+1]) && (i >= 0))
        i = next[i];

    if (p[j] == p[i+1])
        next[j] = i + 1;
    else
        next[j] = -1;
}

其中while循环一部分有点绕，还是举个例子实在：

j:     0  1  2  3  4  5  6  7  8  9
P:     a  b  c  d  a  b  c  a  b  d
next: -1 -1 -1 -1  0  1  2  0  1 -1

next的前面4个元素都是-1这自不必多说。在j = 7时，i = next[7] = 2，p[i+1] = ‘d’，发生失配，所以设置i = next[i] = -1，退出循环。

综合起来，整个KMP算法代码如下：

int kmp(const char *s, const char *p)
{
	int i, j, lens=strlen(s), lenp=strlen(p);
	int *next = (int *)malloc(sizeof(int)*lenp);

	next[0] = -1;
	for (j = 1; j < lenp; j++) {
		i = next[j-1];
		while ((p[j] != p[i+1]) && (i >= 0))
			i = next[i];
		if (p[j] == p[i+1])
			next[j] = i + 1;
		else
			next[j] = -1;
	}

	i = j = 0;
	while (i < lens && j < lenp) {
		if (s[i] == p[j])
			i++, j++;
		else if (j == 0)
			i++;
		else
			j = next[j-1] + 1;
	}

	free(next);

	return ( j == lenp ? (i-lenp) : -1 );
}

在匹配过程中，i只会单向增加。

对很多人来说，这样的算法自然是not a big deal。但是我是个算法白痴，好记性不如烂笔头。

其实想法很简单，以排列为例，假如要生成abcd的全排列的话，其实就是：

• 先选出a，然后排列bcd。
• 先选出b，然后排列acd。
• ……

即是说，要生成n个元素的全排列，必须先解决n-1个元素的全排列；要生成n-1个元素的全排列，必须先生成n-2个元素的全排列……

幸运的是，1个元素的全排列实在是太“明显”了。

/* Permutaion and combination in C */

#include <stdio.h>

void swap(char *a, char *b)
{
	char tmp;
	tmp = *a, *a = *b, *b = tmp;
}

/* s: start index
   n: last index, NOTE, not total element number of list!
*/
void perm_aux(char *list, int s, int n)
{
	int i;
	if (s == n) { // 此时已经全部扫描完数组
		for (i = 0; i <= n; ++i)
			printf("%c", list[i]);
		printf("\n");
	}else{
		for (i = s; i <= n; ++i) { // 依次选取从s到n的元素作为此子全排列的第一个元素，然后生成s+1到n子序列的全排列
			swap(&list[s], &list[i]);
			perm_aux(list, s+1, n);
			swap(&list[s], &list[i]);
		}
	}
}

/* permutation for a list with m elements */
void perm(char *list, int m)
{
	perm_aux(list, 0, m-1);
}

void comb_aux(char *list, int d, int n, int m)
{
	int i;
	if (d == n) {
		for (i = 0; i <= n; ++i)
			printf ("%c", list[i]);
		printf("\n");
	}else{
		for (i = d; i <= m; ++i) {
			swap(&list[d], &list[i]);
			comb_aux(list, d+1, n, m);
			swap(&list[d], &list[i]);
		}
	}
}

/* Take n numbers from a set of m numbers */
void comb(char *list, int n, int m)
{
	comb_aux(list, 0, n-1, m-1);
}

int main(int argc, char *argv[])
{
	char l[3] = {'a', 'b', 'c' };
	perm(l, 3);
	comb(l, 2, 3);
	return 0;
}

可以大言不慚地吼著說：“我寫的！”

複用不好，很多冗餘代碼。設計不好，接口不明。寫法丑，不夠Pythonic。

唯一的優點是它確實能解決我的問題。數學建模一個題目“最佳陣容”，要算出所有得分會大于某個特定分數的出場陣容。

其實是一個0-1背包問題，但是約束條件比較多，算法自己又不在行，用回溯剪枝寫不出來。Lingo的規劃又只能做出一個解。

還好，動手算了一下，這個組合數也不過百萬級別，這對於現代的電腦完全是小case。所以用最丑的辦法寫了一個出來，當然，還是有點優化的。

程序我也不打算別人看懂，自己以后估計也不會再看，所以就不多解釋了。放這里做個留念，看看自己寫的程序有多丑。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Author: Liu Wei

def combination(items, n=None):
    if n is None:
        n = len(items)
    for i in xrange(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[i+1:]
            for c in combination(rest, n-1):
                yield v + c

def permutation(items, n=None):
    if n is None:
        n = len(items)
    for i in xrange(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[:i] + items[i+i:]
            for p in permutation(rest, n-1):
                yield v + p

# highest score for each player
scores = [
    [9.4, 9.8, 10, 9.5, 9.4, 9.9, 10, 10, 9.4, 9.7],
    [10, 9.4, 9.5, 9.9, 9.7, 9.9, 10, 10, 9.8, 9.5],
    [9.8, 10, 9.4, 9.7, 9.3, 9.1, 9.3, 9.9, 10, 9.6],
    [9.9, 9.6, 10, 10, 9.9, 9.4, 9.8, 9.8, 9.9, 9.8]
    ]

# final array
array = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]

# sparse array for 6 cols
sparse_array = [
    [0, 0, 0, 0, 0, 0], \
    [0, 0, 0, 0, 0, 0], \
    [0, 0, 0, 0, 0, 0], \
    [0, 0, 0, 0, 0, 0], \
    ]

def __sparse_array_check_valid():
    global sparse_array
    # 6 cols
    for i in xrange(6):
        sum = 0
        for j in xrange(4):
            sum += sparse_array[j][i]
        if sum > 3:
            return False
    return True

def __sparse_array_init():
    global sparse_array
    sparse_array =  [[0, 0, 0, 0, 0, 0], \
                    [0, 0, 0, 0, 0, 0], \
                    [0, 0, 0, 0, 0, 0], \
                    [0, 0, 0, 0, 0, 0], \
                    ]

def __sparse_array_set_row(p, r):
    global sparse_array
    a, b = p
    sparse_array[r][a] = 1
    sparse_array[r][b] = 1

def __sparse_array_clear_row(r):
    global sparse_array
    for i in xrange(len(sparse_array[r])):
        sparse_array[r][i] = 0

def sparse_array_output():
    global sparse_array
    print sparse_array

# generator for sparse arrays
def sparse_array_generator():
    global sparse_array
    # 4 rows
    __sparse_array_init()
    for r0 in combination(range(6), 2):
        __sparse_array_clear_row(0)
        __sparse_array_set_row(r0, 0)
        for r1 in combination(range(6), 2):
            __sparse_array_clear_row(1)
            __sparse_array_set_row(r1, 1)
            for r2 in combination(range(6), 2):
                __sparse_array_clear_row(2)
                __sparse_array_set_row(r2, 2)
                for r3 in combination(range(6), 2):
                    __sparse_array_clear_row(3)
                    __sparse_array_set_row(r3, 3)

                    if __sparse_array_check_valid():
                        yield sparse_array
                    #    sparse_array_output()

def __array_set_col(c):
    global array
    for i in xrange(len(array)):
        array[i]1 = 1

def __array_clean_col(c):
    global array
    for i in xrange(len(array)):
        array[i]1 = 0

def __array_init():
    global array
    array = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        ]

def set_allround_player(a):
    for i in a:
        __array_set_col(i)

def set_individual_player(sa, s):
    global array
    for i in range(4):
        for j in range(6):
            array[i][s[j]] = sa[i][j]

def array_generator():
    global array
    for g in combination(range(10), 4):
        # select cols for sparse array in big array
        s = [i for i in range(10) if i not in g]
        __array_init();
        # start to manipulate the array
        # first select all-round player
        set_allround_player(g)
        # then cope with individual event player
        for sa in sparse_array_generator():
            set_individual_player(sa, s)
            yield array

def calc_score(a):
    sum = 0
    for i in range(len(a)):
        for j in range(len(a[0])):
            sum += a[i][j] * scores[i][j]
    return sum

def final_generator():
    for a in array_generator():
        total_score = calc_score(a)
        if total_score >= 236.2:
            yield [a, total_score]

import os
os.chdir("d:/liuw/")
f = file("output", 'a')
for solution, total_score in final_generator():
    f.write(str(solution))
    f.write('\n')
    f.write(str(total_score))
    f.write('\n\n')
f.close()

用到了大量的generator，因為怕會內存不足。但是總yield一個全局數組總覺得有點別扭。話說我們這次的做題目用到了Lingo、Python、Matlab和C，果然是程序員的命，全部學計算機的人組個隊還是有好處的。

最後在電腦上跑了5分鐘左右，結果就出來了。假如想再快點，還可以做雙核並行計算。不過自己這方面沒什麽研究，程序也要得比較急，就沒有多管。

看到很多散列表（hash table）的实现中，长度都是一个素数。至于为什么一定要用素数，一下子也没想出所以然来。上网搜索了一下相关的文章，发现很多人也在讨论这个问题。

http://www.cs.unm.edu/~saia/numtheory.html

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth-2

http://blog.csdn.net/ilibaba/archive/2009/03/05/3960142.aspx

长度是否要是素数，能不能是合数，这个问题大家的意见得不到统一。支持用素数的人的理由是，素数可以使得散列的分布更加均匀。

自己总结一下看这些文章的心得。一个散列运算可以等价如下式：

hash(k) = mix(k) mod m

散列计算中，求余往往是最后一步，因为没有机器拥有无限的内存，所以必须把结果放入到有限的桶（bucket）中。求余前的运算，假如混淆（mix）得比较好的话，那么m使用素数还是合数，分布是一样的。假如混淆（mix）得不够好的话，那么一个素数可以把一些common pattern加以区别。至于什么样的数据混淆用什么样的mix算法比较好，这个得经统计才可以得出结论。总的来讲，使用一个素数总没有错，虽然运行慢了点，却可以得到相对较好的统计特性。个人看法。

Knuth的The Art of Computer Programming中，也用的是一样的理由推荐用素数的m。手上没有书，他应该没有提到合数的问题。上面也仅仅是我个人的一些想法，没有经过严格的证明，我也没有能力去证明。当然，很欢迎有人来指正我的错误。

手上有《算法导论》，第十一章散列表，对这个问题也没有给出严格的证明。但是它提到这样的一个问题，若m=2^p-1，则所有以2^p为基数的解释的字符串，无论字符位置怎么变化，得出的散列值都是一样的。这个证明比较简单，用同余的性质就可以证明，最后的值，其实是各个字符值的和再对m取余，所以散列值不会随字符的位置发生变化。

UPDATE：

StackOverflow上也有对这个问题的讨论。

http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus

上面的文章的观点和我总结出来的基本一致。

中文实在不清楚Process和Procedure如何进行区别，所以题目写了英文。

SICP习题1.11

A function f is defined by the rule that f(n) = n if n = 3 and f(n) = f(n-1) + 2f(n-2) + 3f(n-3) if n >= 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an interative process

SICP中已经给了一个例子，把linear recursive转化为iterative。后面一个要求其实是要把tree recursive进行转化。

好吧，递归的很简单。

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

我比较笨点，迭代的想了好久，写出来个挺锉的。

(define (f n)
  (if (< n 3)
      n
      (f-aux  4 2 1 0 3 n)))

(define (f-aux product a b c count n)
  (if (> count n)
      product
      (f-aux (+ a (* 2 b) (* 3 c))
             (+ a (* 2 b) (* 3 c))
             a
             b
             (+ count 1)
             n)))

这个代码是有冗余的。并不需要专门用一个product去记录结果。写出这样的代码，其实是对“迭代”理解得还不够深刻。改进后的代码是这样的。

(define (f n)
  (if (< n 3)
      n
      (f-aux  4 2 1 2 n)))

(define (f-aux a b c count n)
  (if (> count n)
      c
      (f-aux (+ a (* 2 b) (* 3 c))
             a
             b
             (+ count 1)
             n)))

count并不是必要的，可以直接用n自减到0即可。

ChinaUnix的win_hate也给出了一个版本。我改写了一下，好看点。

(define (g n)
  (g-aux 0 1 2 n))

(define (g-aux x y z n)
  (if (= 0 n)
      x
      (g-aux y z (+ (* 3 x) (* 2 y) z) (- n 1))))

但是这个版本的定义域默认是非负整数，我觉得这是不合适的，因为题目中没有明确指出这一点。

总结一下，有几点比较有意思的：

1. 线性递归和树形递归的尾递归情况，可以转化为迭代，其他情况未考究；
2. 转化时，关键是总结出各个参数的关系，没有必要使用专门的参数去记录结果；
3. 理解迭代的关键点是，每一时刻参数都保持有函数进一步运算的必要信息，而递归把这些信息放在了栈上，由系统隐式操作。

昨天做东西的时候用到这个了。转过来的，觉得不错先记下了。

def comb(items, n=None):
    if n is None:
        n = len(items)
    for i in range(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[i+1:]
            for c in comb(rest, n-1):
                yield v + c

def perm(items, n=None):
    if n is None:
        n = len(items)
    for i in range(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[:i] + items[i+1:]
            for p in perm(rest, n-1):
                yield v + p

yield这个关键字，可以看一下limodou的一[Python 学习]2.5版yield之学习心得。

qsort([]) ->
    [];
qsort([Pivot|T]) ->
    qsort([X || X <- T, X < Pivot])
    ++Pivot++
    qsort([X || X <- T, X >= Pivot]).

用到了list comprehension，很好的功能。