在批处理脚本中实现的蛮力算法的优化
Optimization of a Brute Force algorithm implemented in Batch script
此批处理脚本的目的是实现一个简单的蛮力算法，以生成所有可能的 10 个字母数字字符长字符串，并且字符与下一个字符之间没有重复。
set alphanumerics=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,0,1,2,3,4,5,6,7,8,9
for %%l in (%alphanumerics%) do (
for %%m in (%alphanumerics%) do (
for %%n in (%alphanumerics%) do (
for %%o in (%alphanumerics%) do (
for %%p in (%alphanumerics%) do (
for %%q in (%alphanumerics%) do (
for %%r in (%alphanumerics%) do (
for %%s in (%alphanumerics%) do (
for %%t in (%alphanumerics%) do (
for %%u in (%alphanumerics%) do (
if %%u NEQ %%t (
if %%t NEQ %%s (
if %%s NEQ %%r (
if %%r NEQ %%q (
if %%q NEQ %%p (
if %%p NEQ %%o (
if %%o NEQ %%n (
if %%n NEQ %%m (
if %%m NEQ %%l (
echo %%l%%m%%n%%o%%p%%q%%r%%s%%t%%u >> output.txt
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
这个脚本的主要问题是完成任务所需的时间量仍然非常大，因为 for 块尽管有各种 if 分支正在过滤最终输出。因此，我真的很想改进整个脚本，以最佳方式使用所有计算能力而不浪费它。我正在考虑在并行进程之间分配整个算法。或者，基于 2 的幂的字符串生成器：第一步，脚本可以生成并存储所有可能的字符对。
for %%x in (%alphanumerics%) do (
for %%y in (%alphanumerics%) do (
if %%y NEQ %%x (
echo.%%x%%y >> output.txt
)
)
)
然后，在第二步中，它可以使用之前生成的对来匹配它们，从而产生四个字符长的字符串；然后，八个字符长，等等
for /f %%v in (output.txt) do (
set firstvar=%%v
set firstchar=!firstvar:~1!
;First character of the listed couples
for /f "skip=1" %%w in (output.txt) do (
set secondvar=%%w
set secondchar=!secondvar:~0,1!
;Last character of the listed couples
if !secondchar! NEQ !firstchar! (
echo.!firstvar!!secondvar! >> output_2.txt
)
)
)
总之，为了节省时间，我该如何改进这个算法？
下面的解决方案比你的快得多，也许这是在批处理文件中执行此操作的最快方法。
@echo off
setlocal EnableDelayedExpansion
set "alphanumerics=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,0,1,2,3,4,5,6,7,8,9"
(for %%a in (%alphanumerics%) do (
for %%b in (%alphanumerics%) do if %%a neq %%b (
for %%c in (%alphanumerics%) do if %%b neq %%c (
for %%d in (%alphanumerics%) do if %%c neq %%d (
for %%e in (%alphanumerics%) do if %%d neq %%e (
for %%f in (%alphanumerics%) do if %%e neq %%f (
for %%g in (%alphanumerics%) do if %%f neq %%g (
for %%h in (%alphanumerics%) do if %%g neq %%h (
for %%i in (%alphanumerics%) do if %%h neq %%i (
for %%j in (%alphanumerics%) do if %%i neq %%j (
echo %%a%%b%%c%%d%%e%%f%%g%%h%%i%%j
)
)
)
)
)
)
)
)
)
)) > output.txt
您可以提前排除可能的邻居匹配，如下所示。请注意，出于演示目的，alphanumerics 变量中的密码种子被剪切并且输出仅缩小到每万分之一。
@ECHO OFF
SETLOCAL EnableExtensions EnableDelayedExpansion
set "alphanumerics=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,0,1,2,3,4,5,6,7,8,9,"
set "alphanumerics=a,b,c,d,e,A,B,C,D,E,0,1,2,3,4,5,"
set "alphanumerics=a,b,c,A,B,C,0,1,2,"
set "alphanumerics=a,b,A,B,0,1,"
set /A "_counter=0"
rem > output.txt (
for %%l in (%alphanumerics%) do (
set "al=!alphanumerics:%%l,=!"
for %%m in (!al!) do (
set "am=!alphanumerics:%%m,=!"
for %%n in (!am!) do (
set "an=!alphanumerics:%%n,=!"
for %%o in (!an!) do (
set "ao=!alphanumerics:%%o,=!"
for %%p in (!ao!) do (
set "ap=!alphanumerics:%%p,=!"
for %%q in (!ap!) do (
set "aq=!alphanumerics:%%q,=!"
for %%r in (!aq!) do (
set "ar=!alphanumerics:%%r,=!"
for %%s in (!ar!) do (
set "as=!alphanumerics:%%s,=!"
for %%t in (!as!) do (
set "at=!alphanumerics:%%t,=!"
for %%u in (!at!) do (
rem echo %%l%%m%%n%%o%%p%%q%%r%%s%%t%%u
set /A "_counter+=1"
set /A "_inter=_counter %% 100000"
if !_inter! EQU 0 echo %%l%%m%%n%%o%%p%%q%%r%%s%%t%%u !_counter!
)
)
)
)
)
)
)
)
)
)
echo %_counter%
ENDLOCAL
goto :eof
但是，恐怕我们没有足够的时间（还有磁盘 space）来完成您的任务，因为迭代计数呈指数增长甚至更快！
set "alphanumerics=a,b,A,B,0,1," 有 3479922 个可能的 密码 （在几分钟内找到）。要查看增长时间（和 space），这里是使用 set "alphanumerics=a,b,c,A,B,C,0,1,2," 获得的结果的摘录（密码种子中只有三个字符 c,C,2,）：仍然是前导 a经过超过 千万次迭代 ...
acbcB2A21A 9600000
acbAcA2ABc 9700000
acbA121A1A 9800000
acbCB1aBCA 9900000
acb0bcAcba 10000000
acb01abCA1 10100000
acb1c0AcbA 10200000
acb12cABC2 10300000
acb2BacB2b 10400000
acAba0Bc02 10500000
^CacAbAB1bCb 10536175
Terminate batch job (Y/N)? y
26 lowercase + 26 uppercase + 10 digits = 62 characters
如果除了第一个不受前一个字符限制外，每个位置（相邻限制）有61个字符，那么你将不得不生成
(61^9)*62 = 725037057755716742 combinations.
每秒生成 1000000 个组合，您需要 22991 年才能生成完整列表，并且每个值后有 10 个字符和 CRLF 终止符，需要 7728 PB 的存储空间。
但是...
注意 1
脚本已编辑。正如 JosefZ 指出的那样，原始代码失败了，因为批处理文件中的字符串替换不区分大小写（我忘记了）。代码已更改以解决包含 filler 的问题，以便能够区分大小写字符，但不将其包含在输出中。反正错的原码可以在答案末尾找到。
@echo off
setlocal enableextensions disabledelayedexpansion
set "alphanumerics=,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z"
set "alphanumerics=%alphanumerics%,!_!A,!_!B,!_!C,!_!D,!_!E,!_!F,!_!G,!_!H,!_!I,!_!J,!_!K,!_!L,!_!M,!_!N,!_!O,!_!P,!_!Q,!_!R,!_!S,!_!T,!_!U,!_!V,!_!W,!_!X,!_!Y,!_!Z"
set "alphanumerics=%alphanumerics%,0,1,2,3,4,5,6,7,8,9"
set "_="
rem Just for testing : 4*(3^9) = 78732 combinations
set "alphanumerics=,a,b,!_!A,!_!B"
setlocal enabledelayedexpansion
for %%a in (!alphanumerics!
) do for %%b in (!alphanumerics:^,%%a^=!
) do for %%c in (!alphanumerics:^,%%b^=!
) do for %%d in (!alphanumerics:^,%%c^=!
) do for %%e in (!alphanumerics:^,%%d^=!
) do for %%f in (!alphanumerics:^,%%e^=!
) do for %%g in (!alphanumerics:^,%%f^=!
) do for %%h in (!alphanumerics:^,%%g^=!
) do for %%i in (!alphanumerics:^,%%h^=!
) do for %%j in (!alphanumerics:^,%%i^=!
) do echo(%%a%%b%%c%%d%%e%%f%%g%%h%%i%%j
代码执行时，!_!会包含在for可替换参数中，但由于变量_为空，所以不会包含在输出中echo 命令的，在延迟扩展解析器阶段替换为空字符串。
这是答案中的原始（错误）代码。未正确处理 upper/lower 大小写字符串替换。
@echo off
setlocal enableextensions enabledelayedexpansion
rem Changed to include a starting comma
set "alphanumerics=,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,0,1,2,3,4,5,6,7,8,9"
for %%a in (%alphanumerics%
) do for %%b in (!alphanumerics:^,%%a^=!
) do for %%c in (!alphanumerics:^,%%b^=!
) do for %%d in (!alphanumerics:^,%%c^=!
) do for %%e in (!alphanumerics:^,%%d^=!
) do for %%f in (!alphanumerics:^,%%e^=!
) do for %%g in (!alphanumerics:^,%%f^=!
) do for %%h in (!alphanumerics:^,%%g^=!
) do for %%i in (!alphanumerics:^,%%h^=!
) do for %%j in (!alphanumerics:^,%%i^=!
) do echo %%a%%b%%c%%d%%e%%f%%g%%h%%i%%j
注意 2
写完后我发现这与 中的方法相同，但由于过程中没有存储变量应该稍微快一点。
此批处理脚本的目的是实现一个简单的蛮力算法，以生成所有可能的 10 个字母数字字符长字符串，并且字符与下一个字符之间没有重复。
set alphanumerics=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,0,1,2,3,4,5,6,7,8,9
for %%l in (%alphanumerics%) do (
for %%m in (%alphanumerics%) do (
for %%n in (%alphanumerics%) do (
for %%o in (%alphanumerics%) do (
for %%p in (%alphanumerics%) do (
for %%q in (%alphanumerics%) do (
for %%r in (%alphanumerics%) do (
for %%s in (%alphanumerics%) do (
for %%t in (%alphanumerics%) do (
for %%u in (%alphanumerics%) do (
if %%u NEQ %%t (
if %%t NEQ %%s (
if %%s NEQ %%r (
if %%r NEQ %%q (
if %%q NEQ %%p (
if %%p NEQ %%o (
if %%o NEQ %%n (
if %%n NEQ %%m (
if %%m NEQ %%l (
echo %%l%%m%%n%%o%%p%%q%%r%%s%%t%%u >> output.txt
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
这个脚本的主要问题是完成任务所需的时间量仍然非常大，因为 for 块尽管有各种 if 分支正在过滤最终输出。因此，我真的很想改进整个脚本，以最佳方式使用所有计算能力而不浪费它。我正在考虑在并行进程之间分配整个算法。或者，基于 2 的幂的字符串生成器：第一步，脚本可以生成并存储所有可能的字符对。
for %%x in (%alphanumerics%) do (
for %%y in (%alphanumerics%) do (
if %%y NEQ %%x (
echo.%%x%%y >> output.txt
)
)
)
然后，在第二步中，它可以使用之前生成的对来匹配它们，从而产生四个字符长的字符串；然后，八个字符长，等等
for /f %%v in (output.txt) do (
set firstvar=%%v
set firstchar=!firstvar:~1!
;First character of the listed couples
for /f "skip=1" %%w in (output.txt) do (
set secondvar=%%w
set secondchar=!secondvar:~0,1!
;Last character of the listed couples
if !secondchar! NEQ !firstchar! (
echo.!firstvar!!secondvar! >> output_2.txt
)
)
)
总之，为了节省时间，我该如何改进这个算法？
下面的解决方案比你的快得多，也许这是在批处理文件中执行此操作的最快方法。
@echo off
setlocal EnableDelayedExpansion
set "alphanumerics=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,0,1,2,3,4,5,6,7,8,9"
(for %%a in (%alphanumerics%) do (
for %%b in (%alphanumerics%) do if %%a neq %%b (
for %%c in (%alphanumerics%) do if %%b neq %%c (
for %%d in (%alphanumerics%) do if %%c neq %%d (
for %%e in (%alphanumerics%) do if %%d neq %%e (
for %%f in (%alphanumerics%) do if %%e neq %%f (
for %%g in (%alphanumerics%) do if %%f neq %%g (
for %%h in (%alphanumerics%) do if %%g neq %%h (
for %%i in (%alphanumerics%) do if %%h neq %%i (
for %%j in (%alphanumerics%) do if %%i neq %%j (
echo %%a%%b%%c%%d%%e%%f%%g%%h%%i%%j
)
)
)
)
)
)
)
)
)
)) > output.txt
您可以提前排除可能的邻居匹配，如下所示。请注意，出于演示目的，alphanumerics 变量中的密码种子被剪切并且输出仅缩小到每万分之一。
@ECHO OFF
SETLOCAL EnableExtensions EnableDelayedExpansion
set "alphanumerics=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,0,1,2,3,4,5,6,7,8,9,"
set "alphanumerics=a,b,c,d,e,A,B,C,D,E,0,1,2,3,4,5,"
set "alphanumerics=a,b,c,A,B,C,0,1,2,"
set "alphanumerics=a,b,A,B,0,1,"
set /A "_counter=0"
rem > output.txt (
for %%l in (%alphanumerics%) do (
set "al=!alphanumerics:%%l,=!"
for %%m in (!al!) do (
set "am=!alphanumerics:%%m,=!"
for %%n in (!am!) do (
set "an=!alphanumerics:%%n,=!"
for %%o in (!an!) do (
set "ao=!alphanumerics:%%o,=!"
for %%p in (!ao!) do (
set "ap=!alphanumerics:%%p,=!"
for %%q in (!ap!) do (
set "aq=!alphanumerics:%%q,=!"
for %%r in (!aq!) do (
set "ar=!alphanumerics:%%r,=!"
for %%s in (!ar!) do (
set "as=!alphanumerics:%%s,=!"
for %%t in (!as!) do (
set "at=!alphanumerics:%%t,=!"
for %%u in (!at!) do (
rem echo %%l%%m%%n%%o%%p%%q%%r%%s%%t%%u
set /A "_counter+=1"
set /A "_inter=_counter %% 100000"
if !_inter! EQU 0 echo %%l%%m%%n%%o%%p%%q%%r%%s%%t%%u !_counter!
)
)
)
)
)
)
)
)
)
)
echo %_counter%
ENDLOCAL
goto :eof
但是，恐怕我们没有足够的时间（还有磁盘 space）来完成您的任务，因为迭代计数呈指数增长甚至更快！
set "alphanumerics=a,b,A,B,0,1," 有 3479922 个可能的 密码 （在几分钟内找到）。要查看增长时间（和 space），这里是使用 set "alphanumerics=a,b,c,A,B,C,0,1,2," 获得的结果的摘录（密码种子中只有三个字符 c,C,2,）：仍然是前导 a经过超过 千万次迭代 ...
acbcB2A21A 9600000
acbAcA2ABc 9700000
acbA121A1A 9800000
acbCB1aBCA 9900000
acb0bcAcba 10000000
acb01abCA1 10100000
acb1c0AcbA 10200000
acb12cABC2 10300000
acb2BacB2b 10400000
acAba0Bc02 10500000
^CacAbAB1bCb 10536175
Terminate batch job (Y/N)? y
26 lowercase + 26 uppercase + 10 digits = 62 characters
如果除了第一个不受前一个字符限制外，每个位置（相邻限制）有61个字符，那么你将不得不生成
(61^9)*62 = 725037057755716742 combinations.
每秒生成 1000000 个组合，您需要 22991 年才能生成完整列表，并且每个值后有 10 个字符和 CRLF 终止符，需要 7728 PB 的存储空间。
但是...
注意 1
脚本已编辑。正如 JosefZ 指出的那样，原始代码失败了，因为批处理文件中的字符串替换不区分大小写（我忘记了）。代码已更改以解决包含 filler 的问题，以便能够区分大小写字符，但不将其包含在输出中。反正错的原码可以在答案末尾找到。
@echo off
setlocal enableextensions disabledelayedexpansion
set "alphanumerics=,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z"
set "alphanumerics=%alphanumerics%,!_!A,!_!B,!_!C,!_!D,!_!E,!_!F,!_!G,!_!H,!_!I,!_!J,!_!K,!_!L,!_!M,!_!N,!_!O,!_!P,!_!Q,!_!R,!_!S,!_!T,!_!U,!_!V,!_!W,!_!X,!_!Y,!_!Z"
set "alphanumerics=%alphanumerics%,0,1,2,3,4,5,6,7,8,9"
set "_="
rem Just for testing : 4*(3^9) = 78732 combinations
set "alphanumerics=,a,b,!_!A,!_!B"
setlocal enabledelayedexpansion
for %%a in (!alphanumerics!
) do for %%b in (!alphanumerics:^,%%a^=!
) do for %%c in (!alphanumerics:^,%%b^=!
) do for %%d in (!alphanumerics:^,%%c^=!
) do for %%e in (!alphanumerics:^,%%d^=!
) do for %%f in (!alphanumerics:^,%%e^=!
) do for %%g in (!alphanumerics:^,%%f^=!
) do for %%h in (!alphanumerics:^,%%g^=!
) do for %%i in (!alphanumerics:^,%%h^=!
) do for %%j in (!alphanumerics:^,%%i^=!
) do echo(%%a%%b%%c%%d%%e%%f%%g%%h%%i%%j
代码执行时，!_!会包含在for可替换参数中，但由于变量_为空，所以不会包含在输出中echo 命令的，在延迟扩展解析器阶段替换为空字符串。
这是答案中的原始（错误）代码。未正确处理 upper/lower 大小写字符串替换。
@echo off
setlocal enableextensions enabledelayedexpansion
rem Changed to include a starting comma
set "alphanumerics=,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,0,1,2,3,4,5,6,7,8,9"
for %%a in (%alphanumerics%
) do for %%b in (!alphanumerics:^,%%a^=!
) do for %%c in (!alphanumerics:^,%%b^=!
) do for %%d in (!alphanumerics:^,%%c^=!
) do for %%e in (!alphanumerics:^,%%d^=!
) do for %%f in (!alphanumerics:^,%%e^=!
) do for %%g in (!alphanumerics:^,%%f^=!
) do for %%h in (!alphanumerics:^,%%g^=!
) do for %%i in (!alphanumerics:^,%%h^=!
) do for %%j in (!alphanumerics:^,%%i^=!
) do echo %%a%%b%%c%%d%%e%%f%%g%%h%%i%%j
注意 2
写完后我发现这与