设有a1+a2+—+aK=N,a1,a2,—,aK为正整数(K>=2),将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的多重全排列。
现在介绍算法,该算法能够生成符合上述要求的所有多重全排列
说明:以下二种算法仅适用于k>=2的情形,k=1为特殊情形我没有专门处理,不处理问题也不大
算法一(K=3,N=5,a1=2,a2=1,a3=2,a[i]=i):思路简单代码易于理解,代码简单。基本思路为在栈中回溯和向前试探,向前试探寻找满足容量上限的下一个候选数,从而扩大候选解的规模,候选解规模达到N即得到一个多重全排列。无法发现符合容量上限的下一个候选数即回溯
C++代码:
#include "stdafx.h" #include <vector> #include <iostream> using namespace std; const int K = 3; const int N = 5; int search(int start, const vector<int> &num, const vector<int> &count) //从start开始顺序查找满足容量限制的第一个数字,查找失败返回0,否则返回找到的数字 { for (; start <= K; ++start) { if (num[start - 1] + 1 <= count[start - 1]) return start; } return 0; } int main() { vector<int> count{ 2, 1, 2 }; //a1,---,ak值 vector<int> num(count.size(), 0); //统计循环过程中1,---,k的数目 vector<int> arrange(N, 0); //存放找到的多重全排列的栈结构 int i = 1; //栈顶指针 int number = 0; bool TF = true; //回溯标志 while (true) { if (i == 1) { if (TF == true) { arrange[i - 1] = 1; ++num[0]; ++i; } else { --num[arrange[i - 1] - 1]; ++arrange[i - 1]; if (arrange[i-1] > K) { break; } else { ++num[arrange[i - 1] - 1]; ++i; TF = true; } } } else { if (TF == true) { arrange[i - 1] = search(1, num, count); ++num[arrange[i - 1] - 1]; } else { int temp; if ((temp = search(arrange[i - 1] + 1, num, count)) == 0) { --num[arrange[i - 1] - 1]; --i; continue; } else { --num[arrange[i - 1] - 1]; arrange[i - 1] = temp; ++num[arrange[i - 1] - 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; }
运行结果:
算法二(K=3,N=5,a1=2,a2=1,a3=2,a[i]=i):代码相对而言更复杂,方法较笨,就是单纯地模拟手工寻找多重全排列的过程,该过程中按a[1],—,a[k]的顺序逐一选择子排列,成功找到子排列则向前试探扩大候选解的规模寻找下一个,当a[1],—,a[k]的所有子排列全部找到后即获得一个多重全排列,当已无新的子排列可供选择时即回溯
C++代码:
#include "stdafx.h" #include <vector> #include <iostream> using namespace std; bool find(bool TF, int n, int k, vector<int> &temp) //TF==true,函数从头寻找满足1<=a1<--<ak<=n的第一个排列a1,a2,--,ak存放在temp中 { //TF==false,函数寻找上一次找到的存放在temp中满足1<=a1<--<ak<=n的排列a1,a2,--,ak的下一个排列,找到存放在temp中返回true,找不到返回false int i; if (TF == true) { i = 0; } else { 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; i++; TF = 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; } } } const int K = 3; const int N = 5; struct back { vector<int> sub; //存放find函数找到的多重全排列中的一个子排列的排列位置 vector<int> father; //存放多重全排列所有N个排列位置被与其对应的sub子排列之前的所有排列占据后剩下的排列位置 back(int k) :sub(k, 0) {} }; void diffset(vector<back> &stack, const vector<int> &count) //计算father和sub的差集,得到sub的下一排列可取得排列位置 { int i = 0; int j = 0; back temp(count[stack.size()]); while (i < stack.back().father.size() && j < stack.back().sub.size()) { if (i + 1 < stack.back().sub[j]) { temp.father.push_back(stack.back().father[i]); ++i; } else if (i + 1 > stack.back().sub[j]) { ++j; } else { ++i; ++j; } } while (i < stack.back().father.size()) { temp.father.push_back(stack.back().father[i]); ++i; } stack.push_back(temp); } int main() { vector<int> count{2, 1, 2}; //a1,---,ak值 int i = 1; //循环当前正在处理的子排列序号 int num = 0; //多重全排列计数 bool TF = true; //回溯标志,true前进至本层,false回溯至本层 vector<back> stack; while (true) { if (i == 1) { if (TF == true) { stack.push_back(back(count[0])); find(true, N, count[i - 1], stack.back().sub); for (int j = 1; j <= N; j++) stack.back().father.push_back(j); ++i; } else { if (find(false, N, count[i-1], stack.back().sub) == true) { ++i; TF = true; } else { break; } } } else { if (TF == true) { diffset(stack, count); find(true, stack.back().father.size(), count[i - 1], stack.back().sub); } else { if (find(false, stack.back().father.size(), count[i - 1], stack.back().sub) == false) { stack.pop_back(); --i; continue; } } if (i == K) //找到一个多重全排列,输出 { ++num; vector<int> temp(N, 0); for (vector<back>::size_type i = 0; i < stack.size(); ++i) { for (vector<int>::size_type j = 0; j < stack[i].sub.size(); ++j) { temp[stack[i].father[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; }
运行结果: