找回密码
 欢迎注册
查看: 11750|回复: 13

[讨论] 求解拆分数组成固定组数的拆分方法(函数)

[复制链接]
发表于 2009-7-10 18:41:05 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
一个老问题,但这次没有限制,求全分组。具体如下:
设有1.....30个整数存放入a[1...30]的整数数组中,初始化如下:
int a[30];
for (int i=0;i<30;i++) a[i]= 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个组的所有的可能拆分数(就是返回上面多少行),这个数应该是固定的,具体多少我还没搞懂。

请指教,谢谢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-10 22:47:00 | 显示全部楼层
2) 取最小的,然后找两个和它一组
f(n)=C(2,n-1)*f(n-3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 22:49:58 | 显示全部楼层
没明白版主的意思?能说明白些吗?取最小的是取什么最小的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 23:08:48 | 显示全部楼层
我自己写了一个函数,理论上可以实现。但是运算时间太太长了。。。。。。。。。不现实。有人给出意见吗?
  1. ============Part 1 - Head.h============================
  2. //head.h
  3. #include<iostream>
  4. #include<bitset>
  5. #include<iomanip>
  6. #include<algorithm>
  7. #include<fstream>
  8. #include<cstdlib>
  9. #include<string>
  10. #include<vector>
  11. #include<set>
  12. #include<map>
  13. #include<utility>
  14. #include<cstdlib>
  15. #include<ctime>
  16. #include <sstream>
  17. #include <cmath>

  18. //一个Group (三个数字)
  19. struct Group {
  20.     int r1;
  21.     int r2;
  22.     int r3;
  23.     std::set<int> rSet;
  24.     void reset() {
  25.         r1 = r2 = r3 = 0;
  26.         rSet.clear();
  27.     }

  28.     void setCodes(int num1,int num2,int num3) {
  29.         r1 = num1;
  30.         r2 = num2;
  31.         r3 = num3;
  32.        rSet.clear();
  33.         rSet.insert(rSet.end(),r1);
  34.         rSet.insert(rSet.end(),r2);
  35.         rSet.insert(rSet.end(),r3);
  36.     }

  37.     Group() {
  38.         reset();
  39.     }
  40. };
  41. //一种折分方法
  42. struct OneDivided{
  43.     Group group[10];
  44.     void reset() {
  45.         for(int i=0;i<10;i++) {
  46.             group[i].reset();
  47.         }
  48.     }
  49.     OneDivided(){
  50.         reset();
  51.     }
  52. };

  53. //求数组a中的n个数的m组合,组合的结果以整数的集合形式放入codesResult中
  54. int
  55. combineCodes(int a[], int n, int m, std::vector<ThreeCodes>& codesResult) const{

  56.     codesResult.clear();

  57.     //m should smaller or equal n
  58.     m = m > n ? n : m;

  59.     int* order = new int[m+1];
  60.     for(int i=0; i<=m; i++) {
  61.         order[i] = i-1; // 注意这里order[0]=-1用来作为循环判断标识
  62.     }

  63.     int count = 0;
  64.     int k = m;
  65.     bool flag = true;           // 标志找到一个有效组合

  66.     while(order[0] == -1) {

  67.         if(flag) {
  68.             // 输出符合要求的组合
  69.             ThreeCodes item;
  70.             item.reset();

  71.             for(int i=1; i<=m; i++){
  72.                 //std::cout << a[order[i]] << " ";
  73.                 if(i==1) {
  74.                     item.r1 = a[order[1]];
  75.                 } else if(i==2){
  76.                     item.r2 = a[order[2]];
  77.                 } else if(i==3) {
  78.                     item.r3 = a[order[3]];
  79.                 }
  80.             }
  81.             codesResult.push_back(item);
  82.             //std::cout << std::endl;

  83.             count++;
  84.             flag = false;
  85.         }

  86.         order[k]++;                // 在当前位置选择新的数字
  87.         if(order[k] == n)          // 当前位置已无数字可选,回溯
  88.         {
  89.             order[k--] = 0;
  90.             continue;
  91.         }

  92.         if(k < m)                  // 更新当前位置的下一位置的数字
  93.         {
  94.             order[++k] = order[k-1];
  95.             continue;
  96.         }

  97.         if(k == m) {
  98.             flag = true;
  99.         }
  100.     }

  101.     delete[] order;
  102.     return count;
  103. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 23:12:10 | 显示全部楼层
  1. ============Part2---------main.cpp==============================
  2. #include "head.h"

  3. //求把30个数的数组分解为10个Group的算法
  4. //思量是:先将30个数组合3,一共有4060个3组合。
  5. //然后再在这4060个组合里面依次选出第1个Group,第2个Group....第10个Group
  6. //选择的范围就是在上面组合出来的4060个3组合里面选,选第n+1个Group的时候排除掉和
  7. //第1 - n组合3有重复的3组合(就是只选前面没有出现的Group)来保证各个Group是互相独立的
  8. //没有交集。
  9. long Get30Group10(void) const {
  10.     long total = 0;
  11.     std::vector<ThreeCodes> threeCodeResult;
  12.     int howManyThreeCodeResult = 0;
  13.     int a[30];
  14.     for(int i=0;i<30;i++) a[i] = i+1;
  15.       
  16.     //howManyThreeCodeResult  is 4060
  17.     howManyThreeCodeResult = combineCodes(a,30,3,threeCodeResult);
  18.       
  19.     std::set<int> reSet;
  20.     std::set<int> tmpSet;
  21.     std::set<int>::iterator reIter;

  22.     for(int i=0;i<howManyThreeCodeResult;i++){
  23.         //求一种分拆方式,分拆的10个Group放入oneDivided中
  24.         OneDivided oneDivided;
  25.         //选择Group0
  26.         oneDivided.group[0].setCodes(threeCodeResult[i].r1,
  27.                                      threeCodeResult[i].r2,
  28.                                      threeCodeResult[i].r3);
  29.         for(int j=0;j<howManyThreeCodeResult;j++) {
  30.             tmpSet.clear();
  31.             tmpSet.insert(tmpSet.begin(),threeCodeResult[j].r1);
  32.             tmpSet.insert(tmpSet.begin(),threeCodeResult[j].r2);
  33.             tmpSet.insert(tmpSet.begin(),threeCodeResult[j].r3);

  34.             reSet.clear();
  35.             reIter = reSet.begin();
  36.             set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  37.                 tmpSet.begin(), tmpSet.end(),
  38.                 inserter(reSet, reIter));

  39.             if(reSet.size() > 0) {
  40.                 //有相同
  41.                 continue;
  42.             }
  43.             //选择Group1, 在选择Group1之前,先排除和Group0有重复的元素,下面其他类似
  44.             oneDivided.group[1].setCodes(threeCodeResult[j].r1,
  45.                         threeCodeResult[j].r2,threeCodeResult[j].r3);

  46.             for(int k=0;k<howManyThreeCodeResult;k++) {
  47.                 tmpSet.clear();
  48.                 tmpSet.insert(tmpSet.begin(),threeCodeResult[k].r1);
  49.                 tmpSet.insert(tmpSet.begin(),threeCodeResult[k].r2);
  50.                 tmpSet.insert(tmpSet.begin(),threeCodeResult[k].r3);

  51.                 reSet.clear();
  52.                 reIter = reSet.begin();
  53.                 set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  54.                         tmpSet.begin(), tmpSet.end(),
  55.                         inserter(reSet, reIter));
  56.                 int size0 = reSet.size();
  57.                 if(size0 > 0) {
  58.                     continue;
  59.                 }
  60.                 reSet.clear();
  61.                 reIter = reSet.begin();
  62.                 set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  63.                         tmpSet.begin(), tmpSet.end(),
  64.                         inserter(reSet, reIter));
  65.                 int size1 = reSet.size();

  66.                 if(size1 > 0) {
  67.                     //有相同
  68.                     continue;
  69.                 }
  70.                 oneDivided.group[2].setCodes(threeCodeResult[k].r1,
  71.                             threeCodeResult[k].r2,threeCodeResult[k].r3);

  72.                 for(int m=0;m<howManyThreeCodeResult;m++) {
  73.                     tmpSet.clear();
  74.                     tmpSet.insert(tmpSet.begin(),threeCodeResult[m].r1);
  75.                     tmpSet.insert(tmpSet.begin(),threeCodeResult[m].r2);
  76.                     tmpSet.insert(tmpSet.begin(),threeCodeResult[m].r3);

  77.                     reSet.clear();
  78.                     reIter = reSet.begin();
  79.                     set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  80.                             tmpSet.begin(), tmpSet.end(),
  81.                             inserter(reSet, reIter));
  82.                     int size0 = reSet.size();
  83.                     if(size0 > 0) {
  84.                         continue;
  85.                     }

  86.                     reSet.clear();
  87.                     reIter = reSet.begin();
  88.                     set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  89.                             tmpSet.begin(), tmpSet.end(),
  90.                             inserter(reSet, reIter));
  91.                     int size1 = reSet.size();
  92.                     if(size1 > 0) {
  93.                         continue;
  94.                     }

  95.                     reSet.clear();
  96.                     reIter = reSet.begin();
  97.                     set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  98.                             tmpSet.begin(), tmpSet.end(),
  99.                             inserter(reSet, reIter));
  100.                     int size2 = reSet.size();
  101.                     if(size2 > 0) {
  102.                         continue;
  103.                     }
  104.                     oneDivided.group[3].setCodes(threeCodeResult[m].r1,
  105.                                 threeCodeResult[m].r2,threeCodeResult[m].r3);
  106.                     for(int n=0;n<howManyThreeCodeResult;n++) {
  107.                         tmpSet.clear();
  108.                         tmpSet.insert(tmpSet.begin(),threeCodeResult[n].r1);
  109.                         tmpSet.insert(tmpSet.begin(),threeCodeResult[n].r2);
  110.                         tmpSet.insert(tmpSet.begin(),threeCodeResult[n].r3);

  111.                         reSet.clear();
  112.                         reIter = reSet.begin();
  113.                         set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  114.                             tmpSet.begin(), tmpSet.end(),
  115.                                 inserter(reSet, reIter));
  116.                         int size0 = reSet.size();
  117.                         if(size0 > 0) {
  118.                         continue;
  119.                         }

  120.                         reSet.clear();
  121.                         reIter = reSet.begin();
  122.                         set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  123.                             tmpSet.begin(), tmpSet.end(),
  124.                                 inserter(reSet, reIter));
  125.                         int size1 = reSet.size();
  126.                         if(size1 > 0) {
  127.                             continue;
  128.                         }

  129.                         reSet.clear();
  130.                         reIter = reSet.begin();
  131.                         set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  132.                             tmpSet.begin(), tmpSet.end(),
  133.                                 inserter(reSet, reIter));
  134.                         int size2 = reSet.size();
  135.                         if(size2 > 0) {
  136.                             continue;
  137.                         }

  138.                         reSet.clear();
  139.                         reIter = reSet.begin();
  140.                         set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  141.                             tmpSet.begin(), tmpSet.end(),
  142.                             inserter(reSet, reIter));
  143.                         int size3 = reSet.size();
  144.                         if(size3 > 0) {
  145.                         continue;
  146.                         }

  147.                         oneDivided.group[4].setCodes(threeCodeResult[n].r1,
  148.                                     threeCodeResult[n].r2,threeCodeResult[n].r3);

  149.                         for(int o=0;o<howManyThreeCodeResult;o++) {
  150.                             tmpSet.clear();
  151.                             tmpSet.insert(tmpSet.begin(),threeCodeResult[o].r1);
  152.                             tmpSet.insert(tmpSet.begin(),threeCodeResult[o].r2);
  153.                             tmpSet.insert(tmpSet.begin(),threeCodeResult[o].r3);

  154.                             reSet.clear();
  155.                             reIter = reSet.begin();
  156.                             set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  157.                                 tmpSet.begin(), tmpSet.end(),
  158.                                     inserter(reSet, reIter));
  159.                             int size0 = reSet.size();
  160.                             if(size0 > 0) {
  161.                             continue;
  162.                             }

  163.                             reSet.clear();
  164.                             reIter = reSet.begin();
  165.                             set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  166.                                 tmpSet.begin(), tmpSet.end(),
  167.                                     inserter(reSet, reIter));
  168.                             int size1 = reSet.size();
  169.                             if(size1 > 0) {
  170.                             continue;
  171.                             }

  172.                             reSet.clear();
  173.                             reIter = reSet.begin();
  174.                             set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  175.                                 tmpSet.begin(), tmpSet.end(),
  176.                                     inserter(reSet, reIter));
  177.                             int size2 = reSet.size();
  178.                             if(size2 > 0) {
  179.                             continue;
  180.                             }

  181.                             reSet.clear();
  182.                             reIter = reSet.begin();
  183.                             set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  184.                                 tmpSet.begin(), tmpSet.end(),
  185.                                 inserter(reSet, reIter));
  186.                             int size3 = reSet.size();
  187.                             if(size3 > 0) {
  188.                             continue;
  189.                             }

  190.                             reSet.clear();
  191.                             reIter = reSet.begin();
  192.                             set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  193.                                 tmpSet.begin(), tmpSet.end(),
  194.                                 inserter(reSet, reIter));
  195.                             int size4 = reSet.size();
  196.                             if(size4 > 0) {
  197.                             continue;
  198.                             }

  199.                             oneDivided.group[5].setCodes(threeCodeResult[o].r1,
  200.                                         threeCodeResult[o].r2,threeCodeResult[o].r3);

  201.                             for(int p=0;p<howManyThreeCodeResult;p++) {
  202.                                 tmpSet.clear();
  203.                                 tmpSet.insert(tmpSet.begin(),threeCodeResult[p].r1);
  204.                                 tmpSet.insert(tmpSet.begin(),threeCodeResult[p].r2);
  205.                                 tmpSet.insert(tmpSet.begin(),threeCodeResult[p].r3);

  206.                                 reSet.clear();
  207.                                 reIter = reSet.begin();
  208.                                 set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  209.                                     tmpSet.begin(), tmpSet.end(),
  210.                                         inserter(reSet, reIter));
  211.                                 int size0 = reSet.size();
  212.                                 if(size0 > 0) {
  213.                                 continue;
  214.                                 }

  215.                                 reSet.clear();
  216.                                 reIter = reSet.begin();
  217.                                 set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  218.                                     tmpSet.begin(), tmpSet.end(),
  219.                                         inserter(reSet, reIter));
  220.                                 int size1 = reSet.size();
  221.                                 if(size1 > 0) {
  222.                                 continue;
  223.                                 }

  224.                                 reSet.clear();
  225.                                 reIter = reSet.begin();
  226.                                 set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  227.                                     tmpSet.begin(), tmpSet.end(),
  228.                                         inserter(reSet, reIter));
  229.                                 int size2 = reSet.size();
  230.                                 if(size2 > 0) {
  231.                                 continue;
  232.                                 }

  233.                                 reSet.clear();
  234.                                 reIter = reSet.begin();
  235.                                 set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  236.                                     tmpSet.begin(), tmpSet.end(),
  237.                                     inserter(reSet, reIter));
  238.                                 int size3 = reSet.size();
  239.                                 if(size3 > 0) {
  240.                                 continue;
  241.                                 }

  242.                                 reSet.clear();
  243.                                 reIter = reSet.begin();
  244.                                 set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  245.                                     tmpSet.begin(), tmpSet.end(),
  246.                                     inserter(reSet, reIter));
  247.                                 int size4 = reSet.size();
  248.                                 if(size4 > 0) {
  249.                                 continue;
  250.                                 }

  251.                                 reSet.clear();
  252.                                 reIter = reSet.begin();
  253.                                 set_intersection(oneDivided.group[5].redSet.begin(),oneDivided.group[5].redSet.end(),
  254.                                     tmpSet.begin(), tmpSet.end(),
  255.                                     inserter(reSet, reIter));
  256.                                 int size5 = reSet.size();
  257.                                 if(size5 > 0) {
  258.                                 continue;
  259.                                 }

  260.                                 oneDivided.group[6].setCodes(threeCodeResult[p].r1,
  261.                                             threeCodeResult[p].r2,threeCodeResult[p].r3);
  262.                                 for(int s=0;s<howManyThreeCodeResult;s++) {
  263.                                     tmpSet.clear();
  264.                                     tmpSet.insert(tmpSet.begin(),threeCodeResult[s].r1);
  265.                                     tmpSet.insert(tmpSet.begin(),threeCodeResult[s].r2);
  266.                                     tmpSet.insert(tmpSet.begin(),threeCodeResult[s].r3);

  267.                                     reSet.clear();
  268.                                     reIter = reSet.begin();
  269.                                     set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  270.                                         tmpSet.begin(), tmpSet.end(),
  271.                                             inserter(reSet, reIter));
  272.                                     int size0 = reSet.size();
  273.                                     if(size0 > 0) {
  274.                                     continue;
  275.                                     }

  276.                                     reSet.clear();
  277.                                     reIter = reSet.begin();
  278.                                     set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  279.                                         tmpSet.begin(), tmpSet.end(),
  280.                                             inserter(reSet, reIter));
  281.                                     int size1 = reSet.size();
  282.                                     if(size1 > 0) {
  283.                                     continue;
  284.                                     }

  285.                                     reSet.clear();
  286.                                     reIter = reSet.begin();
  287.                                     set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  288.                                         tmpSet.begin(), tmpSet.end(),
  289.                                             inserter(reSet, reIter));
  290.                                     int size2 = reSet.size();
  291.                                     if(size2 > 0) {
  292.                                     continue;
  293.                                     }

  294.                                     reSet.clear();
  295.                                     reIter = reSet.begin();
  296.                                     set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  297.                                         tmpSet.begin(), tmpSet.end(),
  298.                                         inserter(reSet, reIter));
  299.                                     int size3 = reSet.size();
  300.                                     if(size3 > 0) {
  301.                                         continue;
  302.                                     }
  303. //===================================Part 2 End ===============================//
  304. //见下面(由于帖子长度有限制)
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 23:12:36 | 显示全部楼层
  1. //===================================Part 3 Start ================//
  2.                                     reSet.clear();
  3.                                     reIter = reSet.begin();
  4.                                     set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  5.                                         tmpSet.begin(), tmpSet.end(),
  6.                                         inserter(reSet, reIter));
  7.                                     int size4 = reSet.size();
  8.                                     if(size4 > 0) {
  9.                                         continue;
  10.                                     }

  11.                                     reSet.clear();
  12.                                     reIter = reSet.begin();
  13.                                     set_intersection(oneDivided.group[5].redSet.begin(),oneDivided.group[5].redSet.end(),
  14.                                         tmpSet.begin(), tmpSet.end(),
  15.                                         inserter(reSet, reIter));
  16.                                     int size5 = reSet.size();
  17.                                     if(size5 > 0) {
  18.                                         continue;
  19.                                     }

  20.                                     reSet.clear();
  21.                                     reIter = reSet.begin();
  22.                                     set_intersection(oneDivided.group[6].redSet.begin(),oneDivided.group[6].redSet.end(),
  23.                                         tmpSet.begin(), tmpSet.end(),
  24.                                         inserter(reSet, reIter));
  25.                                     int size6 = reSet.size();
  26.                                     if(size6 > 0) {
  27.                                         continue;
  28.                                     }

  29.                                     oneDivided.group[7].setCodes(threeCodeResult[s].r1,
  30.                                                 threeCodeResult[s].r2,threeCodeResult[s].r3);

  31.                                     for(int t=0;t<howManyThreeCodeResult;t++) {
  32.                                         tmpSet.clear();
  33.                                         tmpSet.insert(tmpSet.begin(),threeCodeResult[t].r1);
  34.                                         tmpSet.insert(tmpSet.begin(),threeCodeResult[t].r2);
  35.                                         tmpSet.insert(tmpSet.begin(),threeCodeResult[t].r3);

  36.                                         reSet.clear();
  37.                                         reIter = reSet.begin();
  38.                                         set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  39.                                             tmpSet.begin(), tmpSet.end(),
  40.                                                 inserter(reSet, reIter));
  41.                                         int size0 = reSet.size();
  42.                                         if(size0 > 0) {
  43.                                             continue;
  44.                                         }

  45.                                         reSet.clear();
  46.                                         reIter = reSet.begin();
  47.                                         set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  48.                                             tmpSet.begin(), tmpSet.end(),
  49.                                                 inserter(reSet, reIter));
  50.                                         int size1 = reSet.size();
  51.                                         if(size1 > 0) {
  52.                                             continue;
  53.                                         }

  54.                                         reSet.clear();
  55.                                         reIter = reSet.begin();
  56.                                         set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  57.                                             tmpSet.begin(), tmpSet.end(),
  58.                                                 inserter(reSet, reIter));
  59.                                         int size2 = reSet.size();
  60.                                         if(size2 > 0) {
  61.                                             continue;
  62.                                         }

  63.                                         reSet.clear();
  64.                                         reIter = reSet.begin();
  65.                                         set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  66.                                             tmpSet.begin(), tmpSet.end(),
  67.                                             inserter(reSet, reIter));
  68.                                         int size3 = reSet.size();
  69.                                         if(size3 > 0) {
  70.                                             continue;
  71.                                         }

  72.                                         reSet.clear();
  73.                                         reIter = reSet.begin();
  74.                                         set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  75.                                             tmpSet.begin(), tmpSet.end(),
  76.                                             inserter(reSet, reIter));
  77.                                         int size4 = reSet.size();
  78.                                         if(size4 > 0) {
  79.                                             continue;
  80.                                         }

  81.                                         reSet.clear();
  82.                                         reIter = reSet.begin();
  83.                                         set_intersection(oneDivided.group[5].redSet.begin(),oneDivided.group[5].redSet.end(),
  84.                                             tmpSet.begin(), tmpSet.end(),
  85.                                             inserter(reSet, reIter));
  86.                                         int size5 = reSet.size();
  87.                                         if(size5 > 0) {
  88.                                             continue;
  89.                                         }

  90.                                         reSet.clear();
  91.                                         reIter = reSet.begin();
  92.                                         set_intersection(oneDivided.group[6].redSet.begin(),oneDivided.group[6].redSet.end(),
  93.                                             tmpSet.begin(), tmpSet.end(),
  94.                                             inserter(reSet, reIter));
  95.                                         int size6 = reSet.size();
  96.                                         if(size6 > 0) {
  97.                                             continue;
  98.                                         }

  99.                                         reSet.clear();
  100.                                         reIter = reSet.begin();
  101.                                         set_intersection(oneDivided.group[7].redSet.begin(),oneDivided.group[7].redSet.end(),
  102.                                             tmpSet.begin(), tmpSet.end(),
  103.                                             inserter(reSet, reIter));
  104.                                         int size7 = reSet.size();
  105.                                         if(size7 > 0) {
  106.                                             continue;
  107.                                         }

  108.                                         oneDivided.group[8].setCodes(threeCodeResult[t].r1,
  109.                                                     threeCodeResult[t].r2,threeCodeResult[t].r3);

  110.                                         for(int u=0;u<howManyThreeCodeResult;u++) {
  111.                                             tmpSet.clear();
  112.                                             tmpSet.insert(tmpSet.begin(),threeCodeResult[u].r1);
  113.                                             tmpSet.insert(tmpSet.begin(),threeCodeResult[u].r2);
  114.                                             tmpSet.insert(tmpSet.begin(),threeCodeResult[u].r3);

  115.                                             reSet.clear();
  116.                                             reIter = reSet.begin();
  117.                                             set_intersection(oneDivided.group[0].redSet.begin(),oneDivided.group[0].redSet.end(),
  118.                                                 tmpSet.begin(), tmpSet.end(),
  119.                                                     inserter(reSet, reIter));
  120.                                             int size0 = reSet.size();
  121.                                             if(size0 > 0) {
  122.                                                 continue;
  123.                                             }

  124.                                             reSet.clear();
  125.                                             reIter = reSet.begin();
  126.                                             set_intersection(oneDivided.group[1].redSet.begin(),oneDivided.group[1].redSet.end(),
  127.                                                 tmpSet.begin(), tmpSet.end(),
  128.                                                     inserter(reSet, reIter));
  129.                                             int size1 = reSet.size();
  130.                                             if(size1 > 0) {
  131.                                                 continue;
  132.                                             }

  133.                                             reSet.clear();
  134.                                             reIter = reSet.begin();
  135.                                             set_intersection(oneDivided.group[2].redSet.begin(),oneDivided.group[2].redSet.end(),
  136.                                                 tmpSet.begin(), tmpSet.end(),
  137.                                                     inserter(reSet, reIter));
  138.                                             int size2 = reSet.size();
  139.                                             if(size2 > 0) {
  140.                                                 continue;
  141.                                             }

  142.                                             reSet.clear();
  143.                                             reIter = reSet.begin();
  144.                                             set_intersection(oneDivided.group[3].redSet.begin(),oneDivided.group[3].redSet.end(),
  145.                                                 tmpSet.begin(), tmpSet.end(),
  146.                                                 inserter(reSet, reIter));
  147.                                             int size3 = reSet.size();
  148.                                             if(size3 > 0) {
  149.                                                 continue;
  150.                                             }

  151.                                             reSet.clear();
  152.                                             reIter = reSet.begin();
  153.                                             set_intersection(oneDivided.group[4].redSet.begin(),oneDivided.group[4].redSet.end(),
  154.                                                 tmpSet.begin(), tmpSet.end(),
  155.                                                 inserter(reSet, reIter));
  156.                                             int size4 = reSet.size();
  157.                                             if(size4 > 0) {
  158.                                                 continue;
  159.                                             }

  160.                                             reSet.clear();
  161.                                             reIter = reSet.begin();
  162.                                             set_intersection(oneDivided.group[5].redSet.begin(),oneDivided.group[5].redSet.end(),
  163.                                                 tmpSet.begin(), tmpSet.end(),
  164.                                                 inserter(reSet, reIter));
  165.                                             int size5 = reSet.size();
  166.                                             if(size5 > 0) {
  167.                                                 continue;
  168.                                             }

  169.                                             reSet.clear();
  170.                                             reIter = reSet.begin();
  171.                                             set_intersection(oneDivided.group[6].redSet.begin(),oneDivided.group[6].redSet.end(),
  172.                                                 tmpSet.begin(), tmpSet.end(),
  173.                                                 inserter(reSet, reIter));
  174.                                             int size6 = reSet.size();
  175.                                             if(size6 > 0) {
  176.                                                 continue;
  177.                                             }

  178.                                             reSet.clear();
  179.                                             reIter = reSet.begin();
  180.                                             set_intersection(oneDivided.group[7].redSet.begin(),oneDivided.group[7].redSet.end(),
  181.                                                 tmpSet.begin(), tmpSet.end(),
  182.                                                 inserter(reSet, reIter));
  183.                                             int size7 = reSet.size();
  184.                                             if(size7 > 0) {
  185.                                                 continue;
  186.                                             }

  187.                                             reSet.clear();
  188.                                             reIter = reSet.begin();
  189.                                             set_intersection(oneDivided.group[8].redSet.begin(),oneDivided.group[8].redSet.end(),
  190.                                                 tmpSet.begin(), tmpSet.end(),
  191.                                                 inserter(reSet, reIter));
  192.                                             int size8 = reSet.size();
  193.                                             if(size8 > 0) {
  194.                                                 continue;
  195.                                             }

  196.                                             oneDivided.group[9].setCodes(threeCodeResult[u].r1,
  197.                                                         threeCodeResult[u].r2,threeCodeResult[u].r3);
  198.                                             for(int rr=0;rr<10;rr++) {
  199.                                                 std::cout << oneDivided.group[rr].r1 << " "
  200.                                                           << oneDivided.group[rr].r2 << " "
  201.                                                           << oneDivided.group[rr].r3 << " "
  202.                                                           << "||";
  203.                                             }
  204.                                             total++;
  205.                                           

  206.                                         }//end for(u)
  207.                                     }//end for(t)
  208.                                 }//end for(s)
  209.                             }//end for(p);
  210.                         }//end for(o)
  211.                     }//end for(n)
  212.                 }//end for(m)
  213.             } //end for(k)
  214.         }//end for(j)
  215.     }//end for (i)
  216.     return total;
  217. }

  218. void main(void) {
  219.    long total = Get30Group10();
  220.    std::cout << "Total: " << total;
  221. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-7-10 23:15:55 | 显示全部楼层
以上程序在gcc+STL下面正确编译并运行。但是发现运算时间太长太长了。。。。。。。。。。。。。。。。

求帮助。。。。。。。。。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-12 10:43:24 | 显示全部楼层
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万个世纪
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-15 16:29:58 | 显示全部楼层
30!/10!/(3!)^10=1208883745669600000
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-15 17:21:56 | 显示全部楼层
northwolves分析正确,shshsh_0510还需要在结果上除以10!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-4-18 15:50 , Processed in 0.052183 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表