Liuw's Thinkpad

对很多人来说，这样的算法自然是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;
}

前几天写的，动态生成函数。

非Stackless的Python做递归时实在有够慢，而且吃内存太多了。

不幸的是，我刚写完这个函数，就发现用Stackless Python跑原来的程序快得很。浪费时间了。

所以，最后还是用Stackless Python来跑了，不过这个东西还是放上来吧。跑起来比原来的CPython还是快不少的，因为用的都是循环。但是有一个限制，就是循环的最高嵌套数目是20。

# -*- coding: utf-8 -*-
#!/usr/bin/python

# non-recursive combination
# liuw

def MakeCombinationFunction(name, n, k):
    '''
This function returns a function object which will generate indexs
for combination.

name function name
n    total element count
k    take k elements from n, maximum is 20
    '''
    if k > n:
        k = n
    constructs = [('%sfor i%d in xrange(i%d+1, %d):\n'%(' '*(i+1)*4, i+1, i, n),
                   'i%d'%(i+1,))
                  for i in range(k)]
    f, a = map(None, *constructs)
    level = len(constructs)
    f = ' '.join(f)
    source = '    i0 = -1\n' + f + '%syield [%s]' % (' '*4*(level+1), ','.join(a))
    source = 'def %s():\n' % name + source
    scope = {}
    exec source in scope
    return scope[name]

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

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之学习心得。