[挑战]批处理输出若干个字符或数字的排列组合

CrLf · 发表于 2011-5-21 11:51:21

这个很短小。@echo off
call:perm "a b c xy z"
pause

:perm // code by plp
setlocal enabledelayedexpansion&set "s=%~1 "
if "!s: =!" == "" (echo %~2)else for %%b in (%~1)do call:perm "!s:%%b =!" ...
plp626 发表于 2011-4-21 13:48

我现在只要看到能用call的地方，都会想到兄台这段代码，今天就在缘鸟看到一个关于整数划分的问题，感觉很可能可以套用该思路
http://www.autobatch.org/bbs/vie ... &extra=page%3D1
但是写了半天，也没能模仿出来，能否请plp兄用call的办法解题，做个示范呢？以前一直感觉call和goto是累赘，但是现在发现call用好了也可以很强大，所以想学一点这些方面的技巧

523066680 · 发表于 2011-5-21 12:07:10

本帖最后由 523066680 于 2011-5-21 12:39 编辑

在cn-dos做过
arrangement

@echo off
setlocal enabledelayedexpansion
set /p inp="仅支持排列几个普通字符，不要乱输哦:"
call :func "%inp%" ""
pause
exit
:func
if "%~1"=="" (echo _%~2 &goto :eof)
setlocal
set strnow=%~1
set /a lp=0,lpb=lp+1
:lp
call :func "!strnow:~0,%lp%!!strnow:~%lpb%!" "%~2!strnow:~%lp%,1!"
if not "!strnow:~%lpb%!"=="" (
set /a lp+=1,lpb=lp+1
goto :lp
)
endlocal

复制代码

combination

@echo off
call :func "abcd" ""
pause &exit
:func
setlocal
if %1=="" (
if not %2=="" (echo %2)
goto :eof
)
set strnow=%~1
call :func "%strnow:~1%" "%~2%strnow:~0,1%"
call :func "%strnow:~1%" "%~2"
endlocal

复制代码

本来利用批处理可以用变量作为语句执行的特点可以用变量构造多层for ,这样速度很快。
但是排列方面整起来不容易，组合的话倒可以：

@echo off &setlocal enabledelayedexpansion
set element=a b c
:gettitle
for %%x in (%element%) do (
set "fo=for %%%%x in ("%%x" "") do (!fo!"
set end="!end!)"
set result=!result!%%~%%x
)
%fo%
echo "%result%"
%end:"=%
pause

复制代码

caruko · 发表于 2011-5-21 14:54:21

本帖最后由 caruko 于 2011-5-21 14:58 编辑

不用CALL的办法，但目前不支持重复字符，因为用到字符替换，数字比如“2 12” “a ab bf”就会出错。
去重复也可以，但是需要增加一些代码，把字符改成"_2_ _12_"，效率有降低。
纯数字的话，稍改一下效率更快。

@echo off
SETLOCAL ENABLEDELAYEDEXPANSION
set "str=a b c d e f"
for %%i in (%str%) do (
set /a n+=1,_%%i=n
)
echo, !str!
for /l %%a in (1,1,10000000) do (
set "last="&set "flag="&set "pos=0"
for %%b in (!str!) do (
set /a pos+=1
if defined last (
set /a n1=_%%b,n2=_!last!
if !n1! gtr !n2! set flag=!last! !pos!
set "last=%%b"
) else (
set "last=%%b"
)
)
if not defined flag call :end %%a
for /f %%b in ("!flag!") do for %%c in (!str!) do if !_%%c! gtr !_%%b! set "th=%%c"
for /f "tokens=1,3" %%b in ("!flag! !th!") do (
set "temp=!str:%%b=#!"
set "temp=!temp:%%c=%%b!"
set "str=!temp:#=%%c!"
)
set "ppos="&set "cut1="&set "cut2="&set "array="
for %%b in (!str!) do (
set /a ppos+=1
for /f "tokens=2" %%c in ("!flag!") do (
if !ppos! geq %%c (
set "cut2=!cut2! %%b"
) else (
set "cut1=!cut1! %%b"
)
)
)
for %%i in (!cut2!) do (
set "array=%%i !array!"
for %%j in (!array!) do (
if %%i gtr %%j (
set "array=!array:%%i=#!"
set "array=!array:%%j=%%i!"
set "array=!array:#=%%j!"
)
)
)
set str=!cut1! !array!
echo,!str!
)
:end
echo,一共%1个排列.
pause>nul&exit

复制代码

plp626 · 发表于 2011-5-21 15:00:05

16# zm900612

你首先得给问题找到一个递归关系(recursion case)，然后确定初始态（base case），比如n!=n*(n-1)!光有这个递归关系还不行，一定得有个出发点，就是所谓的base case, 它是递归函数终止的标志。

再者，批处理的call又不完全同于C语言的函数，它必须加setlocal后才能保证函数内部变量不影响外部变量。。这会带来不少问题。。批处理的call==娱乐。。
=============================

怎么写完一个递归函数，你又怎么知道自己写的函数是正确的呢？
我引用宋劲彬的一段话：

如果你相信你正在写的递归函数是正确的，并调用它，然后在此基础上写完这个递归函数，那么它就会是正确的，从而值得你相信它正确。

看你说的那个整数划归问题，我还真不好找处一个递归关系。。。

caruko · 发表于 2011-5-21 15:23:27

不用递归的算法，对字符位置敏感，去重复有点麻烦。

CrLf · 发表于 2011-5-21 15:30:58

16# zm900612

你首先得给问题找到一个递归关系(recursion case)，然后确定初始态（base case），比如n!=n*(n-1)!光有这个递归关系还不行，一定得有个出发点，就是所谓的base case, 它是递归函数终止的标志。

...
plp626 发表于 2011-5-21 15:00

嗯，确实，那个题目若用call来解决，我只有个感觉可行的大方向，却整不出一条很有逻辑的明晰的思路。

caruko · 发表于 2011-5-21 16:57:29

本帖最后由 caruko 于 2011-5-21 17:07 编辑

不用CALL，不用递归的办法，应该是批处理最快的方法之一吧，比CALL 递归速度要快3倍以上吧。
但是跳出FOR还是没有好的办法，目前用CALL EXIT退出循环。
不支持重复字符，因为对字符的位置敏感，重复字符的原位置值判断麻烦。

稍作修改，在原字符前后各加一个@，以保证不会意外的替换掉字符的一部分，只要字符不带@以及特殊字符即可。

代码可以得到任意字符的一个排列的下一个排列，或者得到第N个排列，比如排列字符为abcdef，现求 abdfec 的下一个排列，只要在初始化位置值后，替换STR为abdfec，计算一次以后即得到 abecdf。

支持多字符元素的组合，如代码：

@echo off&SETLOCAL ENABLEDELAYEDEXPANSION
set "str=1 11 12 a ab acd"
set time1=!time!
for %%i in (%str%) do (
set /a n+=1,_@%%i@=n
set "tstr=!tstr! @%%i@"
)
set "str=!tstr!"
echo,!str:@=!
for /l %%a in (1,1,10000000) do (
set "last="&set "flag="&set "pos=0"
for %%b in (!str!) do (
set /a pos+=1
if defined last (
set /a n1=_%%b,n2=_!last!
if !n1! gtr !n2! set flag=!last! !pos!
set "last=%%b"
) else (
set "last=%%b"
)
)
if not defined flag call :end %%a
for /f %%b in ("!flag!") do for %%c in (!str!) do if !_%%c! gtr !_%%b! set "th=%%c"
for /f "tokens=1,3" %%b in ("!flag! !th!") do (
set "temp=!str:%%b=#!"
set "temp=!temp:%%c=%%b!"
set "str=!temp:#=%%c!"
)
set "ppos="&set "cut1="&set "cut2="&set "array="
for %%b in (!str!) do (
set /a ppos+=1
for /f "tokens=2" %%c in ("!flag!") do (
if !ppos! geq %%c (
set "cut2=!cut2! %%b"
) else (
set "cut1=!cut1! %%b"
)
)
)
for %%i in (!cut2!) do (
set "array=%%i !array!"
for %%j in (!array!) do (
if %%i gtr %%j (
set "array=!array:%%i=#!"
set "array=!array:%%j=%%i!"
set "array=!array:#=%%j!"
)
)
)
set str=!cut1! !array!
echo,!str:@=!
)
:end
echo,一共%1个排列. !time1!--^>!time!
pause>nul&exit

复制代码

523066680 · 发表于 2011-5-21 17:12:29

哪位能把for 语句构造到变量里边去，然后替换执行的。
会很有戏哦
@echo off
for %%a in (a b c) do (
for %%b in (a b c) do (
for %%c in (a b c) do (
if not %%a==%%b (
if not %%b==%%c (
if not %%a==%%c (
echo %%a%%b%%c
)))
)))
pause
)

caruko · 发表于 2011-5-21 17:22:04

23# 523066680

@echo off
set a=%%a&set b=%%b&set c=%%c
set "fo=for %a% in (a b c) do for %b% in (a b c) do for %c% in (a b c) do if not %a%==%b% if not %b%==%c% if not %a%==%c% echo %a%%b%%c%"
%fo%

复制代码

plp626 · 发表于 2011-5-21 17:44:11

本帖最后由 plp626 于 2011-5-22 09:25 编辑

批处理的makefunction 特性：（利用netben版主首创的内敛函数技巧）

@echo off&setlocal EnableDelayedExpansion
call:makefun _perm "a b c d xy"
%_perm%
pause&exit
:makefun <funname> <"charlist">
Set n=-1&Set s0=%~2&Set p=&set f=&for %%a in (%~2)do Set/a n+=1
for /l %%a in (0 1 %n%)do (Set/a m=%%a+1
Set "f=!f!&for %%%%a in (^!s%%a^!)do Set s!m!=^!s%%a:%%%%a=^!"
Set p=!p! %%%%a)
set %1=!f:~1,-15!ECHO !p!&goto:eof

复制代码

caruko · 发表于 2011-5-21 18:09:46

=.=
好高明的算法，看了半天还没弄明白

CrLf · 发表于 2011-5-21 23:37:11

24# caruko
晕，原来你们早就想到了，我刚才一直没看这个贴子，不小心侵权（虽然确实是自己想的不过思路撞车是事实，而且我贴子发得比较晚…），明天上了电脑再编辑那个贴子。还有，plp兄发的函数我没看懂，明个也好好研究下

wankoilz · 发表于 2011-5-22 09:25:47

呵呵，思路撞车很正常，楼上不必在意！
plp的代码确实是不一般的精致啊，PF！！

plp626 · 发表于 2011-5-22 09:32:39

27# zm900612

注意看17楼第三个代码，我的和他的思路基本一致。。。

powerbat · 发表于 2011-5-22 11:04:24

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

		自动登录	找回密码
密码			注册

[新手上路]批处理新手入门导读	[视频教程]批处理基础视频教程	[视频教程]VBS基础视频教程	[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动	[批处理精品]CMD命令50条不能说的秘密	[在线下载]第三方命令行工具	[在线帮助]VBScript / JScript 在线参考

[数值计算] [挑战]批处理输出若干个字符或数字的排列组合

评分

评分

评分

null

浏览过的版块