Board logo

标题: [数值计算] [挑战]批处理输出若干个字符或数字的排列组合 [打印本页]

作者: 舒待子    时间: 2011-4-19 10:20     标题: [挑战]批处理输出若干个字符或数字的排列组合

字符的排列组合,一般地,n个数字(不重复)的全排列有n!个组合方式。
这个应该好理解,比如三个字符:a b c,那么他的全排列的所有组合方式就是
a b c
a c b
b a c
b c a
c a b
c b a
----------------
现在征集代码,对指输入的n个字符,输出它的全排列

看哪个代码最快
那个代码最短小
  1. @echo off&title 输出任意个字符的排列组合
  2. set/p str=输入字符,并用空格隔开
  3. rem ------------------
  4. rem 你的代码
复制代码

作者: batman    时间: 2011-4-19 12:32

麻烦发贴前先在论坛搜索下。。。
作者: 舒待子    时间: 2011-4-19 12:47

麻烦发贴前先在论坛搜索下。。。
batman 发表于 2011-4-19 12:32


你觉得我没搜索吗?
作者: CrLf    时间: 2011-4-19 12:47

for嵌套...
作者: 舒待子    时间: 2011-4-19 12:49

for嵌套...
zm900612 发表于 2011-4-19 12:47


我看了那些代码,我的帖子就是要突出“最”字,要不怎么叫“挑战”呢?
作者: batman    时间: 2011-4-19 12:55

6# 舒待子
楼主认为这个贴子和你的有什么实质性的区别?标题不同?
http://www.bathome.net/thread-1701-1-4.html
作者: batman    时间: 2011-4-19 13:10

3楼穷举法,8楼递归法:
http://www.bathome.net/viewthrea ... hlight=%C5%C5%C1%D0
作者: asnahu    时间: 2011-4-19 13:28

4# 舒待子


斑竹让你搜索是对的,论坛早就有相关的帖子,浮躁是学不了东西的。
作者: 舒待子    时间: 2011-4-19 13:39

3楼穷举法,8楼递归法:
http://www.bathome.net/viewthrea ... hlight=%C5%C5%C1%D0
batman 发表于 2011-4-19 13:10


看了两个都是你的代码,一个要生产临时文件,另一个还好,
=======================
题外话,我觉得版主有些“倚老卖老”

你以前讨论过就不许别人再发帖讨论了吗? 排列组合算法五花八门,我发帖为大家提供再交流平台,怎么就浮躁了

尽管我是用马甲帖,也是看这帖太冷清了。
作者: 舒待子    时间: 2011-4-19 13:42

这是我最后一贴,此号作废,论坛官僚味十足。
作者: caruko    时间: 2011-4-19 14:07

=.=
发表对别人的看法的同时,也看看自己。
你可以坚持自己的想法,但不能强迫别人也有兴趣。
不依自己的想法就是"XX主义"?
作者: Hello123World    时间: 2011-4-19 15:21

不依自己的想法就是"XX主义"!
作者: wc726842270    时间: 2011-4-19 15:24

早上就看见这个贴子了,还真没想到跟贴的会这么多。上火
作者: plp626    时间: 2011-4-21 13:48

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

这个很短小。
  1. @echo off
  2. call:perm "a b c xy z"
  3. pause
  4. :perm <"c1 c2 ..."> // code by plp
  5. setlocal enabledelayedexpansion&set "s=%~1 "
  6. if "!s: =!" == ""  (echo %~2)else for %%b in (%~1)do call:perm "!s:%%b =!" "%~2 %%b"
  7. endlocal&goto:eof
复制代码
这个代码可精简为:
  1. @echo off&setlocal enabledelayedexpansion
  2. call:perm "a b c xy z"
  3. pause
  4. :perm <"c1 c2 ..."> // code by plp
  5. setlocal&set "s=%~1 "&if "!s: =!" == ""  (echo %~2)else for %%b in (%~1)do call:perm "!s:%%b =!" "%~2 %%b"
复制代码
依据:
setlocal enabledelayedexpansion后,子过程会自动继承变量延迟开启,
call一个子过程,若setlcoal后,在结束该子过程时默认endlocal。。。
作者: plp626    时间: 2011-4-21 14:08

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

这个兼容特殊字符
  1. @echo off
  2. call:perm "< & > plp |"
  3. pause
  4. :perm <"s1 s2 ...">
  5. setlocal enabledelayedexpansion&set "s= %~1"&for /f "tokens=*" %%a in ("%~1")do Set "ss=%%a"
  6. if "!s: =!" == ""  (echo "%~2 ") else for %%b in ("!ss: =" "!")do call:perm "!s: %%~b=!" "%~2 %%~b"
  7. endlocal&goto:eof
复制代码
这个可精简为:
  1. @echo off&setlocal enabledelayedexpansion
  2. call:perm "< & > plp |"
  3. pause
  4. :perm <"s1 s2 ...">
  5. setlocal&set "s= %~1"&for /f "tokens=*" %%a in ("%~1")do Set "ss=%%a"
  6. if "!s: =!" == ""  (echo "%~2 ") else for %%b in ("!ss: =" "!")do call:perm "!s: %%~b=!" "%~2 %%~b"
复制代码
依据:
setlocal enabledelayedexpansion后,子过程会自动继承变量延迟开启,
call一个子过程,若setlcoal后,在结束该子过程时默认endlocal。。。
作者: CrLf    时间: 2011-5-21 11:51

这个很短小。@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

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

在cn-dos做过
arrangement
  1. @echo off
  2. setlocal enabledelayedexpansion
  3. set /p inp="仅支持排列几个普通字符,不要乱输哦:"
  4. call :func "%inp%" ""
  5. pause
  6. exit
  7. :func
  8. if "%~1"=="" (echo _%~2 &goto :eof)
  9. setlocal
  10. set strnow=%~1
  11. set /a lp=0,lpb=lp+1
  12. :lp
  13.   call :func "!strnow:~0,%lp%!!strnow:~%lpb%!" "%~2!strnow:~%lp%,1!"
  14.   if not "!strnow:~%lpb%!"=="" (
  15.    set /a lp+=1,lpb=lp+1
  16.    goto :lp
  17.   )
  18. endlocal
复制代码
combination
  1. @echo off
  2. call :func "abcd" ""
  3. pause &exit
  4. :func
  5. setlocal
  6. if %1=="" (
  7.     if not %2=="" (echo %2)
  8.     goto :eof
  9. )
  10. set strnow=%~1
  11.    call :func "%strnow:~1%" "%~2%strnow:~0,1%"
  12.    call :func "%strnow:~1%" "%~2"
  13. endlocal
复制代码
本来利用批处理可以用变量作为语句执行的特点可以用变量构造多层for ,这样速度很快。
但是排列方面整起来不容易,组合的话倒可以:
  1. @echo off &setlocal enabledelayedexpansion
  2. set element=a b c
  3. :gettitle
  4. for %%x in (%element%) do (
  5.   set "fo=for %%%%x in ("%%x" "") do (!fo!"
  6.   set end="!end!)"
  7.   set result=!result!%%~%%x
  8. )
  9. %fo%
  10.   echo "%result%"
  11. %end:"=%
  12. pause
复制代码

作者: caruko    时间: 2011-5-21 14:54

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

不用CALL的办法,但目前不支持重复字符,因为用到字符替换,数字比如“2 12” “a  ab  bf”就会出错。
去重复也可以,但是需要增加一些代码,把字符改成"_2_  _12_",效率有降低。
纯数字的话,稍改一下效率更快。
  1. @echo off
  2. SETLOCAL ENABLEDELAYEDEXPANSION
  3. set "str=a b c d e f"
  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个排列.
  53. pause>nul&exit
复制代码

作者: plp626    时间: 2011-5-21 15:00

16# zm900612

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

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

怎么写完一个递归函数,你又怎么知道自己写的函数是正确的呢?
我引用宋劲彬的一段话:
如果你相信你正在写的递归函数是正确的,并调用它,然后在此基础上写完这个递归函数,那么它就会是正确的,从而值得你相信它正确。



看你说的那个整数划归问题,我还真不好找处一个递归关系。。。
作者: caruko    时间: 2011-5-21 15:23

不用递归的算法,对字符位置敏感,去重复有点麻烦。
作者: CrLf    时间: 2011-5-21 15:30

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

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

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

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

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

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

作者: 523066680    时间: 2011-5-21 17:12

哪位能把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

23# 523066680
  1. @echo off
  2. set a=%%a&set b=%%b&set c=%%c
  3. 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%"
  4. %fo%
复制代码

作者: plp626    时间: 2011-5-21 17:44

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

批处理的makefunction 特性:(利用netben版主首创的内敛函数技巧)
  1. @echo off&setlocal EnableDelayedExpansion
  2. call:makefun _perm "a b c d xy"
  3. %_perm%
  4. pause&exit
  5. :makefun <funname> <"charlist">
  6. Set n=-1&Set s0=%~2&Set p=&set f=&for %%a in (%~2)do Set/a n+=1
  7. for /l %%a in (0 1 %n%)do (Set/a m=%%a+1
  8. Set "f=!f!&for %%%%a in (^!s%%a^!)do Set s!m!=^!s%%a:%%%%a=^!"
  9. Set p=!p! %%%%a)
  10. set %1=!f:~1,-15!ECHO !p!&goto:eof
复制代码

作者: caruko    时间: 2011-5-21 18:09

=.=
好高明的算法,看了半天还没弄明白
作者: CrLf    时间: 2011-5-21 23:37     标题: null

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

呵呵,思路撞车很正常,楼上不必在意!
plp的代码确实是不一般的精致啊,PF!!
作者: plp626    时间: 2011-5-22 09:32

27# zm900612


注意看17楼第三个代码,我的和他的思路基本一致。。。
作者: powerbat    时间: 2011-5-22 11:04

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

29# plp626


嗯,本质上确实是一样的...原先没注意看52兄的第三个代码,但是大概扫了一眼留下印象了吧,后来自己的思路也是这个路线的,汗
作者: CrLf    时间: 2011-5-22 12:39

30# powerbat


我不知道有没理解对,老兄似乎是说全部列举出来再排除重复,但是这样效率太低了,假设有7个项,每个项都能多次使用而且不排除重复的所有排列=7的7次方=823543,但是题目所要求的真正的组合=!7=5040,也就是说,后者比前者少计算了八十多万次,这是不可忍受的。
所以粗看了下大家的代码,大部分是用批处理实现!7的计算方式,以节省用时
作者: powerbat    时间: 2011-5-22 12:58

列举出来的组合数完全没重复。
排除一部分组合只是为了满足那个题目的要求
作者: CrLf    时间: 2011-5-22 13:14

33# powerbat


噢,那是我理解问题了呵呵
作者: ahighhand    时间: 2019-3-17 10:04

各位老师的代码都好牛!但26个字母里选3个不重复排列怎么整呢,修改哪个都没成功
作者: 523066680    时间: 2019-3-17 12:47

本帖最后由 523066680 于 2019-3-17 12:58 编辑

回复 35# ahighhand

26选3
组合
  1. @echo off
  2. call :func "abcdefghijklmnopqrstuvwxyz" "" 0
  3. pause &exit
  4. :func
  5.     setlocal
  6.     set /a v=%3
  7.     if %v% equ 3 (echo %~2 &goto :eof)
  8.     if %1  == "" (goto :eof)
  9.     set strnow=%~1
  10.     call :func "%strnow:~1%" "%~2%strnow:~0,1%" %v%+1
  11.     call :func "%strnow:~1%" "%~2" %v%
  12.     endlocal
复制代码
排列
  1. @echo off &setlocal enabledelayedexpansion
  2. set alphabet=abcdefghijklmnopqrstuvwxyz
  3. for /l %%a in (0,1,25) do set eles=!eles! !alphabet:~%%a,1!
  4. call :func "%eles%" "" 0
  5. pause &exit
  6. :func
  7.     setlocal
  8.     set /a v=%3
  9.     if %v% equ 3 ( echo %~2 &goto :eof)
  10.     set eles=%~1
  11.     for %%a in ( %eles% ) do call :func "!eles:%%a=!" "%~2%%a" %v%+1
  12.     endlocal
复制代码

作者: 老刘1号    时间: 2019-3-17 22:20

回复 36# 523066680


    似曾相识的感觉,happy好像也出过这个题,当时的我(菜鸡)还解不出来
作者: 523066680    时间: 2019-3-17 23:12

本帖最后由 523066680 于 2019-3-17 23:26 编辑

回复 37# 老刘1号

    那个帖子,我转发了一段迭代解法(摘自《高阶Perl》),若想要第N个结果、或者想要从第N个排列开始排,可以直接算,而不需要从头开始。
不过没什么人留意
http://www.bathome.net/redirect. ... 3749&pid=198745
http://www.code-by.org/viewtopic.php?p=814#p814

如果做多线程并行,这种迭代法就很好用,8核的CPU,8线程分别从不同的起点开始迭代。
如果是跑GPU,并发量就更大了,若是简单的加密应该可以利用这种方法,大量并发加速碰撞。
作者: ahighhand    时间: 2019-3-18 23:59

回复  ahighhand

26选3
组合排列
523066680 发表于 2019-3-17 12:47


谢谢版主!如果想直接输出到list.txt怎么修改更好些?
作者: Batcher    时间: 2019-3-19 09:16

回复 39# ahighhand


call :func "abcdefghijklmnopqrstuvwxyz" "" 0 > list.txt
试试这样可以吗




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