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;
}

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

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