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

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

2012-9-17 08:57
13013

************************************************************************
自己研究出来了,答案代码  还是要一切靠自己啊

	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;

		}

	}


[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

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

是这样吧?
2012-9-17 10:07
0
雪    币: 4333
活跃值: (4323)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
对的 就是不知道这种枚举算法该怎么写
2012-9-17 10:09
0
雪    币: 209
活跃值: (143)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
如果我理解的没错的话,对任意的m和n,完全可以用有限的嵌套循环来解决。
2012-9-17 10:11
0
雪    币: 209
活跃值: (143)
能力值: ( 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
雪    币: 4333
活跃值: (4323)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
有点高深,理解一下... 谢谢您先 :)   递归有可行性么?
2012-9-17 10:20
0
雪    币: 209
活跃值: (143)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
递归也行 效率低,运算量太大的话可能栈溢出且不好预测
2012-9-17 10:25
0
雪    币: 4333
活跃值: (4323)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
10
能不能敢情大哥贴一份代码看一下,现在还没能转过弯来  谢谢您了
2012-9-17 10:33
0
雪    币: 209
活跃值: (143)
能力值: ( 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
活跃值: (143)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
内循环还有很大的优化空间,可以缓存每次除法得到的结果序列,这样有很多很多中情形下可以提早跳出子循环。如果做了这个优化,相信数据量越大效率提升越明显。
2012-9-17 10:43
0
雪    币: 4333
活跃值: (4323)
能力值: ( 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
活跃值: (143)
能力值: ( 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
雪    币: 4333
活跃值: (4323)
能力值: ( 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
活跃值: (143)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
和data的长度没关系,data的长度是一亿也不影响速度。只要计算出来排列的相对位置,直接填空就是了。

说白了,和用来填充的元素个数和括号数有关。和被插入的data大小无关。
2012-9-17 13:05
0
雪    币: 4333
活跃值: (4323)
能力值: ( 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
游客
登录 | 注册 方可回帖
返回
//