多重排列问题

  1. 输出1-m个数中取n个数的所有多重排列。例如n=2,m=3的所有多重排列为:
1    1
1    2
1    3
2    1
2    2
2    3
3    1
3    2
3    3

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#include <stack>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 25;
int n, m;
int ans[MAXN];
int num[MAXN];

void dfs(int x, int cnt)
{
	if(cnt == n + 1)
	{
		for(int i = 1; i <= n; i++)
		{
			cout << ans[i] << " ";
		}
		cout << endl;
		return;
	}
	for(int i = 1; i <= m; i++)
	{
		ans[cnt] = num[i];
		dfs(i, cnt + 1);
	}
}


int main()
{
	while (cin >> m >> n)
	{
		for(int i = 1; i <= m; i++)
		{
			cin >> num[i];
		}
		dfs(1, 1);
	}
	return 0;
}
  1. 输出1-m个数中取n个数的所有排列。例如n=2,m=3的所有排列为:
1    2
1    3
2    1
2    3
3    1
3    2
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#include <stack>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 25;
int n, m;
int ans[MAXN];
int num[MAXN];
bool vis[MAXN];

void dfs(int x, int cnt)
{
	if(cnt == n + 1)
	{
		for(int i = 1; i <= n; i++)
		{
			cout << ans[i] << " ";
		}
		cout << endl;
		return;
	}
	for(int i = 1; i <= m; i++)
	{
		if(!vis[i])
		{
			vis[i] = true;
			ans[cnt] = num[i];
			dfs(i, cnt + 1);
			vis[i] = false;
		}
	}
}


int main()
{
	while (cin >> m >> n)
	{
		for(int i = 1; i <= m; i++)
		{
			cin >> num[i];
		}
		memset(vis, false, sizeof(vis));
		dfs(1, 1);
	}
	return 0;
}
输出m个数中取n个数的所有组合。例如m=5,n=3的所有组合为:
1      2      3
1      2      4
1      2      5 
1      3      4
1      3      5
1      4      5 
2      3      4
2      3      5
2      4      5 
3      4      5
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#include <stack>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 25;
int n, m;
int ans[MAXN];
int num[MAXN];
bool vis[MAXN];

void dfs(int x, int cnt)
{
	if(cnt == n + 1)
	{
		for(int i = 1; i <= n; i++)
		{
			cout << ans[i] << " ";
		}
		cout << endl;
		return;
	}
	for(int i = x; i <= m; i++)
	{
		if(!vis[i])
		{
			vis[i] = true;
			ans[cnt] = num[i];
			dfs(i, cnt + 1);
			vis[i] = false;
		}
	}
}


int main()
{
	while (cin >> m >> n)
	{
		for(int i = 1; i <= m; i++)
		{
			cin >> num[i];
		}
		memset(vis, false, sizeof(vis));
		dfs(1, 1);
	}
	return 0;
}


原文地址:https://www.cnblogs.com/lgh1992314/p/5835100.html