Board logo

标题: 【练习-020】批处理根据输入列出组合 [打印本页]

作者: terse    时间: 2008-9-1 01:36     标题: 【练习-020】批处理根据输入列出组合

如输入a b a


输入 a b c d e a b

写了一个效率很不高到7位的话 就要近50秒
难度是要能处理相同字符组合
贴出就加分
2天后来加分
作者: pusofalse    时间: 2008-9-1 02:07

这题的难度好像不在于相同的字符,对我来说,如何排列才是最难的。头疼,排列组合。。。
作者: huahua0919    时间: 2008-9-1 09:40

楼主的a b a 组合其中有相同的,怎么算组合(排列组合不允许有相同的组合)

[ 本帖最后由 huahua0919 于 2008-9-1 09:55 编辑 ]
作者: Batcher    时间: 2008-9-1 10:07     标题: 回复 3楼 的帖子

楼主的题目要求是"列出组合",而不是"列出排列组合",因此应该允许重复的字符出现吧。
作者: flyinspace    时间: 2008-9-1 23:39

原帖由 terse 于 2008-9-1 01:36 发表
如输入a b a
274

输入 a b c d e a b
275
写了一个效率很不高到7位的话 就要近50秒
难度是要能处理相同字符组合
贴出就加分
2天后来加分


去掉重复的?对楼主来说会难么?

再其中的输出加上一句.

if not 输出==true (
      set 输出=true
      echo 输出
)

当然这里我更情愿用临时文件的方法来解决。

type 临时文件 | findstr /r "^输出$"
if errorlevel 1 ***

至于程序算法...天啊。.代码太长了。
作者: terse    时间: 2008-9-2 16:11

原帖由 huahua0919 于 2008-9-1 09:40 发表
楼主的a b a 组合其中有相同的,怎么算组合(排列组合不允许有相同的组合)

可能是我的表述有问题
我的意思是:输入3个字符应该是6种组合  输入4个字符应该是24种组合  输入5个字符应该是120种组合
不管输入有无重复字符 也就是如果输入a a a a a 就要输出120行 a a a a a 实际上最后一行的第一位并不一定是第一排的第一位的a
这样的表述是否清楚?
下面是个效率不错的组合输出:但输入的组合不能有重复字符 而且是固定位数
  1. @echo off&setlocal enabledelayedexpansion
  2. set var=a b c d c d e f
  3. for %%i in (!var!) do (
  4.     set var1=!var:%%i=!
  5.     for %%j in (!var1!) do (
  6.     set var2=!var1:%%j=!
  7.     for %%k in (!var2!) do (
  8.     set var3=!var2:%%k=!
  9.     for %%l in (!var3!) do (
  10.     set var4=!var3:%%l=!
  11.     for %%m in (!var4!) do (
  12.     set var5=!var4:%%m=!
  13.     for %%n in (!var5!) do (
  14.     set var6=!var5:%%n=!
  15.     set/a flag+=1
  16.     echo %%i %%j %%k %%l %%m %%n !var6: =!
  17.     ))))))
  18.     echo 共有%flag%个组合
  19. pause
复制代码

[ 本帖最后由 terse 于 2008-9-2 16:12 编辑 ]
作者: pusofalse    时间: 2008-9-2 16:17

有重复字符很简单啊。
  1. set var=a b c a b
  2. for %%a in (%var%) do set/a nn+=1&set .!nn!=%%a
  3. for /l %%a in (1 1 %nn%) do set "str=!str!%%a "
  4. for %%i in (!str!) do (
  5. ....
  6. ....
  7. echo !.%%i! !.%%j! !.%%k! !.%%l! !.%%m!
复制代码

作者: terse    时间: 2008-9-2 16:36

原帖由 pusofalse 于 2008-9-2 16:17 发表
有重复字符很简单啊。set var=a b c a b
for %%a in (%var%) do set/a nn+=1&set .!nn!=%%a
for /l %%a in (1 1 %nn%) do set "str=!str!%%a "
for %%i in (!str!) do (
....
....
echo !.%%i! !.%%j! !.%%k ...

啊?不会吧!
你的%%j  %%k 是预先写入的?前面虽然得到位数但 并没表示到%%K吧
作者: pusofalse    时间: 2008-9-2 16:49     标题: 回复 8楼 的帖子

  1. @echo off&setlocal enabledelayedexpansion
  2. set str=a b a
  3. for %%a in (%str%) do set /a n+=1& set .!n!=%%a&set "var=!var!!n! "
  4. for %%i in (!var!) do (
  5.     set var1=!var:%%i=!
  6.     for %%j in (!var1!) do (
  7.     set var2=!var1:%%j=!
  8.     for %%k in (!var2!) do (
  9.     set/a flag+=1
  10.     echo !.%%i! !.%%j! !.%%k!
  11.     )))
  12.     echo 共有%flag%个组合
  13. pause
复制代码

作者: batman    时间: 2008-9-2 17:00

一直觉得穷举法不是批处理的强项,尤其是在不知道有多少位数字或字母的情况下,更是难
以写出通用的代码,本人以前写过一个适用于9位内数字或字母排列的代码,实际上到了8位
就已经达到了效率的极限了。。。
作者: terse    时间: 2008-9-2 17:22

原帖由 pusofalse 于 2008-9-2 16:49 发表
@echo off&setlocal enabledelayedexpansion
set str=a b a
for %%a in (%str%) do set /a n+=1& set .!n!=%%a&set "var=!var!!n! "
for %%i in (!var!) do (
    set var1=!var:%%i=!
    for %%j in (!var1!) ...

输入4位  输出时少了一位
确切的是输入3位数上 输出仍输出3位
作者: terse    时间: 2008-9-2 17:24

原帖由 batman 于 2008-9-2 17:00 发表
一直觉得穷举法不是批处理的强项,尤其是在不知道有多少位数字或字母的情况下,更是难
以写出通用的代码,本人以前写过一个适用于9位内数字或字母排列的代码,实际上到了8位
就已经达到了效率的极限了。。。

穷举法确实不是批处理的强项  即便出一个通用的代码 也是效率的代价
作者: pusofalse    时间: 2008-9-2 17:26

这样的题用递归来做比较好些,否则用我这样的方法,还是一样只是穷举,而且不通用,太臃肿,4个字符只能再加一个for,若有5个字符就得用5个for。
完全是不通用的。
作者: terse    时间: 2008-9-3 23:33

抛个砖  这样的处理效率肯定不是很高  后来者突破吧
  1. @echo off&setlocal enabledelayedexpansion
  2. set/p str=请输入(空格隔开)
  3. for %%i in (!str!) do set/a n+=1&set !n!=%%i
  4.     call:lp
  5.     echo %mn% 个组合
  6.     pause&exit
  7. :lp
  8. set/a m+=1
  9.     if %m% leq %n% for /l %%i in (1 1 %n%) do (
  10.     for %%j in (%~1) do set .%%j=%%j
  11.     if not defined .%%i call :lp "%~1 %%i"
  12.     for /l %%k in (1 1 %n%) do set .%%k=
  13.     ) else (
  14.     for /l %%l in (1 1 %n%) do set .%%l=
  15.     for %%m in (%~1) do set/p=!%%m! <nul
  16.     echo.
  17.     set/a mn+=1
  18.     )
  19.     set/a m-=1
复制代码

作者: 523066680    时间: 2008-9-6 10:15

哈哈 可以用来做概率题
作者: batman    时间: 2008-9-6 21:49     标题: 来个另类的

要生成个临时文件b.bat:
  1. @echo off&setlocal enabledelayedexpansion
  2. set /p num=请输入字符:
  3. set "s=abcdefghijklnmopqrstuvwxyz"&set "nums=%num%"
  4. :lp
  5. set /a n+=1
  6. set "str1=%str1% %n%"
  7. set "ss=%ss%str%n%"&set "k=%k%)"
  8. set "_%n%=%num:~,1%"&set "num=%num:~1%"
  9. if defined num goto lp
  10. echo ^@echo off^&setlocal enabledelayedexpansion>b.bat
  11. for /f "skip=1 delims=" %%a in (%~fs0) do (
  12.     set /a x+=1
  13.     if !x! equ 9 goto loop
  14.     if !x! equ 1 (
  15.        echo set "num=%nums%">>b.bat
  16.        ) else (
  17.        if !x! neq 2 if !x! neq 6 echo %%a>>b.bat
  18.     )
  19. )
  20. :loop
  21. set "a=%%%%%s:~,1%"&set "b=%ss:~,4%"&set "c=%ss:~4,4%"
  22. set "str=!str!^!_%a%^!"
  23. if "%c%" equ "" set "c=flag"  
  24. echo for %a% in (^^^!%b%^^^!) do (set "%c%=^!%b%:%a%=^!">>b.bat
  25. set "s=%s:~1%"&set "ss=%ss:~4%"
  26. if defined ss goto loop
  27. echo echo !str!>>b.bat
  28. echo %k%>>b.bat
  29. echo pause^>nul>>b.bat
  30. endlocal&b
复制代码

[ 本帖最后由 batman 于 2008-9-6 22:06 编辑 ]
作者: terse    时间: 2008-9-7 13:53

想给多点分  怎么总是错误啊
作者: pusofalse    时间: 2008-9-7 16:55     标题: 回复 17楼 的帖子

terse前辈是不是输入空格了 abad 要这样的。
作者: caruko    时间: 2011-5-21 15:02

效率还可以,但不支持重复字符。
7个字符,5040组合,用时不到15秒。
  1. @echo off&SETLOCAL ENABLEDELAYEDEXPANSION
  2. set "str=a b c d e f g"
  3. set time1=!time!
  4. for %%i in (%str%) do (
  5.     set /a n+=1,_%%i=n
  6. )
  7. echo, !str!
  8. for /l %%a in (1,1,10000000) do (
  9.     set "last="&set "flag="&set "pos=0"
  10.     for %%b in (!str!) do (
  11.         set /a pos+=1
  12.         if defined last (
  13.             set /a n1=_%%b,n2=_!last!
  14.             if !n1! gtr !n2! set flag=!last! !pos!
  15.             set "last=%%b"
  16.         ) else (
  17.             set "last=%%b"
  18.         )
  19.     )
  20.     if not defined flag call :end %%a
  21.     for /f %%b in ("!flag!") do for %%c in (!str!) do if !_%%c! gtr !_%%b! set "th=%%c"
  22.     for /f "tokens=1,3" %%b in ("!flag! !th!") do (
  23.         set "temp=!str:%%b=#!"
  24.         set "temp=!temp:%%c=%%b!"
  25.         set "str=!temp:#=%%c!"
  26.     )
  27.     set "ppos="&set "cut1="&set "cut2="&set "array="
  28.     for %%b in (!str!) do (
  29.         set /a ppos+=1
  30.         for /f "tokens=2" %%c in ("!flag!") do (
  31.             if !ppos! geq %%c (
  32.                 set "cut2=!cut2! %%b"
  33.             ) else (
  34.                 set "cut1=!cut1! %%b"
  35.             )
  36.         )
  37.     )
  38.     for %%i in (!cut2!) do (
  39.         set "array=%%i !array!"
  40.         for %%j in (!array!) do (
  41.             if %%i gtr %%j (
  42.                 set "array=!array:%%i=#!"
  43.                 set "array=!array:%%j=%%i!"
  44.                 set "array=!array:#=%%j!"
  45.             )
  46.         )
  47.     )
  48.     set str=!cut1! !array!
  49.     echo,!str!
  50. )
  51. :end
  52. echo,一共%1个排列. !time1!--^>!time!
  53. pause>nul&exit
复制代码

作者: wankoilz    时间: 2011-5-21 18:19

本帖最后由 wankoilz 于 2011-5-22 09:05 编辑

既然老帖被挖出来了,俺也来凑热闹。
支持重复字符,我这里测试8个字母40320种组合耗时近4秒:
  1. @echo off&setlocal enabledelayedexpansion
  2. set/p s=请输入,用一个空格分开:
  3. echo %time%
  4. set f1=a.txt
  5. set f2=b.txt
  6. >!f1! echo !s:~,1!&set s=!s:~1!
  7. set len=1
  8. for %%a in (%s%) do (
  9.     (for /f %%b in (!f1!) do (
  10.         set tmp=%%b
  11.         for /l %%c in (0,1,!len!) do echo !tmp:~,%%c!%%a!tmp:~%%c!
  12.     ))>!f2!
  13.     set t=!f1!
  14.     set f1=!f2!
  15.     set f2=!t!
  16.     set/a len+=1
  17. )
  18. echo %time%
  19. start %f1%&del/f %f2%
  20. pause
复制代码

作者: CrLf    时间: 2011-5-21 19:04

本帖最后由 zm900612 于 2011-5-22 13:16 编辑

【该思路已有先例,523066680较早提出】
我认为for嵌套递归始终是最快的方案,所以构思了一个基于for /l递归的新思路,唯一的缺陷是for嵌套理论上限62层[A-Za-z0-9],本代码由于作者偷懒,功能不够强大,仅兼容低于10层,而且不能有重复项...
  1. @echo off&setlocal enabledelayedexpansion
  2. set str= a b c d e f g
  3. set t=%time%
  4. for %%a in (%str%) do (
  5. set /a n+=1,"tmp+=^!tmp"
  6. set "echo=%%!n! !echo!"
  7. )
  8. ::初始化
  9. set "for=for /f %%1 in ("^^!tmp1:%%2 =^^!") do (set /a z+=1)&echo %echo%"
  10. for /l %%a in (2 1 %n%) do (
  11. set /a last=%%a-1
  12. set "for=for %%%%a in (^!tmp%%a^!) do ((set tmp!last!=^!tmp%%a: %%%%a = ^!)&!for!)"
  13. )
  14. ::为str构建相应层数的for嵌套
  15. set tmp%n%=%str%
  16. %for%
  17. ::执行组装而成的for嵌套
  18. echo 共有%z%种组合 开始于%t% 结束于%time%
  19. pause
复制代码

作者: caruko    时间: 2011-5-21 19:13

楼上是字符插入的方法啊。
作者: CrLf    时间: 2011-5-21 19:22

22# caruko


??
不懂...
作者: CrLf    时间: 2011-5-21 19:24

反正5040种组合耗时3秒,应该算不错的成绩了
作者: wankoilz    时间: 2011-5-21 21:06

楼上是字符插入的方法啊。
caruko 发表于 2011-5-21 19:13

是字符插入法。
作者: CrLf    时间: 2011-5-21 21:22

你们怎么会认为是字符插入呢?这段代码和我所理解的字符插入的概念一点关系都没有呀,看来原有的注释太少,弄详细点:
  1. @echo off&setlocal enabledelayedexpansion
  2. set str= a b c d e f g
  3. set t=%time%
  4. for %%a in (%str%) do (
  5.         set /a n+=1,"tmp+=^!tmp"
  6.         set "echo=%%!n! !echo!"
  7. )
  8. ::初始化
  9. set "for=for /f %%1 in ("^^!tmp1:%%2 =^^!") do (set /a z+=1)&echo %echo%"
  10. ::定义最里层的for
  11. for /l %%a in (2 1 %n%) do (
  12.         set /a last=%%a-1
  13.         set "for=for %%%%a in (^!tmp%%a^!) do ((set tmp!last!=^!tmp%%a: %%%%a = ^!)&!for!)"
  14. rem 定义for嵌套,一层包一层...
  15. )
  16. ::为str构建相应层数的for嵌套
  17. set tmp%n%=%str%
  18. %for%
  19. ::执行组装而成的for嵌套,改成echo !for!就明白了
  20. echo 共有%z%种组合 开始于%t% 结束于%time%
  21. pause
复制代码

作者: CrLf    时间: 2011-5-21 21:27

那个%for%运行起来就是这个效果:
  1. @echo off&setlocal enabledelayedexpansion&set tmp5=a b c de f
  2. for %%5 in (!tmp5!) do (
  3. set tmp4=!tmp5:%%5 =!
  4. for %%4 in (!tmp4!) do (
  5. set tmp3=!tmp4:%%4 =!
  6. for %%3 in (!tmp3!) do (
  7. set tmp2=!tmp3:%%3 =!
  8. for %%2 in (!tmp2!) do (
  9. set tmp1=!tmp2:%%2 =!
  10. for /f "delims=" %%1 in ("!tmp1:%%2=!") do (
  11. echo %%5 %%4 %%3 %%2 %%1
  12. )
  13. )
  14. )
  15. )
  16. )
  17. pause
复制代码
很明显是最土的办法...只是我改进思路后,在执行之前可以自动定义层数,然后用一个变量存储了整个for嵌套,实际运行的代码就是这样子:
  1. @echo off&setlocal enabledelayedexpansion&set tmp5=a b c de f
  2. for %%5 in (!tmp5!) do ((set tmp4=!tmp5:%%5 =!)&for %%4 in (!tmp4!) do ((set tmp3=!tmp4:%%4 =!)&for %%3 in (!tmp3!) do ((set tmp2=!tmp3:%%3 =!)&for %%2 in (!tmp2!) do ((set tmp1=!tmp2:%%2 =!)&for /f "delims=" %%1 in ("!tmp1:%%2=!") do echo %%5 %%4 %%3 %%2 %%1 ))))
  3. pause
复制代码

作者: CrLf    时间: 2011-5-21 21:31

噢,发现27楼代码就是6楼代码,只是21楼代码是对这种思路的改进
作者: wankoilz    时间: 2011-5-22 09:02

本帖最后由 wankoilz 于 2011-5-22 09:03 编辑

我是用的字符插入法,呵呵。
楼上构造for嵌套虽然不错,但效率还是不及20楼。
把21楼代码的%for%改成(%for%)>a.txt,且去掉for中的set/a z+=1 之后效率有所提升,测试8个字符40320个组合耗时近8秒。
作者: plp626    时间: 2011-5-22 09:39

要速度就不能call,那么6楼的思路是最快的,

为了短小,我们可以构造一个“制造函数的函数”来制造6楼那个代码,从而支持可变字符个数的排列

16楼和21楼的思路就是如此。。。
作者: powerbat    时间: 2011-5-22 11:06

最老老实实的枚举法没人关注。。。
怎样对字符串进行可重复组合?
http://www.bathome.net/viewthrea ... muid=29086#pid78176
从一组数字中取任意个数字之和在一个数值范围内
http://www.bathome.net/viewthrea ... muid=29086#pid77555
作者: wankoilz    时间: 2011-5-22 11:38

本帖最后由 wankoilz 于 2011-5-22 11:42 编辑

6楼并非最快吧...
把6楼代码构造成求8个字符40320个组合,且去掉set/a flag+=1,耗时8秒。
  1. @echo off&setlocal enabledelayedexpansion
  2. set var=a b c d e f g h
  3. echo %time%
  4. (for %%i in (!var!) do (
  5.     set var1=!var:%%i=!
  6.     for %%j in (!var1!) do (
  7.     set var2=!var1:%%j=!
  8.     for %%k in (!var2!) do (
  9.     set var3=!var2:%%k=!
  10.     for %%l in (!var3!) do (
  11.     set var4=!var3:%%l=!
  12.     for %%m in (!var4!) do (
  13.     set var5=!var4:%%m=!
  14.     for %%n in (!var5!) do (
  15.     set var6=!var5:%%n=!
  16.     for %%o in (!var6!) do (
  17.     set var7=!var6:%%o=!
  18.     for %%p in (!var7!) do (
  19.     echo %%i %%j %%k %%l %%m %%n %%o %%p
  20.     )))))))))>c.txt
  21. echo %time%
  22. pause
复制代码
同样的求8个字符40320个组合,下面的耗时不到4秒:
  1. @echo off&setlocal enabledelayedexpansion
  2. set/p s=请输入,用一个空格分开:
  3. echo %time%
  4. set f1=a.txt
  5. set f2=b.txt
  6. >!f1! echo !s:~,1!&set s=!s:~1!
  7. set len=1
  8. for %%a in (%s%) do (
  9.     (for /f %%b in (!f1!) do (
  10.         set tmp=%%b
  11.         for /l %%c in (0,1,!len!) do echo !tmp:~,%%c!%%a!tmp:~%%c!
  12.     ))>!f2!
  13.     set t=!f1!
  14.     set f1=!f2!
  15.     set f2=!t!
  16.     set/a len+=1
  17. )
  18. echo %time%
  19. start %f1%&del/f %f2%
  20. pause
复制代码
我在想for嵌套得太深了是不是会影响效率...
作者: plp626    时间: 2011-5-22 12:20

32# wankoilz


没测试,
真如你说的话,看来有更快的算法,先收藏。。
作者: CrLf    时间: 2011-5-22 13:39

32楼用偏移的办法确实更好,如果是8个排列项,那这种方法就避开了!7次的set和for /l,从而弥补了for /f频繁读写对效率的影响,这种用for /f从文件读取的思路真是太妙了
作者: wankoilz    时间: 2011-5-22 15:19

本帖最后由 wankoilz 于 2011-5-22 15:20 编辑

32楼的代码来自20楼...
楼上分析的在理,但就32楼代码而言for/f读取算不上频繁吧,8个字符执行7次for/f
作者: CrLf    时间: 2011-5-22 15:56

建议把临时文件名改为纯数字,这样每次循环还可以省去两个set




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