求解拆分数组成固定组数的拆分方法（函数）
一个老问题，但这次没有限制，求全分组。具体如下：设有1.....30个整数存放入a的整数数组中,初始化如下：
int a;
for (int i=0;i<30;i++) a= i+1;
现要把此30个数分成10个组，每组固定3个数（不管数的顺序，如1，2，3 和 2， 3，1 算一样的一组）。
1）设计一个函数，打印出该30数组拆分为10组的全部可能的分组情况,每行打印一种拆分方法，以||分开各组。如：
1 2 3 ||4 5 6 ||7 8 9 ||10 11 12 ||13 14 15|| 16 17 18|| 19 20 21|| 22 23 24|| 25 26 27|| 28 29 30|| －－算一种拆分方法
.....
.....
2)该函数返回30个数拆分为10个组的所有的可能拆分数（就是返回上面多少行），这个数应该是固定的，具体多少我还没搞懂。
请指教，谢谢。 2) 取最小的，然后找两个和它一组
f(n)=C(2,n-1)*f(n-3) 没明白版主的意思？能说明白些吗？取最小的是取什么最小的？ 我自己写了一个函数，理论上可以实现。但是运算时间太太长了。。。。。。。。。不现实。有人给出意见吗？＝＝＝＝＝＝＝＝＝＝＝＝Part 1 - Head.h＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
//head.h
#include<iostream>
#include<bitset>
#include<iomanip>
#include<algorithm>
#include<fstream>
#include<cstdlib>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<utility>
#include<cstdlib>
#include<ctime>
#include <sstream>
#include <cmath>
//一个Group (三个数字）
struct Group {
int r1;
int r2;
int r3;
std::set<int> rSet;
void reset() {
r1 = r2 = r3 = 0;
rSet.clear();
}
void setCodes(int num1,int num2,int num3) {
r1 = num1;
r2 = num2;
r3 = num3;
rSet.clear();
rSet.insert(rSet.end(),r1);
rSet.insert(rSet.end(),r2);
rSet.insert(rSet.end(),r3);
}
Group() {
reset();
}
};
//一种折分方法
struct OneDivided{
Group group;
void reset() {
for(int i=0;i<10;i++) {
group.reset();
}
}
OneDivided(){
reset();
}
};
//求数组a中的n个数的m组合，组合的结果以整数的集合形式放入codesResult中
int
combineCodes(int a[], int n, int m, std::vector<ThreeCodes>& codesResult) const{
codesResult.clear();
//m should smaller or equal n
m = m > n ? n : m;
int* order = new int;
for(int i=0; i<=m; i++) {
order = i-1; // 注意这里order=-1用来作为循环判断标识
}
int count = 0;
int k = m;
bool flag = true; // 标志找到一个有效组合
while(order == -1) {
if(flag) {
// 输出符合要求的组合
ThreeCodes item;
item.reset();
for(int i=1; i<=m; i++){
//std::cout << a] << " ";
if(i==1) {
item.r1 = a];
} else if(i==2){
item.r2 = a];
} else if(i==3) {
item.r3 = a];
}
}
codesResult.push_back(item);
//std::cout << std::endl;
count++;
flag = false;
}
order++; // 在当前位置选择新的数字
if(order == n) // 当前位置已无数字可选，回溯
{
order = 0;
continue;
}
if(k < m) // 更新当前位置的下一位置的数字
{
order[++k] = order;
continue;
}
if(k == m) {
flag = true;
}
}
delete[] order;
return count;
} ============Part2---------main.cpp==============================
#include "head.h"
//求把30个数的数组分解为10个Group的算法
//思量是：先将30个数组合3，一共有4060个3组合。
//然后再在这4060个组合里面依次选出第1个Group，第2个Group....第10个Group
//选择的范围就是在上面组合出来的4060个3组合里面选，选第n＋1个Group的时候排除掉和
//第1 － n组合3有重复的3组合（就是只选前面没有出现的Group)来保证各个Group是互相独立的
//没有交集。
long Get30Group10(void) const {
long total = 0;
std::vector<ThreeCodes> threeCodeResult;
int howManyThreeCodeResult = 0;
int a;
for(int i=0;i<30;i++) a = i+1;
//howManyThreeCodeResultis 4060
howManyThreeCodeResult = combineCodes(a,30,3,threeCodeResult);
std::set<int> reSet;
std::set<int> tmpSet;
std::set<int>::iterator reIter;
for(int i=0;i<howManyThreeCodeResult;i++){
//求一种分拆方式，分拆的10个Group放入oneDivided中
OneDivided oneDivided;
//选择Group0
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,
threeCodeResult.r3);
for(int j=0;j<howManyThreeCodeResult;j++) {
tmpSet.clear();
tmpSet.insert(tmpSet.begin(),threeCodeResult.r1);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r2);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r3);
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
if(reSet.size() > 0) {
//有相同
continue;
}
//选择Group1, 在选择Group1之前，先排除和Group0有重复的元素，下面其他类似
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,threeCodeResult.r3);
for(int k=0;k<howManyThreeCodeResult;k++) {
tmpSet.clear();
tmpSet.insert(tmpSet.begin(),threeCodeResult.r1);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r2);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r3);
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size0 = reSet.size();
if(size0 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size1 = reSet.size();
if(size1 > 0) {
//有相同
continue;
}
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,threeCodeResult.r3);
for(int m=0;m<howManyThreeCodeResult;m++) {
tmpSet.clear();
tmpSet.insert(tmpSet.begin(),threeCodeResult.r1);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r2);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r3);
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size0 = reSet.size();
if(size0 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size1 = reSet.size();
if(size1 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size2 = reSet.size();
if(size2 > 0) {
continue;
}
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,threeCodeResult.r3);
for(int n=0;n<howManyThreeCodeResult;n++) {
tmpSet.clear();
tmpSet.insert(tmpSet.begin(),threeCodeResult.r1);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r2);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r3);
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size0 = reSet.size();
if(size0 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size1 = reSet.size();
if(size1 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size2 = reSet.size();
if(size2 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size3 = reSet.size();
if(size3 > 0) {
continue;
}
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,threeCodeResult.r3);
for(int o=0;o<howManyThreeCodeResult;o++) {
tmpSet.clear();
tmpSet.insert(tmpSet.begin(),threeCodeResult.r1);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r2);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r3);
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size0 = reSet.size();
if(size0 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size1 = reSet.size();
if(size1 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size2 = reSet.size();
if(size2 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size3 = reSet.size();
if(size3 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size4 = reSet.size();
if(size4 > 0) {
continue;
}
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,threeCodeResult.r3);
for(int p=0;p<howManyThreeCodeResult;p++) {
tmpSet.clear();
tmpSet.insert(tmpSet.begin(),threeCodeResult.r1);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r2);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r3);
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size0 = reSet.size();
if(size0 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size1 = reSet.size();
if(size1 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size2 = reSet.size();
if(size2 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size3 = reSet.size();
if(size3 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size4 = reSet.size();
if(size4 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size5 = reSet.size();
if(size5 > 0) {
continue;
}
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,threeCodeResult.r3);
for(int s=0;s<howManyThreeCodeResult;s++) {
tmpSet.clear();
tmpSet.insert(tmpSet.begin(),threeCodeResult.r1);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r2);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r3);
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size0 = reSet.size();
if(size0 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size1 = reSet.size();
if(size1 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size2 = reSet.size();
if(size2 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size3 = reSet.size();
if(size3 > 0) {
continue;
}
//===================================Part 2 End ===============================//
//见下面（由于帖子长度有限制） //===================================Part 3 Start ================//
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size4 = reSet.size();
if(size4 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size5 = reSet.size();
if(size5 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size6 = reSet.size();
if(size6 > 0) {
continue;
}
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,threeCodeResult.r3);
for(int t=0;t<howManyThreeCodeResult;t++) {
tmpSet.clear();
tmpSet.insert(tmpSet.begin(),threeCodeResult.r1);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r2);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r3);
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size0 = reSet.size();
if(size0 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size1 = reSet.size();
if(size1 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size2 = reSet.size();
if(size2 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size3 = reSet.size();
if(size3 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size4 = reSet.size();
if(size4 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size5 = reSet.size();
if(size5 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size6 = reSet.size();
if(size6 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size7 = reSet.size();
if(size7 > 0) {
continue;
}
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,threeCodeResult.r3);
for(int u=0;u<howManyThreeCodeResult;u++) {
tmpSet.clear();
tmpSet.insert(tmpSet.begin(),threeCodeResult.r1);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r2);
tmpSet.insert(tmpSet.begin(),threeCodeResult.r3);
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size0 = reSet.size();
if(size0 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size1 = reSet.size();
if(size1 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size2 = reSet.size();
if(size2 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size3 = reSet.size();
if(size3 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size4 = reSet.size();
if(size4 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size5 = reSet.size();
if(size5 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size6 = reSet.size();
if(size6 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size7 = reSet.size();
if(size7 > 0) {
continue;
}
reSet.clear();
reIter = reSet.begin();
set_intersection(oneDivided.group.redSet.begin(),oneDivided.group.redSet.end(),
tmpSet.begin(), tmpSet.end(),
inserter(reSet, reIter));
int size8 = reSet.size();
if(size8 > 0) {
continue;
}
oneDivided.group.setCodes(threeCodeResult.r1,
threeCodeResult.r2,threeCodeResult.r3);
for(int rr=0;rr<10;rr++) {
std::cout << oneDivided.group.r1 << " "
<< oneDivided.group.r2 << " "
<< oneDivided.group.r3 << " "
<< "||";
}
total++;
}//end for(u)
}//end for(t)
}//end for(s)
}//end for(p);
}//end for(o)
}//end for(n)
}//end for(m)
} //end for(k)
}//end for(j)
}//end for (i)
return total;
}
void main(void) {
long total = Get30Group10();
std::cout << "Total: " << total;
} 以上程序在gcc＋STL下面正确编译并运行。但是发现运算时间太长太长了。。。。。。。。。。。。。。。。
求帮助。。。。。。。。。。。 1-30，最小的是1，先将1与某两个元素分为一组，需要从剩下的29个中取两个，故有C(2,29)种方法。
接下来需要将其他的27个分组。
于是f(30)=C(2,29)*f(27)=C(2,29)*C(2,26)*f(24)=...=C(2,29)*C(2,26)*...*C(2,5)*C(2,2)=1208883745669600000
如果你的程序每秒输出1000种的话,你需要大约40万个世纪 30!/10!/(3!)^10=1208883745669600000 northwolves分析正确,shshsh_0510还需要在结果上除以10!
页:
[1]
2