排列组合

排列(permutation)

排列 - 从 n 个不同的元素中取出 m(1≤m≤n)个不同的元素,按照一定的顺序排成一列,这个过程就叫排列

全排列 - 当 m=n 这种特殊情况出现的时候,比如说,在田忌赛马的故事中,田忌的三匹马必须全部出战

如果选择出的这 m 个元素可以有重复的,这样的排列就是为重复排列(Permutation with Repetition),否则就是不重复排列(Permutation without Repetition)


1.对于 n 个元素的全排列,所有可能的排列数量就是 nx(n-1)x(n-2)x…x2x1,也就是 n!(n的阶乘);

2.对于 n 个元素里取出 m(0<m≤n) 个元素的不重复排列数量是 nx(n-1)x(n-2)x…x(n - m + 1),也就是 n!/(n-m)!。


linux c例子1-全排列

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

void swap(char *x, char *y) 
{
    if (x == y) return;
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

void permute(char *a, int l, int r) 
{ 
   int i; 
   if (l == r) 
     printf("%s\n", a); 
   else
   { 
       for (i = l; i <= r; i++) 
       { 
          swap((a+l), (a+i)); 
          permute(a, l+1, r); 
          swap((a+l), (a+i)); //backtrack 
       } 
   } 
} 

int main() 
{ 
    char str[] = "ABC"; 
    int n = strlen(str); 
    permute(str, 0, n-1); 
    return 0; 
}
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 
ABC ACB BAC BCA CBA CAB


linux c例子2-非全排列

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

void swap(char *x, char *y) 
{
    if (x == y) return;
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

void permute(char *a, int l, int r, int n) 
{ 
    int  i;
    char c;
    if (l == n) {
        c = a[n];
        a[n] = 0;
        printf("%s ", a);
        a[n] = c;
    
    } else { 
       for (i = l; i <= r; i++) 
       { 
          swap((a+l), (a+i));
          permute(a, l+1, r, n); 
          swap((a+l), (a+i)); //backtrack 
       } 
   } 
} 

int main() 
{ 
    char str[] = "ABCD"; 
    int n = strlen(str); 
    permute(str, 0, n-1, 2);
    printf("\n");
    return 0; 
}
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 
AB AC AD BA BC BD CB CA CD DB DC DA



“田忌赛马”的故事我想你肯定听过吧?田忌是齐国有名的将领,他常常和齐王赛马,可是总是败下阵来,心中非常不悦。孙膑想帮田忌一把。他把这些马分为上、中、下三等。他让田忌用自己的下等马来应战齐王的上等马,用上等马应战齐王的中等马,用中等马应战齐王的下等马。三场比赛结束后,田忌只输了第一场,赢了后面两场,最终赢得与齐王的整场比赛。孙膑每次都从田忌的马匹中挑选出一匹,一共进行三次,排列出战的顺序。是不是感觉这个过程很熟悉?这其实就是数学中的排列过程 

linux c例子3

这里我们假设 a b c 分别为田忌的上 中 下 等马,A B C 代表齐王的上 中 下马匹

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

typedef unsigned char uchar;

typedef struct {
	uchar 	name;		//马名字
} horse;

typedef struct {
	horse 	arr[3];		//存放马
	int 	h_num;		//马数目
} horses;

typedef struct {
	horses 	*permu[6];
	int 	num;
} hs_permu;

uchar time_map[256];

void horse_init()
{
	//设置田忌上中下等马跑完全程需要的时间 5s 10s 15s
	time_map['a'] = 5;
	time_map['b'] = 10;
	time_map['c'] = 15;

	//齐王上中下等马时间 4s 9s 14s
	time_map['A'] = 4;
	time_map['B'] = 9;
	time_map['C'] = 14;
}

horses 	*tianji_permu[6];
int 	tianji_num;

horses *h_copy(horses *h1)
{
	int 	i;
	horses 	*h2;

	h2 = malloc(sizeof(horses));
	for (i = 0; i < h1->h_num; i++) {
		h2->arr[i] = h1->arr[i];
	}

	h2->h_num = h1->h_num;

	return h2;
}

void h_add(horses *hs3, horse *h1)
{
	hs3->arr[hs3->h_num++] = *h1;
}

void h_del(horses *hs3, horse *h1)
{
	horses 	*hs;
	int 	i, n;
	
	n = 0;
	hs = hs3;
	
	for (i = 0; i < hs3->h_num; i++) {
		if (hs3->arr[i].name == h1->name)
			continue;

		hs->arr[n++] = hs3->arr[i];
	}

	hs->h_num = n;
}

void permutation(hs_permu *hsp, horses *hs1, horses *hs2)
{
	int 	i;
	horses 	*hs3, *hs4;

	if (hs1->h_num == 0) {
		//全部马已经出战,完成一次排列
		hsp->permu[hsp->num++] = hs2;
		return;
	}

	for (i = 0; i < hs1->h_num; i++) {
		hs4 = h_copy(hs2);
		h_add(hs4, &hs1->arr[i]);

		hs3 = h_copy(hs1);
		h_del(hs3, &hs1->arr[i]);

		permutation(hsp, hs3, hs4);
	}

}

//打印排列组合
void dump_permutation(hs_permu *hsp)
{
	int 	i, j;
	horses 	*hs;

	for (i = 0; i < hsp->num; i++) {
		hs = hsp->permu[i];

		printf("[");
		for (j = 0; j < hs->h_num; j++) {
			printf("%c,", hs->arr[j].name);
		}
		printf("]\n");
	}
}

//打印一次组合
void dump_horses(horses *hs)
{
	int j;

	printf("[");
	for (j = 0; j < hs->h_num; j++) {
		printf("%c,", hs->arr[j].name);
	}
	printf("]\n");
}

int compare(horses *tjh, horses *qwh)
{
	int 	i, tj_win_num;

	tj_win_num = 0;

	for (i = 0; i < 3; i++) {
		//printf("%c-%d %c-%d ", tjh->arr[i].name, time_map[tjh->arr[i].name], qwh->arr[i].name, time_map[qwh->arr[i].name]);
		if (time_map[tjh->arr[i].name] < time_map[qwh->arr[i].name])
			tj_win_num++;
		else
			tj_win_num--;
	}

	return tj_win_num;
}

void compare_and_dump(hs_permu *tianji_permu, hs_permu *qiwang_permu)
{
	int 	i,j;
	horses 	*tjh, *qwh;

	for (i = 0; i < tianji_permu->num; i++) {
		for (j = 0; j < qiwang_permu->num; j++) {
			tjh = tianji_permu->permu[i];
			qwh = qiwang_permu->permu[j];

			if (compare(tjh, qwh) > 0) {
				dump_horses(tjh);
				dump_horses(qwh);
				printf("\n");
			}

		}
	}

}

int main()
{
	horse_init();

	//田忌
	hs_permu 	tianji_permu;
	tianji_permu.num = 0;
	

	horses 	*tianji_hs = malloc(sizeof(horses));
	tianji_hs->h_num = 3;
	tianji_hs->arr[0].name = 'a';
	tianji_hs->arr[1].name = 'b';
	tianji_hs->arr[2].name = 'c';

	horses 	*result = malloc(sizeof(horses));
	result->h_num = 0;

	permutation(&tianji_permu, tianji_hs, result);
	printf("tianji-num: %d\n", tianji_permu.num);
	dump_permutation(&tianji_permu);


	//齐王
	hs_permu 	qiwang_permu;
	qiwang_permu.num = 0;

	horses 	*qiwang_hs = malloc(sizeof(horses));
	qiwang_hs->h_num = 3;
	qiwang_hs->arr[0].name = 'A';
	qiwang_hs->arr[1].name = 'B';
	qiwang_hs->arr[2].name = 'C';

	result = malloc(sizeof(horses));
	result->h_num = 0;

	permutation(&qiwang_permu, qiwang_hs, result);
	printf("qiwang-num: %d\n", qiwang_permu.num);
	dump_permutation(&qiwang_permu);

	//查找田忌赢的排列
	printf("\n\n[tianji win permutation]\n");
	compare_and_dump(&tianji_permu, &qiwang_permu);

	return 0;
}
[root@izbp1irxwqt7ei21awv6wvz ccc]# ./a.out 
tianji-num: 6
[a,b,c,]
[a,c,b,]
[b,a,c,]
[b,c,a,]
[c,a,b,]
[c,b,a,]
qiwang-num: 6
[A,B,C,]
[A,C,B,]
[B,A,C,]
[B,C,A,]
[C,A,B,]
[C,B,A,]


[tianji win permutation]
[a,b,c,]
[B,C,A,]

[a,c,b,]
[B,A,C,]

[b,a,c,]
[C,B,A,]

[b,c,a,]
[C,A,B,]

[c,a,b,]
[A,B,C,]

[c,b,a,]
[A,C,B,]

其实暴力破解也是基于排列组合


组合(combination)

组合可以说是排列的兄弟,两者类似但又有所不同,那就是,组合是不考虑每个元素出现的顺序

从定义上来说,组合是指,从 n 个不同元素中取出 m(1≤m≤n)个不同的元素

田忌赛马的规则改一下,改为从 10 匹马里挑出 3 匹比赛,但是并不关心这 3 匹马的出战顺序,那么也是一个组合的问题

对于所有 m 取值的组合之全集合,我们可以叫作全组合(All Combination)。例如对于集合{1, 2, 3}而言,全组合 - {空集, {1}, {2}, {3}, {1, 2}, {1,3} {2, 3}, {1, 2, 3}}


1.n 个元素里取出 m 个的组合,可能性数量就是 n 个里取 m 个的排列数量,除以 m 个全排列的数量,也就是 (n! / (n-m)!) / m!

2.对于全组合而言,可能性为 2^n 种。例如,当 n=3 的时候,全组合包括了 8 种情况

比如从 1,2,3,4,5 中取出 3 个来组合,首先求出全排列 5! / (5 - 3)!,而那么多的排列里每 3! 个排列都属于一个组合所以得除以6


下面是 linux c语言实现的组合例子

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

typedef unsigned char uchar;

typedef struct {
	uchar 	name;		//马名字
} horse;

typedef struct {
	horse 	arr[6];		//存放马
	int 	h_num;		//马数目
} horses;

typedef struct {
	horses 	*com[1024];
	int 	num;
} hs_com;

hs_com 		*com_g;


horses *h_copy(horses *h1)
{
	int 	i;
	horses 	*h2;

	h2 = malloc(sizeof(horses));
	for (i = 0; i < h1->h_num; i++) {
		h2->arr[i] = h1->arr[i];
	}

	h2->h_num = h1->h_num;

	return h2;
}

void h_add(horses *hs3, horse *h1)
{
	hs3->arr[hs3->h_num++] = *h1;
}

void h_del(horses *hs3, horse *h1)
{
	horses 	*hs;
	int 	i, n;
	
	n = 0;
	hs = hs3;
	
	for (i = 0; i < hs3->h_num; i++) {
		if (hs3->arr[i].name == h1->name)
			continue;

		hs->arr[n++] = hs3->arr[i];
	}

	hs->h_num = n;
}

void combination(horses *hs1, horses *hs2, int num)
{
	int 	i, n;
	horses 	*hs3, *hs4;

	if (hs2->h_num == num) {
		//完成了组合
		com_g->com[com_g->num++] = h_copy(hs2);;
		return;
	}

	if (hs1->h_num == 0)
		return;

	n = hs1->h_num;

	for (i = 0; i < n; i++) {
		hs4 = h_copy(hs2);
		h_add(hs4, &hs1->arr[0]);

		h_del(hs1, &hs1->arr[0]);

		hs3 = h_copy(hs1);
		combination(hs3, hs4, num);
	}

	free(hs3);
	free(hs4);
}

//打印排列组合
void dump_combination(hs_com *hsp)
{
	int 	i, j;
	horses 	*hs;

	for (i = 0; i < hsp->num; i++) {
		hs = hsp->com[i];

		printf("[");
		for (j = 0; j < hs->h_num; j++) {
			printf("%c,", hs->arr[j].name);
		}
		printf("]\n");
	}
}


int main(int argc, char **argv)
{
	int 	num;
	horses 	*hs_g, *res;

	if (argc != 2) {
		printf("./a.out [1-6]\n");
		return 1;
	}

	num = atoi(argv[1]);
	if (num < 1 || num > 6) {
		printf("./a.out [1-6]\n");
		return 1;
	}

	com_g = calloc(sizeof(hs_com), 1);
	hs_g = calloc(sizeof(horses), 1);
	res = calloc(sizeof(horses), 1);

	hs_g->arr[0].name = 'a';
	hs_g->arr[1].name = 'b';
	hs_g->arr[2].name = 'c';
	hs_g->arr[3].name = 'd';
	hs_g->arr[4].name = 'e';
	hs_g->arr[5].name = 'f';
	hs_g->h_num = 6;

	combination(hs_g, res, num);

	dump_combination(com_g);
	return 0;
}
[root@dldl ccc]# ./a.out 1
[a,]
[b,]
[c,]
[d,]
[e,]
[f,]
[root@dldl ccc]# ./a.out 2
[a,b,]
[a,c,]
[a,d,]
[a,e,]
[a,f,]
[b,c,]
[b,d,]
[b,e,]
[b,f,]
[c,d,]
[c,e,]
[c,f,]
[d,e,]
[d,f,]
[e,f,]
[root@dldl ccc]# ./a.out 3
[a,b,c,]
[a,b,d,]
[a,b,e,]
[a,b,f,]
[a,c,d,]
[a,c,e,]
[a,c,f,]
[a,d,e,]
[a,d,f,]
[a,e,f,]
[b,c,d,]
[b,c,e,]
[b,c,f,]
[b,d,e,]
[b,d,f,]
[b,e,f,]
[c,d,e,]
[c,d,f,]
[c,e,f,]
[d,e,f,]
[root@dldl ccc]# ./a.out 6
[a,b,c,d,e,f,]
#n = 6,m = 1
n!/(n-m)/1! = 6/1 = 6

#n = 6,m = 2
n!/(n-2)!/2! = 15

#n = 6,m = 3
n!/(n-3)!/3! = 20

#n = 6,m = 6
n!/(n-6)!/6! = 1




上一篇: 迭代法、数学归纳法、递归
下一篇: 渐进记法
作者邮箱: 203328517@qq.com