Board logo

标题: [已解决]批处理怎样对字符串进行可重复组合? [打印本页]

作者: yangfengoo    时间: 2011-5-1 10:23     标题: [已解决]批处理怎样对字符串进行可重复组合?

对给定个数字符进行可重复组合
例:set zf=abcdefghijklmnopqrstuvwxyz
如果输入5(不固定) 则从zf 中取5个进行组合:
有:aaaaa;aaaab,aaaac,……zzzzz。
但如aaaac,acaaa,aacaa,caaaa……
     abcde,cdabc,dacbe……

均属重复只要任意一个即可。
说明:1.遍历比较实现应该很简单,但效率太低。希望有高效的方法。
          2.这题如一般排列组合有差别
         3.如果字符不好处理,set zf=0123456789亦可(这个是原题要求,也是我要的),这里要求字符是为了通用性。
--------------------------------------------
感谢powerbat 提供的思路
  1. @echo off
  2. setlocal enableDelayedExpansion
  3. set arr=0123456789
  4. ::len为arr的长度
  5. set len=10
  6. set /p num=需要组合的字数:
  7. set /a num-=1,len-=1
  8. for /l %%a in (0 1 %num%) do (
  9.     if 0==%%a (set start=0) else (set /a start=%%a-1&set start=%%!start!)
  10.     set "do=!do! for /l %%%%a in (!start!,1,%len%) do"
  11.     set "exp=!exp!^!arr:~%%%%a,1^!"
  12. )
  13. %do% echo %exp%
  14. pause
  15. endlocal
复制代码

作者: batman    时间: 2011-5-1 11:48

1# yangfengoo
请问楼主不用遍历如何实现组合?
作者: yangfengoo    时间: 2011-5-1 11:55

本帖最后由 yangfengoo 于 2011-5-1 11:57 编辑

2# batman

这不是在集思广益吗?难道一定要遍历才行?这个问题本来就和一般的组合不同,如果全部遍历一遍有太多重复的数据
作者: mxxcgzxxx    时间: 2011-5-1 13:26

做个简单的,试试
  1. @echo off&setlocal enabledelayedexpansion
  2. set /p a=请输入组合元素:
  3. set "str=%a%"
  4. set /a max=8190,min=0
  5. for /l %%a in (1,1,14) do (
  6.      set /a "num=(max+min)/2"
  7.      for /f "delims=" %%b in ("!num!") do if "!str:~%%b!" equ "" (set /a max=num) else set /a min=num
  8. )
  9. if "!str:~%num%!" neq "" set /a num+=1
  10. :1
  11. set /p b=您需要组合的字数:
  12. set d=0
  13. set "m="
  14. :2
  15. set /a c=!random!%%%num%
  16. set m=%m%!a:~%c%,1!
  17. set /a d+=1
  18. if %d%==%b% goto :3
  19. goto :2
  20. :3
  21. echo %m%
  22. pause
  23. goto :1
复制代码

作者: powerbat    时间: 2011-5-1 16:36

如果字符数多且组合字数多,不知道呈什么级数增长(我数学不太好)。最多处理15个字符:
  1. @echo off
  2. setlocal enableDelayedExpansion
  3. set arr=bathome
  4. set num=5
  5. set /p num=需要组合的字数:
  6. set var=%arr%fedcba9876543210
  7. set /a len=0x%var:~15,1%
  8. set /a numx=num-1, lenx=len-1
  9. for /l %%a in (0 1 %numx%) do (
  10.     if 0==%%a (set start=0) else (set /a start=%%a-1&set start=%%!start!)
  11.     set "do=!do! for /l %%%%a in (!start!,1,%lenx%) do "
  12.     set "exp=!exp!^!arr:~%%%%a,1^!"
  13. )
  14. %do% echo %exp%
  15. pause
  16. endlocal
复制代码

作者: powerbat    时间: 2011-5-1 16:41

说漏了,还有组合字数最多10个
作者: yangfengoo    时间: 2011-5-1 18:11

6# powerbat


思路不错,不过arr的长度被固定了
作者: batman    时间: 2011-5-1 18:26

楼主是否看看这两个贴子:
根据输入进行排列(有字符重复)
http://www.bathome.net/thread-1701-1-4.html
也是排列
http://www.bathome.net/viewthrea ... hlight=%C5%C5%C1%D0
作者: yangfengoo    时间: 2011-5-1 18:32

8# batman


很明显上面的排列不符合我的要求,和我的问题不同。你是否理解了我的要求?
作者: powerbat    时间: 2011-5-1 18:39

字符数和组合字数其实都很好改,只是为了简洁而没有作进一步处理。核心是算法问题。
这个是比较基本的枚举,容易想到,但效率可能不怎么样(本人没研究过算法)
作者: neorobin    时间: 2011-5-1 19:18

本帖最后由 neorobin 于 2011-5-1 19:19 编辑

一种思路(未深入分析):把字符的个数先看作一个和, 先对这个和作 加法式 的分解形式枚举, 再作进一步处理.
例: 5=5, 4+1, 3+2, 3+1+1, 2+3(重复), 2+2+1, 2+1+2(重复), 2+1+1+1, 1+4(重复), 1+3+1(重复), 1+2+2(重复), 1+2+1+1(重复), 1+1+1+1+1
根本上是数论(有没有?), 离散数学类的范畴.
作者: CrLf    时间: 2011-5-1 20:09

一种思路(未深入分析):把字符的个数先看作一个和, 先对这个和作 加法式 的分解形式枚举, 再作进一步处理.
例: 5=5, 4+1, 3+2, 3+1+1, 2+3(重复), 2+2+1, 2+1+2(重复), 2+1+1+1, 1+4(重复), 1+3+1(重复), 1+2+2(重复 ...
neorobin 发表于 2011-5-1 19:18

我的思路和兄台类似,不过我是想把a、b、c这样设置:
set .1=a
set .2=b
set .3=c
然后检查for /l中每个循环的set /a test1=%%a"%%"1,test2=%%a"%%"2,test3=%%a"%%"4,但是只是一个模糊的思路,昨天写了半天竟然发现代码离题了。




欢迎光临 批处理之家 (http://bbs.bathome.net/) Powered by Discuz! 7.2