来源:《ACM/ICPC代码库 jojer & Fandywang》
搜索问题中有很多本质上就是排列组合问题,只不过加上了某些剪枝和限制条件,解这类题目的基本算法框架常常是类循环排列、全排列、一般组合或全组合,而不重复排列和不重复组合则是两种非常有效的剪枝技巧。
文件PermutationCombination.hpp提供调用接口:
#ifndef __PERMUTATION_COMBINATION__ #define __PERMUTATION_COMBINATION__ void loop_permutation(int l); void full_permutation(int l); void unrepeat_permutation(int l); void select_combination(int l, int p); void full_combination(int l, int p); void unrepeat_combination(int l, int p); #endif
文件PermutationCombination.cpp提供实现,需要在主文件中extern进数组num[]和used[],变量n和m
#include "PermutationCombination.hpp" #include <iostream> using namespace std; #define MAX_N 10 int num[MAX_N]; int used[MAX_N]; int n, m; void loop_permutation(int l) { static int rcd[MAX_N]; int i; if (l == n) { cout << rcd[0]; for (i = 1; i < n; i++) cout << ' ' << rcd[i]; cout << endl; return; } for (i = 0; i < m; i++) { rcd[l] = i; loop_permutation(l + 1); } } /* @code cin >> n; for (i = 0; i < n; i++) cin >> num[i]; full_permutation(0); @endcode */ void full_permutation(int l) { static int rcd[MAX_N]; int i; if (l == n) { cout << rcd[0]; for (i = 1; i < n; i++) cout << ' ' << rcd[i]; cout << endl; return; } for (i = 0; i < n; i++) { if (used[i] == 0) { used[i] = 1; rcd[l] = num[i]; full_permutation(l + 1); used[i] = 0; } } } /* @code int value; cin >> n; m = 0; for (i = 0; i < n; i++) { cin >> value; for (j = 0; j < m; j++) if (num[j] == value) { used[j]++; break; } if (j == m) { num[m] = value; used[m++] = 1; } } unrepeat_permutation(0); @endcode */ void unrepeat_permutation(int l) { static int rcd[MAX_N]; int i; if (l == n) { cout << rcd[0]; for (i = 1; i < n; i++) cout << ' ' << rcd[i]; cout << endl; return; } for (i = 0; i < m; i++) { if (used[i] > 0) { used[i]--; rcd[l] = num[i]; unrepeat_permutation(l + 1); used[i]++; } } } /* @code cin >> n >> m; for (i = 0; i < n; i++) cin >> num[i]; select_combination(0, 0); @endcode */ void select_combination(int l, int p) { static int rcd[MAX_N]; int i; if (l == m) { cout << rcd[0]; for (i = 1; i < m; i++) cout << ' ' << rcd[i]; cout << endl; return; } for (i = p; i < n; i++) { rcd[l] = num[i]; select_combination(l + 1, i + 1); } } /* @code cin >> n; for (i = 0; i < n; i++) cin >> num[i]; full_combination(0, 0); @endcode */ void full_combination(int l, int p) { static int rcd[MAX_N]; int i; for (i = 0; i < l; i++) { cout << rcd[i]; if (i < l - 1) cout << ' '; } cout << endl; for (i = p; i < n; i++) { rcd[l] = num[i]; full_combination(l + 1, i + 1); } } /* @code int value; cin >> n; m = 0; for (i = 0; i < n; i++) { cin >> value; for (j = 0; j < m; j++) if (num[j] == value) { used[j]++; break; } if (j == m) { num[m] = value; used[m++] = 1; } } unrepeat_combination(0, 0); @endcode */ void unrepeat_combination(int l, int p) { static int rcd[MAX_N]; int i; for (i = 0; i < l; i++) { cout << rcd[i]; if (i < l - 1) cout << ' '; } cout << endl; for (i = p; i < m; i++) { if (used[i] > 0) { used[i]--; rcd[l] = num[i]; unrepeat_combination(l + 1, i); used[i]++; } } }