DFS求字典序的排列A(n, r)和组合C(n, r)
作者:
Revui
,
2023-11-08 13:13:00
,
所有人可见
,
阅读 87
输入n, r,求排列
输入:
4 2
输出:
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int path[N];
bool used[N];
int n, r;
void dfs(int depth)
{
if (depth == r)
{
for (int i = 0; i < r; i++) cout << setw(3) << path[i];
cout << '\n';
return;
}
for (int i = 1; i <= n; i++)
{
if (!used[i])
{
used[i] = true;
path[depth] = i;
dfs(depth + 1);
used[i] = false;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> r;
dfs(0);
return 0;
}
输入n, r,求组合
输入:
4 2
输出:
1 2
1 3
1 4
2 3
2 4
3 4
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int path[N];
bool used[N];
int n, r;
void dfs(int depth)
{
if (depth > r)//输出条件为depth == r + 1
{
for (int i = 1; i <= r; i++) cout << setw(3) << path[i];
cout << '\n';
return;
}
for (int i = path[depth - 1] + 1; i <= n; i++)//这里让i从上一个填过的数+1的位置开始枚举
{
if (!used[i])
{
used[i] = true;
path[depth] = i;
dfs(depth + 1);
used[i] = false;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> r;
//depth要从1开始,防止for循环里path[depth - 1]越界,若从0开始,则第一次会访问path[-1],结果是未知的
dfs(1);
return 0;
}