排列与组合(permutation combination)

一、排列的定义及公式：

从N个不同的元素中，任取M(M与N均为自然数，下同)个元素按照一定的顺序排成一列，叫做从N个不同元素中取出M个元素的一个排列；
从N个不同的元素中取出M个元素的所有排列的个数，叫做从N个不同元素中取出M个元素的一个排列数；公式为：

二、组合的定义及公式

从N个不同的元素中，任取M(M与N均为自然数，下同)个元素组成一组，叫做从N个不同元素中取出M个元素的一个组合；
从N个不同的元素中取出M个元素的所有组合的个数，叫做从N个不同元素中取出M个元素的一个组合数；公式为：

三、圆排列

线性排列时，n 个不同元素可以排列成 n! 种方式。

但是在圆形排列中，旋转视为相同的排列（即：从哪个元素开始走一圈是一样的）。

举个例子：

假设我们有 4 个人 A, B, C, D，要围成一圈坐下。

所有线性排列有：

A B C D 
A B D C 
A C B D 
A C D B ...

一共有 4! 种线性排列。

但围成一圈坐时，下面这些都被认为是同一种圆排列（因为只是起点不同，顺序没变）：

A B C D 
B C D A 
C D A B 
D A B C

它们是同一个环，只是旋转了一下。因此：每种圆排列对应 n种线性排列（起点不同）。

所以数学公式是：

圆排列数= \(\frac{n!}{n} \)= (n – 1)!

不区分顺时针与逆时针

  • 也就是说：只要绕圈顺序相同，不管是顺时针还是逆时针，都算同一种。
  • 例如 A-B-C-D 和 A-D-C-B 被认为是同一种排列。
  • 那么，每个圆排列会被重复计算 两次（一个顺时针，一个逆时针）。
  • 因此公式变为： \(\frac{(n-1)!}{2}\),

三、计算排列及组合的代码实现： 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/****************************************************************
 * C++  计算排列数和组合数
 * date:20222-5-3
 * version: 1.0
 * author: Alex Li
 ****************************************************************/ 

#include <iostream>
using namespace std;
int fact(int n) {
   if (n == 0 || n == 1)
   return 1;
   else
   return n * fact(n - 1);
}
int main() {
   int n, m, comb, per;
   cout<<"Enter N : ";
   cin>>n;
   cout<<"\nEnter M : ";
   cin>>m;
   comb = fact(n) / (fact(m) * fact(n-m));
   cout << "\nCombination : " << comb;
   per = fact(n) / fact(n-m);
   cout << "\nPermutation : " << per;
   return 0;
}

四、给定字符串，输出全排列：

代码实现：方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-01-20 16:45:45
 * 最后修改: 2026-02-20 21:33:06
 * 文件描述: 全排列 原地交换法
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

int n;
int sum;
int a[20];

void dfs(int k){
    if(k == n){
		sum++;
        for(int i=0;i<n;i++)  //输出排列
            cout << a[i];
        cout << "\n";
        return;
    }

    for(int i=k;i<n;i++){
        swap(a[k], a[i]);
        dfs(k+1);
        swap(a[k], a[i]);   // 回溯
    }
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++)
         cin>>a[i];

    dfs(0);
	cout<<"sum="<<sum;  //输出全排列数
}

方法二：DFS+回溯+used

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2026-02-20 21:47:09
 * 最后修改: 2026-02-20 21:52:42
 * 文件描述: 全排列  回溯+used
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

int n;
int sum;
int a[20];        // 输入的原数组
int p[20];        // 当前排列
bool used[20];    // 标记某个位置是否被用过

void dfs(int k){
    if(k == n){    // 注意这里改成 == n
        sum++;
        for(int i=0;i<n;i++)
            cout << p[i] << " ";
        cout << "\n";
        return;
    }

    for(int i=0;i<n;i++){
        if(!used[i]){
            used[i] = true;
            p[k] = a[i];   // 用输入数组
            dfs(k+1);
            used[i] = false;
        }
    }
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i];

    dfs(0);
    cout<<sum;
}

五、取m个元素排列：

只要把递归的停止条件改成k=m即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-07-07 14:15:34
 * 最后修改: 2026-02-20 21:58:10
 * 文件描述: m个元素的排列
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

int n, m,sum;
int a[20];

void dfs(int k){
    if(k == m){  //改成k=m
		sum++;
        for(int i=0;i<m;i++)
            cout << a[i];
        cout << "\n";
        return;
    }

    for(int i=k;i<n;i++){
        swap(a[k], a[i]);
        dfs(k+1);
        swap(a[k], a[i]);
    }
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++)
        a[i] = i+1;

    dfs(0);
	cout<<sum;
}

七、给定n个元素，从中取m个元素，输出组合

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2022-09-01 23:38:31
 * 最后修改: 2026-02-20 22:51:41
 * 文件描述: 组合数+剪枝
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

int n, m,sum;
int a[20];
int chosen[20];

void dfs(int start, int k){
    if(k == m){                     // 选够 m 个
        sum++;
        for(int i=0;i<m;i++)
            cout << chosen[i] << " ";
        cout << "\n";
        return;
    }
    if(n - start < m - k) return;   // 剩下的元素不够选了，提前剪枝
    for(int i=start;i<n;i++){       // 从 start 开始
        chosen[k] = a[i];
        dfs(i+1, k+1);              // 不能回头
    }
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++)
        cin >> a[i];

    dfs(0, 0);
    cout<<sum;
}

洛谷：P1157

Quizzes
Previous Topic
Back to Lesson
Next Quiz