设有a1a2—aKNa1,a2,—,aK为正整数(K2),将a[1],a[2],—,a[K]K个数排列至1,2,—N这N个排列位置上使得a[1],a[2],—,a[K]所占据的排列位置数恰好分别为a1,a2,—,aK这样占据1,2,—NN个排列位置的a[1],a[2],—,a[K]构成的排列为一个排列位置数为N排列数数目为K的多重全排列。现在介绍算法该算法能够生成符合上述要求的所有多重全排列说明以下二种算法仅适用于k2的情形,k1为特殊情形我没有专门处理不处理问题也不大算法一(K3,N5,a12,a21,a32,a[i]i)思路简单代码易于理解代码简单。基本思路为在栈中回溯和向前试探向前试探寻找满足容量上限的下一个候选数从而扩大候选解的规模候选解规模达到N即得到一个多重全排列。无法发现符合容量上限的下一个候选数即回溯C代码#include vector #include iostream using namespace std; const int K 3; const int N 5; int search(int start, const vectorint num, const vectorint count) //从start开始顺序查找满足容量限制的第一个数字查找失败返回0否则返回找到的数字 { for (; start K; start) { if (num[start - 1] 1 count[start - 1]) return start; } return 0; } int main() { vectorint count{ 2, 1, 2 }; //a1,---,ak值 vectorint num(count.size(), 0); //统计循环过程中1,---,k的数目 vectorint arrange(N, 0); //存放找到的多重全排列的栈结构 int i 1; //栈顶指针 int number 0; bool TF true; //回溯标志 while (true) { if (TF false) { if (i 1 arrange[i - 1] K) { break; } --num[arrange[i - 1] - 1]; } int temp; if ((temp search(TF ? 1 : arrange[i - 1] 1, num, count)) 0) { --i; continue; } else { arrange[i - 1] temp; num[temp - 1]; } if (i N) //找到一个多重全排列输出 { number; cout 第 number 个多重全排列:; for (const int m : arrange) { cout m; } cout endl; cout endl; TF false; } else { i; TF true; } } return 0; }运行结果:算法二(K3,N5,a12,a21,a32,a[i]i)代码相对而言更复杂方法较笨就是单纯地模拟手工寻找多重全排列的过程该过程中按a[1],—,a[k]的顺序逐一选择子排列成功找到子排列则向前试探扩大候选解的规模寻找下一个当a[1],—,a[k]的所有子排列全部找到后即获得一个多重全排列当已无新的子排列可供选择时即回溯C代码#include vector #include iostream using namespace std; /*bool find(bool TF, int n, int k, vectorint temp) //TFtrue函数从头寻找满足1a1--akn的第一个排列a1,a2,--,ak存放在temp中 { //TFfalse,函数寻找上一次找到的存放在temp中满足1a1--akn的排列a1,a2,--,ak的下一个排列找到存放在temp中返回true,找不到返回false int i; if (TF true) { if (n k) { for (int i 1; i k; i) { temp[i - 1] i; } return true; } i 0; } else { if (n k) return false; i k - 1; } while (1) { if (i 0) { if (TF true) { temp[i] 1; } else { temp[i]; } if (temp[i] n - k 1) return false; if (k 1) return true; } else { if (TF true) temp[i] temp[i - 1] 1; else { temp[i]; if ((temp[i] - temp[i - 1]) (n - temp[i - 1]) - (k - i) 1) { i--; TF false; continue; } } if (i k - 1) { return true; } } i; TF true; } }*/ void find(int N, int K, vectorvectorint all_comb) { vectorint a(K, 0); bool TF; int i, j; i 0; TF false; j 0; while (1) { if (i 0) { a[i]; if (a[i] N - K 1) break; } else { if (TF false) a[i] a[i - 1] 1; else { a[i]; if ((a[i] - a[i - 1]) (N - a[i - 1]) - (K - i) 1) { i--; TF true; continue; } } } if (i K - 1) { all_comb[j] a; TF true; continue; } i; TF false; } } long long C(long long m, long long n, vectorvectorlong long C_Matrix) { if (m n || n 0) return 1; long long top_left; if (C_Matrix[m - 1][n - 1] ! 0) top_left C_Matrix[m - 1][n - 1]; else { top_left C_Matrix[m - 1][n - 1] C(m - 1, n - 1, C_Matrix); } long long top; if (C_Matrix[m - 1][n] ! 0) top C_Matrix[m - 1][n]; else { top C_Matrix[m - 1][n] C(m - 1, n, C_Matrix); } return top_left top; } struct back { int sub; //存放find函数找到的多重全排列中的一个子排列的排列位置 vectorint father; //存放多重全排列所有N个排列位置被与其对应的sub子排列之前的所有排列占据后剩下的排列位置 back(int k, int f) :sub(k), father(f) {} back() default; }; void diffset(vectorback stack, const vectorint count, const vectorint count_add, int cur_level, vectorvectorvectorint all_combination) //计算father和sub的差集得到sub的下一排列可取得排列位置 { //优化 int i 0; int j 0; int k 0; cur_level - 2; back temp(0, count_add[cur_level]); while (i stack[cur_level].father.size() j all_combination[cur_level][stack[cur_level].sub].size()) { if (i 1 all_combination[cur_level][stack[cur_level].sub][j]) { temp.father[k] stack[cur_level].father[i]; i; } else if (i 1 all_combination[cur_level][stack[cur_level].sub][j]) { j; } else { i; j; } } while (i stack[cur_level].father.size()) { temp.father[k] stack[cur_level].father[i]; i; } stack[cur_level 1] temp; } const int K 3; const int N 5; int main() //C函数vector没写 { vectorint count{ 2, 1, 2 }; //a1,---,ak值 vectorint count_add(count.size() - 1); int m_max N; int n_max count[0]; count_add[0] N - count[0]; for (int i 1; i count.size() - 1; i) { if (m_max count_add[i - 1]) m_max count_add[i - 1]; if (n_max count[i]) n_max count[i]; count_add[i] count_add[i - 1] - count[i]; } if (m_max count_add.back()) m_max count_add.back(); if (n_max count.back()) n_max count.back(); vectorvectorlong long C_Matrix(m_max 1, vectorlong long(n_max 1, 0)); vectorvectorvectorint all_combination(count.size()); all_combination[0] vectorvectorint(C(N, count[0], C_Matrix), vectorint()); find(N, count[0], all_combination[0]); for (size_t i 1; i all_combination.size(); i) { all_combination[i] vectorvectorint(C(count_add[i - 1], count[i], C_Matrix), vectorint()); find(count_add[i - 1], count[i], all_combination[i]); } int i 2; //循环当前正在处理的子排列序号 int num 0; //多重全排列计数 bool TF true; //回溯标志,true前进至本层,false回溯至本层 vectorback stack(count.size()); stack[0] back(0, N); for (int j 1; j N; j) stack[0].father[j - 1] j; while (true) { if (TF true) { diffset(stack, count, count_add, i, all_combination); } else { stack[i - 1].sub; if (stack[i - 1].sub all_combination[i - 1].size()) { if (i 1) break; --i; continue; } } if (i K) //找到一个多重全排列输出 { num; vectorint temp(N, 0); for (vectorback::size_type i 0; i stack.size(); i) { for (vectorint::size_type j 0; j all_combination[i][stack[i].sub].size(); j) { temp[stack[i].father[all_combination[i][stack[i].sub][j] - 1] - 1] i 1; } } cout 第 num 个多重排列:; for (const int m : temp) { cout m; } cout endl; cout endl; TF false; } else { i; TF true; } } return 0; }运行结果