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

caruko

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

结果如下:

caruko

算了，我自己放一组代码吧。

@ECHO OFF&SETLOCAL ENABLEDELAYEDEXPANSION
set "sz=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79"
for %%i in (!sz!) do (
      set "array=_%%i_ !array!"
      for %%j in (!array!) do (
          for /f "delims=_" %%k in ("%%j") do (
              if %%i gtr %%k (
                  set "array=!array:_%%i_=#!"
                  set "array=!array:_%%k_=_%%i_!"
                  set "array=!array:#=_%%k_!"
              )
           )
      )
)
set "array=!array:_=!"&for %%i in (!array!) do (
      if %%i lss 58 (
          set /a n+=1
          set "min_!n!=%%i"
      ) else (
          set "_max=!_max! %%i"
      )
)
for %%i in (0 !_max!) do (
    call :loop %%i !n!
)
goto :eof


:loop [next] [cut]
for /l %%n in (%2,-1,1) do (
    set str=%1+!min_%%n!
    if %1 equ 0 set str=!min_%%n!
    set /a v=!str!
    if !v! lss 105 if !v! gtr 102 echo,!str!=!v!
    if !v! lss 103 (
            set /a cut=%%n-1
            call :loop !str! !cut!
     )
)
复制代码

wankoilz

楼主能不能说说大致思路，看代码有点累
我来一个比较笨的方法：
将这15个数字分成两组，小于等于51的10个数字为一组，大于51的5个数字为一组。
求出前一组10个数字的所有组合的和，找出符合102<sum<105 组合。
后一组的5个数中最小的也是52，所以任何一个符合102<sum<105 的组合都只可能有该分组中的一个数字。
于是把这5个数分别和“前10个数字的所有组合(上一步已保存)”进行组合，找出符合102<sum<105的就行了。

这方法已经近似穷举了，幸好大于等于52的数字有5个，而使得前面只需要找出10个数字的组合。要如果直接求15个数字的所有组合的话就不知要等到猴年马月了！

@echo off&setlocal enabledelayedexpansion
set str=8, 13, 2,  37, 19, 11, 7,  22, 38
set _51=ok
for %%a in (%str%) do (
    for /f "delims=_=" %%b in ('set _') do (
        set/a sum=%%b+%%a
        if !sum! gtr 102 if !sum! lss 105 echo %%b+%%a=!sum!
        if !sum! lss 104 set _%%b+%%a=ok
    )
set _%%a=ok
)
rem 将后5个数字分别与前面所有组合相组合，并求和判断
for %%a in (52, 61,62, 79, 85) do (
    for /f "delims=_=" %%b in ('set _') do (
        set/a sum=%%b+%%a
        if !sum! gtr 102 if !sum! lss 105 echo %%b+%%a=!sum!
))
pause
复制代码

caruko

楼上说的没错，将（最好是53） 作为分界线，可以减少很多计算。
我说说我的算法吧

1：将数字排序，从小到大。
2：分成2个数字组合，>=53的 和 <53的，才发现我写成了58 =.=。
3：从大到小，循环<53的数字组合，递归调用。每循环到一个数字时，计算当前SUM，如果102<sum<105,则输出。如果<103则递归调用余下的数字。

比如 54321 的数字串，循环到5的时候，下一次就循环4321字串，计算5+4的值，再下一次循环321，计算5+4+3。
这主要是为了防止重复。
因为当计算5+3的时候，就不用再计算5+3+4了，直接5+3+2。
以此类推。 如果当前SUM>104，那么则轮空。

其实从小到大循环是最好的，当较小的数的SUM>104时，后面较大的数就可以不用参与计算，跳过循环了，但批处理的跳出机制问题没有采用。

wankoilz

楼主是说>=52吧？
看来思路是大致相同的，主要还是求组合的问题。不过用批处理实现递归，感觉call太多，是不是会影响效率（当然我的代码效率也不见得高）

powerbat

来一个穷举法

@echo off
setlocal enableDelayedExpansion
set "arr=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79"
set /a range1=102, range2=105
for %%a in (%arr%) do set /a num+=1 & set a[!num!]=%%a
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!
    )
)
for /l %%a in (1 1 %num%) do (
    set /a min=0, max=0
    for /l %%i in (1 1 %%a) do set /a min+=a[%%i], n=num-%%i+1&set /a max+=a[!n!]
    if !min! leq %range2% if !max! geq %range1% (
        rem echo %%a:[!min!,!max!]
        call :Arrangement  %%a %num%
    )
)
pause&exit/b

rem 获取排列
:Arrangement [num] [len]
setlocal enableDelayedExpansion
set /a num=%1, len=%2
for /l %%a in (1 1 %num%) do (
    if 1==%%a (set start=1&set "setstart=set start=1&") else (set /a start=%%a-1&set start=%%!start!&set "setstart=set /a start=!start!+1&")
    set "do=!do! !setstart! for /l %%%%a in (^!start^!,1,%len%) do "
    set "exp=!exp!,^!a[%%%%a]^!"
)
%do% (
    set /a prior=sum, sum=0
    if !prior! leq %range2% (
        for %%a in (%exp%) do set /a sum+=%%a
        if !sum! geq %range1% if !sum! leq %range2% echo%exp:,=+%=!sum!
    )
)
endlocal
goto :eof
复制代码

powerbat

思维稍乱，重新整理了一下

@echo off
set "arr=51, 8, 13, 2, 52, 61, 37, 85, 19, 11, 7, 62, 22, 38, 79,  1,2,3"
set /a range1=102, range2=105
:main
setlocal enableDelayedExpansion
for %%a in (%arr%) do set /a num+=1 & set a[!num!]=%%a
if %num% gtr 20 echo Are you killing 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!
    )
)
for /l %%a in (1 1 %num%) do (
    set /a min=0, max=0
    for /l %%i in (1 1 %%a) do set /a min+=a[%%i], n=num-%%i+1&set /a max+=a[!n!]
    if !min! leq %range2% if !max! geq %range1% (
        rem echo %%a:[!min!,!max!]
        call :Combination  %%a %num%
    )
)
pause
endlocal&exit/b

rem 获取组合
:Combination [num] [len]
%static% set letters=[abcdefghijklmnopqrstuvwxyz]
setlocal enableDelayedExpansion
set /a num=%1, len=%2
for /l %%a in (1 1 %num%) do (
    set var=!letters:~%%a,1!
    if 1==%%a (
        set "set_start=set start=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,%len%) do "
    set "exp=!exp!,^!a[%%!var!]^!"
)
%do% (
    set /a prior=sum, sum=0
    if !prior! leq %range2% (
        for %%a in (%exp%) do set /a sum+=%%a
        if !sum! geq %range1% if !sum! leq %range2% echo%exp:,=+%=!sum!
    )
)
endlocal
goto :eof
复制代码

caruko

好吧，其实我忘了说。。
每个数字只用一次来的。。

powerbat

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

wankoilz

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

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
复制代码

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!
    ）
还有逻辑问题，完全是废代码。

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
.
.
.

caruko

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

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!"
)
复制代码