批处理从一组数字中取任意个数字之和在一个数值范围内

caruko

假如有这么一组数字
{51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79}
使其中N个数字的和sum满足  102<sum<105
并打印出来。
好吧，好像难度过高，那么改为可以支持<=40个数字的组合，每个数字<100。

结果如下:

wankoilz

感谢powerbat讲解。确实！我之前还以为批处理递归没有这种“堆栈”的效果，结果测试了一下还真如楼上所说：每次call 都带来一次循环，那些被call阻挡的，没来得及执行的代码似乎被放入类似“堆栈”的结构里，在call完毕之后都陆续被执行了。测试如下：

@echo off&setlocal enabledelayedexpansion
call :lp
pause

:lp
for /l %%a in (1,1,5) do (
    echo %%a
    set/an+=1&if !n! equ 3 call :lp
)
复制代码

第一次for：本该执行5次echo%%a，但执行到3的时候被call :lp阻断了（此时echo 4和echo 5被“存”起来了），接着就完整的执行了一次for，完了把存起来的echo 4和echo 5也执行了，所以有如下结果(用空行分隔了一下，方便分析)：

1
2
3

1
2
3
4
5

4
5
复制代码

而且这种存储确实是按照类似“堆栈”的方式，即“后进先出”，从下面代码，的执行结果就可以看出来：

@echo off&setlocal enabledelayedexpansion
call :lp
pause

:lp
for /l %%a in (1,1,5) do (
    echo %%a
    set/an+=1
    if !n! equ 3 call :lp
    if !n! equ 5 call :lp
)
复制代码

结果(用空行分隔了一下，方便分析)：

1
2
3

1
2

1
2
3
4
5

3
4
5

4
5
复制代码

第一个for，执行到3的时候被call阻断，输出1,2,3（echo 4和echo 5被保存），然后执行第二次for，执行到2的时候n等于5了，再次call，这时输出1,2（echo 3，echo 4，echo 5被保存），然后是最后一个完整的for，输出1,2,3,4,5。完了执行被保存的call（后保存的先执行），输出3,4,5和4,5。
这样看来15楼的代码是很不错的！

powerbat

“调用函数会得到12，123，1234，12345，123456，1234567，12345678。此时跳出函数”
递归函数也有for啊，这个for取第一个值时，通过递归，就得到了12，123，1234，12345，123456，1234567，12345678，还远远没到跳出的时候。每次递归都要带来一次循环，每个循环体里面又要递归……

wankoilz

我的理解是：批处理开始执行第一个for，调用函数会得到12，123，1234，12345，123456，1234567，12345678。此时跳出函数，回到for，再调用函数得到23，234，2345，23456，234567，2345678
我就想知道我在18楼说的123456 8的结果是怎么来的（代码具体是如何执行的），恕我愚钝哪...

powerbat

递归里面用循环，循环体里面又递归调用，这个递归是很多层的。（这种方法很少用，要死很多脑细胞的）
楼上估计是把递归函数第一个语句还要循环给忘了：
for /l %%i in (%i% 1 %N%) do (

wankoilz

抱歉，之前不能上网，自己照着手机在电脑上测试了一下你的代码有点问题，现在直接复制代码测试是没问题的。
看来我还没高清楼上的算法，请教下：楼上代码的运行结果中，从 12，123，1234，12345，123456，1234567，12345678后接着是123456 8 ，为什么会有123456 8这个结果呢（按照我的理解接下来应该是23，234，2345，23456...），不懂...

terse

ters这种方法会漏掉不少组合吧。
假设有1-15这15个数，在取两个数的组合中就只能得到1-2,2-3,3-4,4-5...14-15，而其它的1-3,1-4,1-5...等都漏掉了
wankoilz 发表于 2011-5-13 10:01

怎么会呢?
给个直观点

@echo off
set n=8
for /l %%i in (1 1 %N%) do (
    set /a i=%%i+1
    call :lp "%%i"
)
pause&exit
:lp
for /l %%i in (%i% 1 %N%) do (
     set /a i=%%i+1
     echo %~1 %%i
     if %%i equ %n% exit/b
     CALL :Lp "%~1 %%i"
)
复制代码

wankoilz

ters这种方法会漏掉不少组合吧。
假设有1-15这15个数，在取两个数的组合中就只能得到1-2,2-3,3-4,4-5...14-15，而其它的1-3,1-4,1-5...等都漏掉了

terse

怎么都这样复杂  我这样递归  效率当然不是很好

@echo off&setlocal enabledelayedexpansion
set "var=51 8 13 2 52 61 37 85 19 11 7 62 22 38 79"
for %%i in (%var%) do set /a N+=1&set _!N!=%%i
for /l %%i in (1 1 %N%) do (
    set /a i=%%i+1
    call :lp !_%%i!
)
pause&exit
:lp
for /l %%i in (!i! 1 %N%) do (
     set /a i=%%i+1,M=%~1+_%%i
     if !M! geq 103 if !M! leq 104 echo %~1+!_%%i!=!M!
     if !M! lss 104 CALL%0 "%~1+!_%%i!"
)
复制代码

caruko

其实有想过只用一层循环来解决，通过一些判断来控制参与计算的变量就可以了。
但循环次数需要先计算全排列次数出来，可是全排列的数字超过13个就溢出了。
没有while条件的循环，用goto实际上跟call差不多效率。

wankoilz

是有点复杂，没怎么看懂，不过楼上用的变量嵌套值得学习！
我求组合的思路是：
先随便拿一个元素出来，比如a，它形成的组合就一个a
然后加入b，它与前面所有已有的组合相组合，这里得到ab。加上前面已有的组合a、自身b，所以a和b形成的组合是a,ab,b
接着加入c，和前面一样，先得到ac,abc,bc，加上已有的和自身c，所有组合就是a,ab,b,ac,abc,bc,c
接下来是d
.
.
.

powerbat

思路比较普通：先排序，分别从数组中取N个数（1≤N≤num）进行组合（先简单判断是否需要取组合数），再将组合数的和与目标比较。取组合数用的是for嵌套循环（利用bat预处理机制），echo !do!就知道展开后是什么了。

之前形成思维定势，老想着因为数组经过排序，所以如果前一组组合数的和大于max，后面就不用比较了，也即下面的当prior(sum)小于max时才比较：
    set /a prior=sum, sum=0
    if !prior! leq %max% (
        for %%a in (%exp%) do set /a sum+=%%a
        if !sum! geq %min% if !sum! leq %max% echo%exp:,=+%=!sum!
    ）
还有逻辑问题，完全是废代码。

powerbat

思维形成定势了，果然有纰漏。稍作改造如下：

@echo off
set "arr=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79"
set /a min=102, max=105
:main
setlocal enableDelayedExpansion
%const% set MAXNUM=20
for %%a in (%arr%) do set /a num+=1 & set a[!num!]=%%a
if %num% gtr %MAXNUM% echo Are you kidding me?&pause&exit /b %num%
rem 冒泡排序
for /l %%i in (1 1 %num%) do (
    set /a start = %%i + 1
    for /l %%j in (!start! 1 %num%) do if !a[%%i]! gtr !a[%%j]! (
        set tmp=!a[%%i]!
        set a[%%i]=!a[%%j]!
        set a[%%j]=!tmp!
    )
)
rem 为枚举组合数生成for嵌套语句
set letters=[abcdefghijklmnopqrstuvwxyz]
for /l %%a in (1 1 %MAXNUM%) do (
    set var=!letters:~%%a,1!
    if 1==%%a (
        set "set_start=set /a start=00+1"
    ) else (
        set /a base=%%a-1
        for %%i in (!base!) do set base=!letters:~%%i,1!
        set "set_start=set /a start=%%!base!+1"
    )
    set "do=!do!!set_start! & for /l %%!var! in (^!start^!,1,^!num^!) do "
    set "exp=!exp!,^!a[%%!var!]^!"
)
rem echo !do!
rem echo !exp!
rem pause
for /l %%a in (1 1 %num%) do (
    set /a minsum=0, maxsum=0
    for /l %%i in (1 1 %%a) do set /a minsum+=a[%%i], n=num-%%i+1&set /a maxsum+=a[!n!]
    rem echo %%a:[!minsum!,!maxsum!]
    if !minsum! leq %max% if !maxsum! geq %min% (
        set /a do_len=54*%%a, exp_len=8*%%a
        call:enum
    )
)
pause
endlocal&exit/b

:enum
setlocal enableDelayedExpansion
set do=!do:~0,%do_len%!
set exp=!exp:~0,%exp_len%!
%do% (
    set /a sum=0%exp:,=+%
    if !sum! geq %min% if !sum! leq %max% echo%exp:,=+%=!sum!
)
endlocal
goto :eof
复制代码

wankoilz

楼上也说说思路吧，直接看代码头晕

powerbat

我知道是这个意思。
set "arr=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79,  1,2,3"
后面故意加了个重复数字