求一算法:用程序实现组合,从10个字符里选取5个.

Ilovesport 2007-11-19 02:27:51
RT,如有{ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' }10个字符,求从中选择5个组合共有多少组,考虑效率.
...全文
864 41 打赏 收藏 转发到动态 举报
写回复
用AI写文章
41 条回复
切换为时间正序
请发表友善的回复…
发表回复
donkey301 2010-06-23
  • 打赏
  • 举报
 回复
总结一下：
1. a002在11楼的代码是正确的，它的原理就是1楼和13楼贴出的网页


                //从左到右扫描数组元素值的“10”组合

		j = 0;

		while(subset[j + 1] <= subset[j] + 1)

			j++;



                //找到第一个“10”组合后将其变为 “01”组合

		subset[j]++;



                //将其左边的所有“1”全部移动到数组的最左端

		for(i = 0; i < j; i++)

			subset[i] = i;

		return 1;

2. 效率问题： 11楼的在我的机子上需要900ms,但如果把vector<int>改为int数组，那么只需80ms,和media在2楼需要的时间差不多，但考虑到11楼函数调用花费的时间，11楼的速度应该是比2楼的快。把他们的代码放在一起比较


  //2楼的

  j=m;                                

  while( B[j]==n )

  --j;

  ++B[j];

  for( i=j+1; i<=m; ++i )

  B[i]=B[j];

  swap( A[j], A[B[j]] );



  //11楼的

    j = 0;

    while(subset[j + 1] <= subset[j] + 1)

      j++;

    subset[j]++;

    for(i = 0; i < j; i++)

      subset[i] = i;

    return 1;

可以看出2楼的多了一步swap.
3. 至于23楼的gray code,看到goto头痛就不测试了。

总结： 11楼的代码配上1楼的原理比较容易理解而且效率也可以，更适合实际工作，因为实际工作中很多时候慢的不是在得到组合上，而是得到组合后如何操作，譬如打印出组合也是一种操作。
p.s. 24楼的估计还是很不错的，我用1秒10^8操作来估计发现基本上在同一数量级
RogueBear 2008-08-26
  • 打赏
  • 举报
 回复
HW121 这个哥们的算法更猛点。。也就是穷举法。不过当m=n 或者m = n + 1的时候 有点问题。需要再看看
RogueBear 2008-08-26
  • 打赏
  • 举报
 回复
测试了下。5选4的时候media2005的程序输出是错的：
输出为
1 2 3 5
1 3 4 5
2 3 4 5 《----这个重复了
2 3 4 5
1 2 4 5
RogueBear 2008-08-26
  • 打赏
  • 举报
 回复
最近搞彩票。找到这里。media2005的算法不错。。强人。。
medie2005 2007-11-20
  • 打赏
  • 举报
 回复
假设现在的计算机的运行速度为 1秒钟10^8个基本运算（我一般这么假设），并设最优算法只要1次基本运算就由上一个组合得到下一个组合。那么，生成1,352,078个组合大概要2,000,000个基本运算，即大约 20 ms左右。
kaishui_gu 2007-11-20
  • 打赏
  • 举报
 回复
to medie2005:

不好意思，把数算错了，23选11总数应该是16224936/12=1,352,078个。

这样的话，最好的组合生成算法产生23选11的时间大概只要应在20 ms左右，我给的算法，效率应该算比较差的了。


请问你的20 ms是怎么算出来的？计算公式？
medie2005 2007-11-20
  • 打赏
  • 举报
 回复
贴一个接近效率最优的组合生成程序。[算法来自Knuth的《计算机程序设计艺术》 第四卷 第三册， 也就是上面我说的基于格雷通路的算法]
#include   <windows.h>

#include   <iostream>

#include   <iterator>



using   namespace   std;



void     combination(   int   n,   int   m   ){

	int  *c=new int[m+2], j;

	for( j=1; j<=m; ++j )  c[j]=j-1; 

	c[m+1]=n;

R2:	;//copy( c+1, c+m+1, ostream_iterator<int>(cout," ") ),cout<<endl;

	if( m&1 )

		if( c[1]+1<c[2] ){

			++c[1];  goto R2;

		}

		else{ 

			j=2;  goto R4;

		}

	else

		if( c[1]>0 ){

			--c[1];  goto R2;

		}

		else{

			j=2;  goto R5;

		};

R4:	if( c[j]>=j ){

		c[j]=c[j-1];  c[j-1]=j-2;  goto R2;

	}

	else

		++j;

R5:	if( c[j]+1<c[j+1] ){

		c[j-1]=c[j];  c[j]=c[j]+1;  goto R2;

	}

	else{

		++j;

		if( j<=m )	goto R4;

	}

	delete []c;

}



int   main(int   argc,   char   *argv[])

{

	int time=GetTickCount();

	combination(   23,  11  );

	cout<<GetTickCount()-time<<" ms\n";

	return   0;

}

在我的机器上，运行时间大概是 20ms 左右，差不多是最优的了。

另外，楼主不要问我算法原理，因为我目前只看到第二册，还没看到第三册。
medie2005 2007-11-20
  • 打赏
  • 举报
 回复
不好意思，把数算错了，23选11总数应该是16224936/12=1,352,078个。

这样的话，最好的组合生成算法产生23选11的时间大概只要应在20 ms左右，我给的算法，效率应该算比较差的了。
medie2005 2007-11-20
  • 打赏
  • 举报
 回复
ls: 我在三楼已经帖了。
a0002 2007-11-20
  • 打赏
  • 举报
 回复
to medie2005

可否把程序贴出来？
a0002 2007-11-20
  • 打赏
  • 举报
 回复
再来一个慢的，但是可以直接得到第n个组合，比如：
10选5的第一个组合是(0,1,2,3,4)，
10选5的最后一个组合（第3003个）组合是(5,6,7,8,9)。

#include <iostream>

#include <vector>



using namespace std;



template <class T>

inline void PRINT_ELEMENTS (const T& coll, char tokens[], const char* optcstr="")

{

    typename T::const_iterator pos;

	

    std::cout << optcstr;

    for (pos=coll.begin(); pos!=--coll.end(); ++pos) {

        std::cout << tokens[*pos] << ' ';

    }

    std::cout << std::endl;

}



//计算组合数C(n,m)

int C(int n, int m)

{

	double result = 1;



	for (int i = 0; i < m; i++)

	{

		result *= n - i;

		result /= i + 1;

	}

	return (int)result;

}



//计算第rank个组合，rank从0到C(n,card)-1

void unrankCombination( int rank, vector<int> &subset, int card)

{

  int p, m;



  m = rank;

  for(int i = card - 1; i >= 0; i--) {

    p = i;

    while( C(p+1, i+1) <= m ) p++;

    m -= C( p, i+1 );

    subset[i] = p;

  }

}



int main(int argc, char* argv[])

{

    int m = 10;

	int n = 15;

	

	vector<int> combination( m + 1 );

	char tokens[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'};



	for( int rank = 0; rank < C( n, m ); rank++)

	{

		unrankCombination( rank, combination, m );

		cout << rank + 1 << ": ";

		PRINT_ELEMENTS( combination, tokens );

	}



	cout << "\n\tpress Enter to exit ..." << endl;

	cin.get();



    return 0;

}

medie2005 2007-11-20
  • 打赏
  • 举报
 回复
若我没看错，a0002用的是词典序法，不过，字典序法效率本身就不高，只是比较通用而已。

因为23选11总数是16,224,936个。因此，如不考虑输出，最好的组合生成算法产生23选11的时间应在160ms左右，
即0.16秒。
在我的机器上，用我给的算法，23选11用时大约是 290 ms（不考虑输出用时），接近最好算法的效率。
mu_yang 2007-11-20
  • 打赏
  • 举报
 回复
好久没看到goto了
22楼,请问你那些个goto是Knuth的还是你的
Ilovesport 2007-11-20
  • 打赏
  • 举报
 回复
要不大家用23个中选11个测试一下自己算法,在算法开始和结束都打印出时间,比较一下时间效率,互相学习一下.
Ilovesport 2007-11-20
  • 打赏
  • 举报
 回复
谢谢楼上几位,晚些结贴,期待高手给出更好的算法.
a0002 2007-11-20
  • 打赏
  • 举报
 回复
to zhulinpptor:
效率太低，尤其是n远大于m时，比如20选5,用你的算法每次要从20个元素中搜索连续的10，而且搜索10串要做两次比较。

pptor 2007-11-20
  • 打赏
  • 举报
 回复
http://www.yuanma.org/data/2006/0529/article_506.htm
a0002 2007-11-20
  • 打赏
  • 举报
 回复
int main(int argc, int argv[])

改成

int main(int argc, char* argv[])
a0002 2007-11-20
  • 打赏
  • 举报
 回复 
#include "stdafx.h"

#include <iostream>

#include <vector>



using namespace std;



#define maxv 100



void getFirstCombination(vector<int> &subset, int card)

{

  int i;



  for(i = 0; i < card; i++)

    subset[i] = i;

  subset[i] = maxv + 1; 

}



int getNextCombination(vector<int> &subset, int card, int v)

{

  int i,j;



  if(subset[0] >= v - card)

    return 0;

  else {

    j = 0;

    while(subset[j + 1] <= subset[j] + 1)

      j++;

    subset[j]++;

    for(i = 0; i < j; i++)

      subset[i] = i;

    return 1;

  }

}



template <class T>

inline void PRINT_ELEMENTS (const T& coll, char tokens[], const char* optcstr="")

{

    typename T::const_iterator pos;

	

    std::cout << optcstr;

    for (pos=coll.begin(); pos!=--coll.end(); ++pos) {

        std::cout << tokens[*pos] << ' ';

    }

    std::cout << std::endl;

}



int main(int argc, int argv[])

{

	int card = 5;

	int vol = 10;

	int index = 1;

	vector<int> combination(card+1);

	char tokens[] = {'A','B','C','D','E','F','G','H','I','J'};



	getFirstCombination( combination, card );

	

	do{ 

		cout << index << ": ";

		PRINT_ELEMENTS( combination, tokens );

		index++;

	}while( getNextCombination(combination, card, vol) );



	cout << "\n\tpress Enter to exit ..." << endl;

	cin.get();



    return 0;

}


这段程序中求组合的算法源于Knuth的《计算机程序设计艺术》。
Sunshine31 2007-11-20
  • 打赏
  • 举报
 回复
忘记说了，公司在深圳
加载更多回复（20）
字符串的组合算法问题的C语言实现攻略
针对第一个字符，我们有两种选择：第一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；第二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都...
基于神经网络的车牌字符识别技术.doc
每个项目都有许多不同的算法来解决，综合考虑到时间和实验要求，这里，车牌的定位我选取基于边缘检测和基于形态学的综合方法来实现，字符分割选取基于投影特征的方法来实现，而字符识别选取基于神经网络的分类方法来...
MD5算法C语言实现
课程名称：C语言实现MD5算法 应用知识：C语言基础知识：流程结构，文件操作，位运算，函数，宏... 课程目的： 1、练习C语言知识综合运用 2、巩固C语言基础知识 3、了解MD5算法的基本原理 课程特点： 1、知识点讲解...
matlab：KNN实现手写数字识别
本资源实现了KNN算法应用手写数字识别案例，利用KNN算法的简单原理解决如何识别数字。本资源利用数字图片的二值化值作为特征，进行特征提取。通过训练集的二值化特征与测试集的二值化特征的欧式距离，通过排序，选取...
算法：字符串的组合
题目：输入一个字符串，输出该字符串中字符的所有组合。...针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；而是不把这个字符放到组合中...
数据结构与算法

33,008

社区成员

35,326

社区内容

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章