组合数学 (二): 排列组合

本是古典何须时尚 2022-02-21 14:54 328阅读 0赞

### 排列组合 ###

*  公式
 *   *  排列
     *  组合
 *  代码
 *   *  输出所有排列
     *  错位排列
 *  输出所有组合

# 公式 #

## 排列 ##

从 M 个数中有序地拿出 N 个数的方案数为

P M N = M ! ( M − N ) ! P\_M^N=\\frac\{M!\}\{(M-N)!\} PMN=(M−N)!M!

简单解释就是: M 个数的全排列个数为  M ! M! M!, 如果拿出 N 个数, 那么就要去掉多出来的所有排列, 所以就要除以  ( M − N ) ! (M-N)! (M−N)!

## 组合 ##

从 M 个数中**不计顺序**地拿出 N 个数的方案数为

C M N = M ! N ! ( M − N ) ! C\_M^N=\\frac\{M!\}\{N!(M-N)!\} CMN=N!(M−N)!M!

我认为也比较好理解, 在相同 M, N 的条件下, 组合就是不计顺序的排列, 所以组合的个数就是排列的个数除以排列的方案, 因此也就是  C M N = P M N N ! C\_M^N=\\frac\{P\_M^N\}\{N!\} CMN=N!PMN

# 代码 #

## 输出所有排列 ##

给定 M 和 N, 输出一个长为 M 的数组的所有排列, 可以用递归的方式解决:  
递归一共有 N 层, 第 i 递归会选择第 i 个位置的输出, 显然如果某个位置在之前已经被选过了, 那么它就不能再被选.  
C 代码如下

#include <stdio.h>
    #define MAXN 100
    
    // 从 M 个数中选出 N 个数来排列
    int M, N;
    
    // 用来存放数据
    int array[MAXN];
    
    // 用来缓存输出
    int buffer[MAXN];
    
    // 用来表示这个位置是否已经被用过
    int flag[MAXN];
    
    // 输出缓存中的 N 个数
    void out() { 
    	for (int i = 0; i < N; i++) { 
    		printf("%d ", buffer[i]);
    	}
    	printf("\n");
    }
    
    // 递归进行排列, 其中 pos 表示当前要选择的位置
    void perm(int pos) { 
    	for (int i = 0; i < M; i++) { 
    		// 如果这个位置已经被标记过, 就 continue, 否则标记这个位置
    		if (flag[i]) continue;
    		flag[i] = 1;
    		buffer[pos] = array[i];
    		// 如果到底了, 就输出, 否则进行下一层递归
    		if (pos == (N-1)) { 
    			out();
    		} else { 
    			perm(pos+1);
    		}
    		// 释放标记
    		flag[i] = 0;
    	}
    }
    
    int main() { 
    	scanf("%d %d" &M, &N);
    	for (int i = 0; i < M; i++) { 
    		scanf("%d", array + i);
    	}
    	perm(0);
    }

## 错位排列 ##

错位排列和上面的区别是, 排列的第 i 个数字不能是原本的第 i 个数字.  
**只需要在上面的代码中再加一行代码就行了**

#include <stdio.h>
    #define MAXM 100
    
    int M, N;
    int array[MAXM];
    int buffer[MAXM];
    int flag[MAXM];
    
    void perm(int pos) { 
    	for (int i = 0; i < M; i++) { 
    		if (flag[i]) continue;
    		// 加下面这一行
    		if (i == pos) continue;
    		flag[i] = 1;
    		buffer[pos] = array[i];
    
    		if (pos == (N - 1)) { 
    			for (int j = 0; j < N; j++) { 
    				printf("%d ", buffer[j]);
    			}
    			printf("\n");
    		} else { 
    			perm(pos + 1);
    		}
    
    		flag[i] = 0;
    	}
    }
    
    int main() { 
    	scanf("%d %d" &M, &N);
    	for (int i = 0; i < M; i++) { 
    		scanf("%d", array + i);
    	}
    	perm(0);
    }

# 输出所有组合 #

从 M 个数中选取 N 个数, 假如我们知道 N, 比如 N = 2, 那么我们可以写一个二层 for 循环:

for (int i = 0; i < M; i++) { 
    	for (int j = i+1; j < M; j++) { 
    	}
    }

即可输出所有组合.  
因此, 我们可以用递归的方式来做到对任意的 N 进行组合:

#include <stdio.h>
    #define MAXM 100
    
    int M, N;
    int array[MAXM];
    int buffer[MAXM];
    
    void combo(int pos, int from) { 
    	// 从 from 开始遍历, from 的值是上一层递归的 i + 1
    	for (int i = from; i < M; i++) { 
    		buffer[pos] = array[i];
    		// 如果递归到底了, 输出, 否则下一层递归
    		if (pos == (N - 1)) { 
    			for (int j = 0; j < N; j++) { 
    				printf("%d ", buffer[j]);
    			}
    			printf("\n");
    		} else { 
    			combo(pos + 1, i + 1);
    		}
    	}
    }
    
    int main() { 
    	scanf("%d %d" &M, &N);
    	for (int i = 0; i < M; i++) { 
    		scanf("%d", array + i);
    	}
    	combo(0, 0);
    }