首页
社区
课程
招聘
[已解决]求一个枚举所有组合算法(很有难度)
发表于: 2012-9-17 08:57 12919

[已解决]求一个枚举所有组合算法(很有难度)

2012-9-17 08:57
12919
************************************************************************
自己研究出来了,答案代码  还是要一切靠自己啊

#include <Windows.h>
#include <stdio.h>
#include <vector>
using namespace std;

BYTE Ndata[10]={'0','1','2','3','4','5','6','7','8','9'};


void SetN(vector<BYTE> data, vector<int> N)
{

int Num = sizeof(Ndata)/sizeof(BYTE);
int szData = data.size();
int szN = N.size();

LPBYTE CopyData = new BYTE[szData+1];//原 data 用来做索引 避开仅用数字
memset(CopyData,0,szData + 1);
memcpy(CopyData,(BYTE *)&data[0],szData);//新 data 用来构造数据

for (int i=0;i<szN;i++)
{
if (N > szData)
{
return;//有一项超出范围 大于数据长度了
}

data[N] = 0;//初始化被设置为N的值为空
}

while(1)
{
for (int i = 1 ; i < Num+1 ; i++ )
{
// 1 **** 0 1,2,3,4,5,6,7,8,9,0
data[N[szN-1]] = i % Num; //只变动最后一位 满位往左进位

CopyData[N[szN-1]] = Ndata[i%Num];//设置最后一位为尾变值 一切从这里开始
printf("%s\n",(char *)CopyData);//输出所有组合
}



for (int i=szN ; i > 0; i--)//检测层数
{

if (data[N[i-1]] == 0)//上一层是否是 0 标志结束要进位
{
if (i-1-1 < 0) //是否还能往上增加
{
delete []CopyData;
return;
}

data[N[i-1-1]] = (data[N[i-1-1]] + 1) % Num; //列出元素索引位置
CopyData[N[i-1-1]] = Ndata[data[N[i-1-1]]];//索引列表

}else
{
break;
}

}

}
}


比如一组数据data = {a,b,c,d,e};

有一个函数 SetN (int arr[])  用来设置对应的 一个或多个N  被设置的位置称为N  N的位置的置将设置成循环变动的(0-9)

int arr[]={2,3};//代表将 data中的 第2位'b'的位置  和第3位'c'的位置置为N

比如SetN (arr)

如果arr属于固定形式的话  那肯定用用这样的代码  arr里面有几个 就用几个for

	int arr[]={2,3};
	BYTE data[]={'a','b','c','d','e'};

	for (int i=0x30;i<0x3A;i++)
	{
		data[arr[0]] = i;
		for (int k=0x30;k<0x3A;k++)
		{
			data[arr[1]] = k;

		}

	}



开始枚举所有组合   输出data为

1.    a,0,0,d,e

2.    a,0,1,d,e
3.    a,0,2,d,e
4.    a,0,3,d,e
5.    a,0,4,d,e
6.    a,0,5,d,e
.......
      a,0,9,d,e
      a,1,0,d,e
      a,1,1,d,e
      a,1,2,d,e
......
      a,2,0,d,e
      a,2,1,d,e
.....一直到...
      a,9,9,d,e

PS: 看到上面这些,有的人说了,设置为 加法呗. 但是这只是个示例. 如果 变动的不是 0- 9 而是设成的其它的一个字符数组呢? 所以0-9只能实现于全数字
看上去就像是 逐渐变大的多个齿轮.  小一级的齿轮转10圈,大一级的齿轮转一圈 逐步往上


现在问题来了
             如果 arr 是动态添加的呢?  比如用户EDIT里面输入  1,3,5就变 1,3,5 位 那就需要3个循环了

如果data很长  那输入 SetN({10,110,200})  变动这三位呢? 甚至更多的


SetN({1,20,50,71,90,130,200});

那又如何枚举组合呢?   因为多加一个 arr成员 就要多一层 for

1个成员位置是
   for

2个成员是 两层嵌套
   for
      for

3个成员是 三层
   for  
       for
         for

4个,5个,6个 依次类推

这个从设计上讲,肯定是没有办法直接在源代码里面设置多少个嵌套的.所以请大家出出主意,只是想弄清楚这种算法设计.代码不做任何实际应用,突然想到自己解决不了这种枚举组合的算法.

通俗易懂版

那再明白一点 假设是在枚举填空 填对了弹提示 "正确"

请填入正确的值在括号内 关键是不知道是什么值 只知道那个在什么范围(0,9) 或者

{A,C,F,G,K,L,B}
里面选择 这时候就要枚举了对吧?


a (_) c (_) f

1 (_) 2 (_) 5(_) 9(_) d(_)

这时候肯定第一时间想到的是把能有的组合都枚举出来吧?

那如果设计一个工具 一个EDIT控件 一个按钮
输入
a N c N f

点击按钮
就开始枚举第一个括号的所有组合

输入
1 N 2 N 5 N 9 N d N
点击按钮
就开始枚举第二个括号的所有组合

前提是不能因为多加了括号就修改源代码加循环.那如果括号很多,那不是整篇代码都是for了? 这里是否涉及一种递归?

我这么打比方或许更明白通俗些

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 6
支持
分享
最新回复 (17)
雪    币: 209
活跃值: (138)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
有明白楼主意思的吗?
2012-9-17 09:23
0
雪    币: 4200
活跃值: (4178)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
更新 我看能不能写得再明白一点点 :)
2012-9-17 09:30
0
雪    币: 209
活跃值: (138)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
看明白点了,有m个备选元素,有n个目标位置,可重复的从m个备选中提取出n个元素形成一个顺序敏感的排列,按照数学原理,共有m的n次方种选择方式

是这样吧?
2012-9-17 10:07
0
雪    币: 4200
活跃值: (4178)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
对的 就是不知道这种枚举算法该怎么写
2012-9-17 10:09
0
雪    币: 209
活跃值: (138)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
如果我理解的没错的话,对任意的m和n,完全可以用有限的嵌套循环来解决。
2012-9-17 10:11
0
雪    币: 209
活跃值: (138)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
试着构思了一种算法,既然总的结果数是可以确定的,即power(m, n),则用一个主循环表示:

for(unsigned index = 0; index < power(m, n); index += 1)

把每一个index理解为一个m进制的数字,则m的位数不会超过n,在m的前面补0,得到一个n位的m进制数字

子循环,分别去m进制数字的每一位
for(unsigned index2 = 0; index2 < n; index2 += 1)

得到的每一位作为偏移值,此值在[0, m)之间,按此偏移在m集合中取元素即得到结果

循环数量:
两层
2012-9-17 10:16
0
雪    币: 4200
活跃值: (4178)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
有点高深,理解一下... 谢谢您先 :)   递归有可行性么?
2012-9-17 10:20
0
雪    币: 209
活跃值: (138)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
递归也行 效率低,运算量太大的话可能栈溢出且不好预测
2012-9-17 10:25
0
雪    币: 4200
活跃值: (4178)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
10
能不能敢情大哥贴一份代码看一下,现在还没能转过弯来  谢谢您了
2012-9-17 10:33
0
雪    币: 209
活跃值: (138)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
11
vc6.0编译

#include <stdio.h>
#include <math.h>

//排列并输出,item为备选元素,m为备选元素个数,n为选择数
void print(char item[], unsigned m, unsigned n)
{
    //宜先对输入参数做可靠性检查,此处略

    //结果总数
    unsigned count = (unsigned)pow(m, n);
    //循环变量
    unsigned index, index2;
    //结果缓冲区,n不要太大,须检查
    char result[100] = "";

    //主循环,count次
    for(index = 0; index < count; index += 1)
    {
        //缓存index为value,因index不可改变
        unsigned value = index;

        //取每一位,按m进制。
        //Todo:此处可以再优化,除法得0时可以快速填充result并跳出子循环
        for(index2 = 0; index2 < n; index2 += 1)
        {
            result[n - index2 - 1] = item[value % m];
            value /= m;
        }

        //输出
        printf("%s\n", result);
    }
}

int main()
{
    //实验数据
    char item[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};

    //排列并输出,未判断参数可靠性
    print(item, 5, 3);

    return 0;
}


结果:
aaa
aab
aac
aad
aae
aba
abb
abc
abd
abe
aca
acb
acc
acd
ace
ada
adb
adc
add
ade
aea
aeb
aec
aed
aee
baa
bab
bac
bad
bae
bba
bbb
bbc
bbd
bbe
bca
bcb
bcc
bcd
bce
bda
bdb
bdc
bdd
bde
bea
beb
bec
bed
bee
caa
cab
cac
cad
cae
cba
cbb
cbc
cbd
cbe
cca
ccb
ccc
ccd
cce
cda
cdb
cdc
cdd
cde
cea
ceb
cec
ced
cee
daa
dab
dac
dad
dae
dba
dbb
dbc
dbd
dbe
dca
dcb
dcc
dcd
dce
dda
ddb
ddc
ddd
dde
dea
deb
dec
ded
dee
eaa
eab
eac
ead
eae
eba
ebb
ebc
ebd
ebe
eca
ecb
ecc
ecd
ece
eda
edb
edc
edd
ede
eea
eeb
eec
eed
eee
Press any key to continue
2012-9-17 10:35
0
雪    币: 209
活跃值: (138)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
内循环还有很大的优化空间,可以缓存每次除法得到的结果序列,这样有很多很多中情形下可以提早跳出子循环。如果做了这个优化,相信数据量越大效率提升越明显。
2012-9-17 10:43
0
雪    币: 4200
活跃值: (4178)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
13
很相近,只是输出有点误差

    char item[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};

    //排列并输出,未判断参数可靠性
    print(item, 5, 3); //这样子表示 只改变第5位和第3位  以 N 改变范围为( 0 - 9 ) 为例 输出如下
输出结果 (5 和 3) 位置可以随便更改顺序. 以第3位的N值开始改变如下:

'a', 'b', '0', 'd', '0', 'f', 'g', 'h', 'i', 'j'
'a', 'b', '0', 'd', '1', 'f', 'g', 'h', 'i', 'j'
'a', 'b', '0', 'd', '2', 'f', 'g', 'h', 'i', 'j'

........
'a', 'b', '0', 'd', '9', 'f', 'g', 'h', 'i', 'j'
'a', 'b', '1', 'd', '0', 'f', 'g', 'h', 'i', 'j'
'a', 'b', '1', 'd', '1', 'f', 'g', 'h', 'i', 'j'
.........
'a', 'b', '9', 'd', '9', 'f', 'g', 'h', 'i', 'j'

不过转换形式貌似很相近.
2012-9-17 11:13
0
雪    币: 209
活跃值: (138)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
14
[QUOTE=Mxixihaha;1102376]很相近,只是输出有点误差

    char item[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};

    //排列并输出,未判断参数可靠性
    print(item, 5, 3); //这样子表示 只改变第5位和第...[/QUOTE]

不是的,我写的5 和 3不是你说的第五和第三
5表示有五个备选元素
3表示有三个括号
我写的只是抽象的算法,具体对应到括号我没考虑
5和3的在你的场景里应用是:
5个填空用的元素 1 2 3 4 5
3个空 a () b () () c
这样从元素中取出三个来填入括号
我提供的算法就是反映了这种填入的顺序
2012-9-17 12:02
0
雪    币: 4200
活跃值: (4178)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
15
嗯,谢谢大哥,但是无法应用到很长的组合里面.

比如    data长度 是 4096 位
而需要改变   第 1000位,1112位 , 1118位 1200位 , 1951位, 3820位 ,4055位

其实跑起来也快,因为枚举的速度与设置的元素多少成正比. 只是不知道不用固定的for怎么写

如果是知道固定的修改个数倒还好,只要是修改的N位置 可能是1个 2个 3个...

像四个要
for (a;;++)
  for(b;;++)
    for(c;;++)
       for(d;;++)
           data[Arr_[3]] = d ;
           data[Arr_[2]] = c ;
           data[Arr_[1]] = b ;
           data[Arr_[0]] = a ;

如果是5个 肯定要继续加 for
6个肯定按这方法还得继续加for

那10个呢?   所以 就得有一种算法 来代替这种 嵌套循环

很明显,手工加for是不现实的, 因为循环的元素需要手工设置.

比如设计理念
vector<int> Arr_n; //定义设置为 N  的位置数组
按上面所说就是 我在界面画一个编辑框 比如我要修改1000位的时候,就输入1000 点按钮添加

Arr_n.push( 1000 )
........

SetN( Arr_n );/ / 这个函数就是难点.
2012-9-17 12:14
0
雪    币: 209
活跃值: (138)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
和data的长度没关系,data的长度是一亿也不影响速度。只要计算出来排列的相对位置,直接填空就是了。

说白了,和用来填充的元素个数和括号数有关。和被插入的data大小无关。
2012-9-17 13:05
0
雪    币: 4200
活跃值: (4178)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
17
嗯嗯.说得非常到点/ 我想过用递归实现 但是还是失败了.
2012-9-17 13:18
0
雪    币: 22
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
18
楼主是想说是求一下,C(n,n)A(n,n)+C(n-1,n)A(n-1,n-1)+...+C(1,n)A(1,1) 这个组合么
2012-10-22 02:21
0
游客
登录 | 注册 方可回帖
返回
//