从10个不同的球里面选择5个球，把全部结果打印出来，并且打印共有多少种方法。
有这样一个需求，有10个不同的球：01,02,03,10,12,15,17,20,25,33。现在想从这10个球里面选择5个球，把所有的组合打印到控制台，并且统计一下共有多少注。
比如选择的是01,02,03,20,25
02,03,10,15,17。
01,10,20,25,33。
......
用C语言或者C++
01, 02, 03, 10, 12
01, 02, 03, 10, 15
01, 02, 03, 12, 15
01, 02, 10, 12, 15
01, 03, 10, 12, 15
02, 03, 10, 12, 15
01, 02, 03, 10, 17
01, 02, 03, 12, 17
01, 02, 10, 12, 17
01, 03, 10, 12, 17
02, 03, 10, 12, 17
01, 02, 03, 15, 17
01, 02, 10, 15, 17
01, 03, 10, 15, 17
02, 03, 10, 15, 17
01, 02, 12, 15, 17
01, 03, 12, 15, 17
02, 03, 12, 15, 17
01, 10, 12, 15, 17
02, 10, 12, 15, 17
03, 10, 12, 15, 17
01, 02, 03, 10, 20
01, 02, 03, 12, 20
01, 02, 10, 12, 20
01, 03, 10, 12, 20
02, 03, 10, 12, 20
01, 02, 03, 15, 20
01, 02, 10, 15, 20
01, 03, 10, 15, 20
02, 03, 10, 15, 20
01, 02, 12, 15, 20
01, 03, 12, 15, 20
02, 03, 12, 15, 20
01, 10, 12, 15, 20
02, 10, 12, 15, 20
03, 10, 12, 15, 20
01, 02, 03, 17, 20
01, 02, 10, 17, 20
01, 03, 10, 17, 20
02, 03, 10, 17, 20
01, 02, 12, 17, 20
01, 03, 12, 17, 20
02, 03, 12, 17, 20
01, 10, 12, 17, 20
02, 10, 12, 17, 20
03, 10, 12, 17, 20
01, 02, 15, 17, 20
01, 03, 15, 17, 20
02, 03, 15, 17, 20
01, 10, 15, 17, 20
02, 10, 15, 17, 20
03, 10, 15, 17, 20
01, 12, 15, 17, 20
02, 12, 15, 17, 20
03, 12, 15, 17, 20
10, 12, 15, 17, 20
01, 02, 03, 10, 25
01, 02, 03, 12, 25
01, 02, 10, 12, 25
01, 03, 10, 12, 25
02, 03, 10, 12, 25
01, 02, 03, 15, 25
01, 02, 10, 15, 25
01, 03, 10, 15, 25
02, 03, 10, 15, 25
01, 02, 12, 15, 25
01, 03, 12, 15, 25
02, 03, 12, 15, 25
01, 10, 12, 15, 25
02, 10, 12, 15, 25
03, 10, 12, 15, 25
01, 02, 03, 17, 25
01, 02, 10, 17, 25
01, 03, 10, 17, 25
02, 03, 10, 17, 25
01, 02, 12, 17, 25
01, 03, 12, 17, 25
02, 03, 12, 17, 25
01, 10, 12, 17, 25
02, 10, 12, 17, 25
03, 10, 12, 17, 25
01, 02, 15, 17, 25
01, 03, 15, 17, 25
02, 03, 15, 17, 25
01, 10, 15, 17, 25
02, 10, 15, 17, 25
03, 10, 15, 17, 25
01, 12, 15, 17, 25
02, 12, 15, 17, 25
03, 12, 15, 17, 25
10, 12, 15, 17, 25
01, 02, 03, 20, 25
01, 02, 10, 20, 25
01, 03, 10, 20, 25
02, 03, 10, 20, 25
01, 02, 12, 20, 25
01, 03, 12, 20, 25
02, 03, 12, 20, 25
01, 10, 12, 20, 25
02, 10, 12, 20, 25
03, 10, 12, 20, 25
01, 02, 15, 20, 25
01, 03, 15, 20, 25
02, 03, 15, 20, 25
01, 10, 15, 20, 25
02, 10, 15, 20, 25
03, 10, 15, 20, 25
01, 12, 15, 20, 25
02, 12, 15, 20, 25
03, 12, 15, 20, 25
10, 12, 15, 20, 25
01, 02, 17, 20, 25
01, 03, 17, 20, 25
02, 03, 17, 20, 25
01, 10, 17, 20, 25
02, 10, 17, 20, 25
03, 10, 17, 20, 25
01, 12, 17, 20, 25
02, 12, 17, 20, 25
03, 12, 17, 20, 25
10, 12, 17, 20, 25
01, 15, 17, 20, 25
02, 15, 17, 20, 25
03, 15, 17, 20, 25
10, 15, 17, 20, 25
12, 15, 17, 20, 25
01, 02, 03, 10, 33
01, 02, 03, 12, 33
01, 02, 10, 12, 33
01, 03, 10, 12, 33
02, 03, 10, 12, 33
01, 02, 03, 15, 33
01, 02, 10, 15, 33
01, 03, 10, 15, 33
02, 03, 10, 15, 33
01, 02, 12, 15, 33
01, 03, 12, 15, 33
02, 03, 12, 15, 33
01, 10, 12, 15, 33
02, 10, 12, 15, 33
03, 10, 12, 15, 33
01, 02, 03, 17, 33
01, 02, 10, 17, 33
01, 03, 10, 17, 33
02, 03, 10, 17, 33
01, 02, 12, 17, 33
01, 03, 12, 17, 33
02, 03, 12, 17, 33
01, 10, 12, 17, 33
02, 10, 12, 17, 33
03, 10, 12, 17, 33
01, 02, 15, 17, 33
01, 03, 15, 17, 33
02, 03, 15, 17, 33
01, 10, 15, 17, 33
02, 10, 15, 17, 33
03, 10, 15, 17, 33
01, 12, 15, 17, 33
02, 12, 15, 17, 33
03, 12, 15, 17, 33
10, 12, 15, 17, 33
01, 02, 03, 20, 33
01, 02, 10, 20, 33
01, 03, 10, 20, 33
02, 03, 10, 20, 33
01, 02, 12, 20, 33
01, 03, 12, 20, 33
02, 03, 12, 20, 33
01, 10, 12, 20, 33
02, 10, 12, 20, 33
03, 10, 12, 20, 33
01, 02, 15, 20, 33
01, 03, 15, 20, 33
02, 03, 15, 20, 33
01, 10, 15, 20, 33
02, 10, 15, 20, 33
03, 10, 15, 20, 33
01, 12, 15, 20, 33
02, 12, 15, 20, 33
03, 12, 15, 20, 33
10, 12, 15, 20, 33
01, 02, 17, 20, 33
01, 03, 17, 20, 33
02, 03, 17, 20, 33
01, 10, 17, 20, 33
02, 10, 17, 20, 33
03, 10, 17, 20, 33
01, 12, 17, 20, 33
02, 12, 17, 20, 33
03, 12, 17, 20, 33
10, 12, 17, 20, 33
01, 15, 17, 20, 33
02, 15, 17, 20, 33
03, 15, 17, 20, 33
10, 15, 17, 20, 33
12, 15, 17, 20, 33
01, 02, 03, 25, 33
01, 02, 10, 25, 33
01, 03, 10, 25, 33
02, 03, 10, 25, 33
01, 02, 12, 25, 33
01, 03, 12, 25, 33
02, 03, 12, 25, 33
01, 10, 12, 25, 33
02, 10, 12, 25, 33
03, 10, 12, 25, 33
01, 02, 15, 25, 33
01, 03, 15, 25, 33
02, 03, 15, 25, 33
01, 10, 15, 25, 33
02, 10, 15, 25, 33
03, 10, 15, 25, 33
01, 12, 15, 25, 33
02, 12, 15, 25, 33
03, 12, 15, 25, 33
10, 12, 15, 25, 33
01, 02, 17, 25, 33
01, 03, 17, 25, 33
02, 03, 17, 25, 33
01, 10, 17, 25, 33
02, 10, 17, 25, 33
03, 10, 17, 25, 33
01, 12, 17, 25, 33
02, 12, 17, 25, 33
03, 12, 17, 25, 33
10, 12, 17, 25, 33
01, 15, 17, 25, 33
02, 15, 17, 25, 33
03, 15, 17, 25, 33
10, 15, 17, 25, 33
12, 15, 17, 25, 33
01, 02, 20, 25, 33
01, 03, 20, 25, 33
02, 03, 20, 25, 33
01, 10, 20, 25, 33
02, 10, 20, 25, 33
03, 10, 20, 25, 33
01, 12, 20, 25, 33
02, 12, 20, 25, 33
03, 12, 20, 25, 33
10, 12, 20, 25, 33
01, 15, 20, 25, 33
02, 15, 20, 25, 33
03, 15, 20, 25, 33
10, 15, 20, 25, 33
12, 15, 20, 25, 33
01, 17, 20, 25, 33
02, 17, 20, 25, 33
03, 17, 20, 25, 33
10, 17, 20, 25, 33
12, 17, 20, 25, 33
15, 17, 20, 25, 33
Press any key to continue . . .
例如求5中选3的组合：
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5
1
2
3
4
5
6
7
8
9
10
-实现代码
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;
#define FLAG_1 1
#define FLAG_0 0
#define POS_NULL -1
void GetSelectedItems(char *flags, int flagCnt, vector<vector<int> > &vvCombin)
{
if (NULL == flags) return;
vector<int> vecItems;
for (int i = 0; i < flagCnt; ++i)
{
if (flags[i] != FLAG_0) vecItems.push_back(i);
}
vvCombin.push_back(vecItems);
}
int Find10Pos(char *flags, int flagCnt)
{
for (int i = 1; i < flagCnt; ++i)
{
if (flags[i - 1] == FLAG_1 && flags[i] == FLAG_0)
{
return i - 1;
}
}
return -1;
}
void Swap10Pos(char *flags, int pos)
{
//10->01
flags[pos + 0] = FLAG_0;
flags[pos + 1] = FLAG_1;
}
void ShiftToLeft(char *flags, int endPos)
{
int cnt = 0;
for (int i = 0; i < endPos; ++i)
{
if (flags[i] == FLAG_1)
{
++cnt;
flags[i] = FLAG_0;
}
}
for (int i = 0; i < cnt; ++i)
{
flags[i] = FLAG_1;
}
}
bool Select(int n, int m, vector<vector<int> > &vvOut)
{
if (m > n) return false;
vvOut.clear();
char *flags = new char[n];
if (NULL == flags) return false;
memset(flags, false, n);
for (int i = 0; i < m; ++i)
{
flags[i] = true;
}
GetSelectedItems(flags, n, vvOut);
int pos = Find10Pos(flags, n);
while (pos != POS_NULL)
{
Swap10Pos(flags, pos);
ShiftToLeft(flags, pos);
GetSelectedItems(flags, n, vvOut);
pos = Find10Pos(flags, n);
}
delete[]flags;
return true;
}
void main()
{
vector<vector<int> > vvCombin;
Select(10, 3, vvCombin);
int nTotalCnt = 0;
for (size_t i = 0; i < vvCombin.size(); ++i)
{
vector<int> &vecItems = vvCombin[i];
for (size_t j = 0; j < vecItems.size(); j++)
{
printf_s("%d\t", vecItems[j] + 1);
}
printf_s("\n");
++nTotalCnt;
}
printf_s("Total count:%d\n", nTotalCnt);
}
C++从N个数中取M个的组合
#include "stdafx.h"
#include <stdlib.h>
//定义一个辅助数组，用来临时存放每一种组合结果
int temp[100];
FILE * fout;
//输出数据
void Display(int *a,int n)
{
for(int i=n;i>=0;i--)
{
fprintf(fout,"%d ",a[i]);
printf("%d ",a[i]);
}
fprintf(fout,"\n");
printf("\n");
}
//通过递归实现 num记录抽取球的个数，开始的时候num=k
void combination(int n,int k,const int num)
{
int a[10]={0};
int i,j;
for(i=n;i>=k;i--)
{
temp[k-1] = i; //记录一个位置
if(k>1)
combination(i-1,k-1,num);
else
{
for(j=num-1;j>=0;j--)
a[j]=temp[j];
Display(a,num-1);
}
}
}
int main()
{
fout=fopen("output.txt","w");
combination(15,6,6);
fclose(fout);
fout==NULL;
system("pause");
return 0;
}
// Q688344.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
string balls[] = { "01", "02", "03", "10", "12", "15", "17", "20", "25", "33" };
typedef void (*ONFINDFUNC)(string);
#define N 5
#define CNT 10
void solve(string feed, int start, int n, ONFINDFUNC f)
{
if (n == 0)
{
f(feed);
}
else
{
for (int i = start; i < CNT; i++)
{
string feed1 = "";
feed1 += feed;
feed1 += balls[i];
solve(feed1, i + 1, n - 1, f);
}
}
}
int resN;
void _find(string s)
{
cout << s.c_str() << endl;
resN++;
}
int _tmain(int argc, _TCHAR* argv[])
{
resN = 0;
solve("", 0, N, _find);
cout << "total:" << resN << endl;
return 0;
}
0102031012
0102031015
0102031017
0102031020
0102031025
0102031033
0102031215
0102031217
0102031220
0102031225
0102031233
0102031517
0102031520
0102031525
0102031533
0102031720
0102031725
0102031733
0102032025
0102032033
0102032533
0102101215
0102101217
0102101220
0102101225
0102101233
0102101517
0102101520
0102101525
0102101533
0102101720
0102101725
0102101733
0102102025
0102102033
0102102533
0102121517
0102121520
0102121525
0102121533
0102121720
0102121725
0102121733
0102122025
0102122033
0102122533
0102151720
0102151725
0102151733
0102152025
0102152033
0102152533
0102172025
0102172033
0102172533
0102202533
0103101215
0103101217
0103101220
0103101225
0103101233
0103101517
0103101520
0103101525
0103101533
0103101720
0103101725
0103101733
0103102025
0103102033
0103102533
0103121517
0103121520
0103121525
0103121533
0103121720
0103121725
0103121733
0103122025
0103122033
0103122533
0103151720
0103151725
0103151733
0103152025
0103152033
0103152533
0103172025
0103172033
0103172533
0103202533
0110121517
0110121520
0110121525
0110121533
0110121720
0110121725
0110121733
0110122025
0110122033
0110122533
0110151720
0110151725
0110151733
0110152025
0110152033
0110152533
0110172025
0110172033
0110172533
0110202533
0112151720
0112151725
0112151733
0112152025
0112152033
0112152533
0112172025
0112172033
0112172533
0112202533
0115172025
0115172033
0115172533
0115202533
0117202533
0203101215
0203101217
0203101220
0203101225
0203101233
0203101517
0203101520
0203101525
0203101533
0203101720
0203101725
0203101733
0203102025
0203102033
0203102533
0203121517
0203121520
0203121525
0203121533
0203121720
0203121725
0203121733
0203122025
0203122033
0203122533
0203151720
0203151725
0203151733
0203152025
0203152033
0203152533
0203172025
0203172033
0203172533
0203202533
0210121517
0210121520
0210121525
0210121533
0210121720
0210121725
0210121733
0210122025
0210122033
0210122533
0210151720
0210151725
0210151733
0210152025
0210152033
0210152533
0210172025
0210172033
0210172533
0210202533
0212151720
0212151725
0212151733
0212152025
0212152033
0212152533
0212172025
0212172033
0212172533
0212202533
0215172025
0215172033
0215172533
0215202533
0217202533
0310121517
0310121520
0310121525
0310121533
0310121720
0310121725
0310121733
0310122025
0310122033
0310122533
0310151720
0310151725
0310151733
0310152025
0310152033
0310152533
0310172025
0310172033
0310172533
0310202533
0312151720
0312151725
0312151733
0312152025
0312152033
0312152533
0312172025
0312172033
0312172533
0312202533
0315172025
0315172033
0315172533
0315202533
0317202533
1012151720
1012151725
1012151733
1012152025
1012152033
1012152533
1012172025
1012172033
1012172533
1012202533
1015172025
1015172033
1015172533
1015202533
1017202533
1215172025
1215172033
1215172533
1215202533
1217202533
1517202533
total:252
Press any key to continue . . .
using namespace std;
void initVecItems(vector &vecItems)
{
// 01,02,03,10,12,15,17,20,25,33
vecItems.push_back(1);
vecItems.push_back(2);
vecItems.push_back(3);
vecItems.push_back(10);
vecItems.push_back(12);
vecItems.push_back(15);
vecItems.push_back(17);
vecItems.push_back(20);
vecItems.push_back(25);
vecItems.push_back(33);
}
int getStartNumber(int iTotal, int iSelect)
{
int iResNumber = 0;
if (iTotal < iSelect) {
return iResNumber;
}
for (int i = iSelect - 1; i >= 0; --i) {
iResNumber += pow(2, i);
}
return iResNumber;
}
int getEndNumber(int iTotal, int iSelect)
{
int iResNumber = 0;
if (iTotal < iSelect) {
return iResNumber;
}
for (int i = iTotal - 1; i >= iTotal - iSelect; --i) {
iResNumber += pow(2, i);
}
return iResNumber;
}
int get2ByteOneCount(int iDecimalValue)
{
int iResCount = 0;
while(iDecimalValue) {
iDecimalValue &= (iDecimalValue - 1);
++iResCount;
}
return iResCount;
}
void get2ByteOneIndex(int iDecimalValue, vector &vecIndex)
{
int iIndex = 0;
while(iDecimalValue) {
if (iDecimalValue & 0x01) {
vecIndex.push_back(iIndex);
}
++iIndex;
iDecimalValue >>= 1;
}
}
void printCombinSerial(vector vecIndex, vector vecItems)
{
for (vector::iterator iter = vecIndex.begin(); iter != vecIndex.end(); ++iter) {
if (iter != vecIndex.begin()) {
cout << ",";
}
cout << setw(2) << setfill('0') << vecItems[*iter];
}
cout << endl;
}
int main(int argc, char* argv[])
{
vector vecItems;
initVecItems(vecItems);
int iTotal = 10;
int iSelect = 5;
int iStartNumber = getStartNumber(iTotal, iSelect);
cout << iStartNumber << endl;
int iEndNumber = getEndNumber(iTotal, iSelect);
cout << iEndNumber << endl;
vector<int> vecIndex;
int iTotalCount = 0;
for (int i = iStartNumber; i <= iEndNumber; ++i) {
if (iSelect == get2ByteOneCount(i)) {
vecIndex.clear();
get2ByteOneIndex(i, vecIndex);
printCombinSerial(vecIndex, vecItems);
++iTotalCount;
}
}
cout << "TotalCount:" << iTotalCount << endl;
}