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

[其他] [讨论]批处理-元素排列与组合应用

在有些问题解决的时候可能需要用到排列或组合的,
应用到它的题目有见到,就是不知道排列与组合有没有独立出过题?

先描述描述,了解或者更了解的话 可以补充,或者跳过:
  1. 排列举例,现在有abc 三个字符,3位排列的结果是:
  2. abc
  3. acb
  4. bac
  5. bca
  6. cab
  7. cba
  8. 排列的个数为 3*2*1=6 个  这个式子我是这么理解的:
  9. 第一位可选3个字符,现有三个开头,
  10. 第二位可选剩下的2个字符,3分别*2=6
  11. 第三位可以剩下1个字符选,所以共有6*1=6个结果。
  12. 从逐位选择字符的思路来做,我选择了递归调用。上次也看过别人说插入法做的,当时没理解代码。
  13. 应用举例: 比如你给定一个带有 减 或者 除的运算式子(除或者减,数字调换一下结果就不同的嘛),
  14.                 以及给定参与运算的那些数,
  15.                 可以用排列找出运算结果为N时,数字的排列方式。  比如算24点,就可以用到。
  16.                 (不过我见过最简洁的算24点是直接递归深入运算,当时理解了很久,其实也是隐含了排列的。
  17.    想批处理算24点的话,必须模拟一下分数,因为计算中可能一些分数被取整,结果就不精确。
  18.    事实上原分数乘某数=24)
  19.   密码: 如果知道密码个数和密码元素范围,个数不多的话,可以排列元素并尝试攻破密码
  20. (但现在都限制错误输入次数了呢)
复制代码
  1. 组合举例:
  2. 给定一个数组{1,2,3,4},列出所有子组合(包括{1,2,3,4},元素调换并不能算另一个组合,如:{2,1,3,4} ):
  3. 1
  4. 1 2
  5. 1 2 3
  6. 1 2 3 4
  7. 1 2 4
  8. 1 3
  9. 1 3 4
  10. 1 4
  11. 2
  12. 2 3
  13. 2 3 4
  14. 2 4
  15. 3
  16. 3 4
  17. 4
  18. n个数的组合的个数应该=(2的n次方)-1  
  19. 在高中必修中对该个数的解释有两种, 为了方便我说运算比较直接的那种(上面那个2^n-1的):
  20. 四个数供选择,也就存在4个位{【1】,【2】,【3】,【4】}
  21. 而组合本身的性质就是: 列出各位的数在或者不在时造成的各种不同子组合,
  22. 就像概率计算,
  23. 第一位有两种情况,2
  24. 在第一位固定的情况下,第二位有两种情况,前2位就有2*2种情况,
  25. 依次类推,共4位,得到 2的4次方,而全部位为空的时候,没有组合,排除它,-1。
  26. (就是讲给没了解到的人的,这个概率计算类似: 给N个位,用0或者1表示,算出能产生多少个不同的数字,
  27. 人家000...也算进了,想像一下就挺直观的~)
  28. 应用举例: 可以用来找出  一组数字中,"和" 或者 "积" 为指定结果的那些组合
  29. 比如:1至9中, 和为15 的组合有
  30. 1+2+3+4+5
  31. 1+2+3+9
  32. 1+2+4+8
  33. 1+2+5+7
  34. 1+3+4+7
  35. 1+3+5+6
  36. 1+5+9
  37. 1+6+8
  38. 2+3+4+6
  39. 2+4+9
  40. 2+5+8
  41. 2+6+7
  42. 3+4+8
  43. 3+5+7
  44. 4+5+6
  45. 6+9
  46. 7+8
复制代码
哈上面不知道算不算交代清楚了,话说网上资料更全,
希望上面没有误导人的地方,如果有,还请知情人士及时告知。

题目是:
1. 排列"abcde" 这5个字符(排满5位)。
2. 找出{1,2,3,4,5,6,7,8} 中,和为30的那些数。

2月24日早上,考虑到指定个数的话,该题目可以用for- n 层  来解决,而我本意
是希望未接触递归的人可以初步用递归解题,以此了解一种解题技能。
当然对于未知元素个数时的排列组合,欢迎各种解法~  
现题目升级一下
  1.    
  2. 1-2. 排列用户输入的字符(9个以内不重复)
  3. 2-2. 对用户输入的n个不同的数字进行组合,找出其中和为30的数字。没有则提示未找到结果。
  4. 为了方便处理,用户输入字符的格式由程序决定。
复制代码
已经很熟悉的话,难度可以增加的( 做有好东东的人要分享下哦)~

[ 本帖最后由 523066680 于 2010-3-1 09:06 编辑 ]

回复 13楼 的帖子

1.首先,感谢回帖!
2.我觉得结果不会更好,
    事情的重点在于,各个位的存在与不存在的处理
    而增加了对应个0,仍然要面对各个位的存在与不存在的处理。

   要是10进制和2进制可以很方便的转化,我觉得会好玩一些
你看   三个位的二进制的值的可能结果是:
000      0(这边表示10进制的值)
001      1
010      2
011      3
100      4
101      5
110      6
111      7
1就刚好对应各个位存在与不存在的所有组合方式。
而在10进制这边只要逐一递增就可以了。

[ 本帖最后由 523066680 于 2010-3-2 08:30 编辑 ]

TOP

对于纯数字的组合来说,我的想法是这样的:
随意输入任意不同的数字,用空格隔开,计算他们的个数N,然后设置一个变量等于N个0,每个0之间要有空格,然后依次把这些0换成输入的数值,这样的话对于计算和为X的组合比较方便,输出的时候可以把0去掉(“ 0 ”替换为“ ”)。这样不会误删,但是如果有0的情况那就再考虑
不过我写不出来

TOP

呀哈 有回帖的就有我~
重复发贴了呵,这次说了一下应用,顺便提出递归的。所以排列和组合都拉进来了。
虽然批处理递归不快,但是在算法上递归还是相对好理解的,而且我还举了两个对应的应用不是么
觉得重复就干掉,我无异议。

我还想借此主题深入讨论算24完善版 来着,我见过的批处理各种算24,无理数分数化处理完成后,
也只输出一个结果,原因在于
1、数字在加法或乘法之间排列调换的时候,对程序是不同的,而在观者看来,输出的结果就属于重复了。
2、而相同数字的排列调换,也是计算得一样的结果。
3、额,还没想到……
不想让人看到 重复,干脆只给一个答案……

[ 本帖最后由 523066680 于 2010-3-1 16:51 编辑 ]

TOP

关于排列这个问题,论坛有过专门的贴子的,我想exist不应该没看过下面这个贴子吧:
http://www.bathome.net/viewthrea ... hlight=%D7%E9%BA%CF
***共同提高***

TOP

来组合来了。
写了两个方案的, 都是从计算结果个数的原理 为出发点
一种是从排列的基础上修改
一种是从(2的n次方-1) 的理解上写的递归, 他就是每一层次中占一个位
最终结果就是其中某个位存在或者不存在时造成的各种结果。
  1. @echo off
  2. setlocal enabledelayedexpansion
  3. call :func "abcd" "" 0
  4. pause &exit
  5. :func
  6. if not %2=="" (echo %2)
  7. if %1=="" (goto :eof)
  8. setlocal
  9.   set strnow=%~1
  10.   set /a lp=0,lpb=lp+1
  11.   :lp
  12.     call :func "!strnow:~%lpb%!" "%~2!strnow:~%lp%,1!"
  13.   if not "!strnow:~%lpb%!"=="" (
  14.     set /a lp+=1,lpb=lp+1
  15.     goto :lp
  16.   )
  17. endlocal
复制代码
二:
  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
复制代码


我现在把标题改为讨论好了。

TOP

回复 8楼 的帖子

哈  我琢磨了,你是循环套循环,用批处理自己构造镶嵌语句 的办法。
虽然我想过用这个办法但是对句子中敏感字符的处理一直没突破。
然后是感谢一下回帖^_^

先不讲组合(事实上组合比排列更容易的,重点是要了解组合的形成性质)。
排列这道题,很多人要求输入的信息重复的时候的处理,
大家的处理思路是怎样的? 各位不要吝啬,这样才能找到好的办法哦。
像 abb。 他可以让实际不同情况个数给你多刷一遍……:
abb,abb,bab,bab,abb,abb

当元素在不同排列时的情况用于参与计算(假设计算用的时间会比一般语句执行长的多),
减少计算次数就显得非常重要。但是如果没有高效的办法,那就让它多算一次好了……

[ 本帖最后由 523066680 于 2010-2-27 21:31 编辑 ]

TOP

效率高点不?
想不去CAII的 那样更好
另 变量字符长度有限制  权当交流
  1. @echo off
  2. set /p str=请输入字符:
  3. setlocal enabledelayedexpansion
  4. set /a max=8190,min=0
  5. for /l %%a in (1,1,14) do (
  6.     set /a "n=(max+min)/2"
  7.     for /f "delims=" %%b in ("!n!") do if "!str:~%%b!" equ "" (set /a max=n) else set /a min=n
  8.     )
  9.     set/a "n-=1"
  10. for /l %%i in (0 1 %n%) do (
  11.     if %%i equ 0 endlocal
  12.     set/a n=%%i+1
  13.     call:lp %%i
  14. )
  15. setlocal enabledelayedexpansion
  16.     for /l %%i in (0 1 %n%) do set _%%i=!str:~%%i,1!&set "v0=!v0! %%i"
  17.     %v%for %%%n% in (!v%n%!) do echo;%vr%!_%%%n%!&set/a t+=1
  18.     echo %t%
  19.     pause&exit
  20. :lp
  21. set "v=%v%for %%%1 in (!v%1!) do set v%n%=!v%1:%%%1=!&"
  22.     set "vr=%vr%!_%%%1!"
复制代码

[ 本帖最后由 terse 于 2010-2-27 15:51 编辑 ]
1

评分人数

TOP

时间到,那么我自顾自地写了
一种开启变量域的  输入几个普通字符并排列
  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
复制代码
还有一种是以前学习批处理不够深入,利用参数记录了各层的处理信息,返回的时候利用各层
参数对应的性质,还原变量并继续处理。

这样的代码并不正规,所以没有设置输入,直接示范。
  1. @echo off&setlocal enabledelayedexpansion
  2. call :func "0" "" "abcdef"
  3. pause &exit
  4. :func
  5. set str=%~3
  6. if "%str:~1%"=="" (set /a na=%~1+1
  7.                    echo,%~2%str%
  8.                    goto :eof)
  9. set na=0
  10. :loop
  11. set /a nb=na+1
  12. call :func "%na%" "%~2!str:~%na%,1!" "!str:~0,%na%!!str:~%nb%!"
  13. set str=%~3
  14. if not "!str:~%na%!"=="" goto :loop
  15. set /a na=%~1+1
复制代码
排列的方式中,如果是逐位安排数字,则递归会相对好理解一些。

我的理解和结果个数验证:

比如有3个字符abc 其排列情况就有3*2*1=6个
     这样计算的原因,用tree目录树表示吧:

    1阶  2阶 3阶
├─a
│    ├─b
│    │     └─c
│    └─c
│              └─b
├─b
│    ├─a
│    │     └─c
│    └─c
│             └─a
└─c
         ├─a
         │    └─b
         └─b
                   └─a
----+---+---+------
         3  X  2 X  1  = 6 个结果


[ 本帖最后由 523066680 于 2010-2-25 20:01 编辑 ]

TOP

回复 5楼 的帖子

我原标题是:  排列与组合    ,可能#@¥!%……  所以就被改成了现在的:计算字符串的排列与组合

今天把标题私自修改成 排列与组合的应用,希望标题过关。

[ 本帖最后由 523066680 于 2010-2-25 09:15 编辑 ]

TOP

如果要计算个数的话就是求一个集合的非空子集个数,公式不难

TOP

气氛只能用安静得诡异来形容

先抢发一个不符合题意的,已知元素个数的组合~ :
  1. @echo off
  2. setlocal enabledelayedexpansion
  3. set /a n=6
  4. set /a x1=1,x2=2,x3=3,x4=4,x5=5,x6=6
  5. for /l %%a in (1,1,%n%) do (
  6.   set fo="!fo! for %%%%a in (!x%%a! -) do ("
  7.   set end="!end!)"
  8.   set echo=!echo!%%%%a
  9. )
  10. set /a arrn=0
  11. %fo:"=%
  12.     set list=%%1%%2%%3%%4%%5%%6
  13.     echo _!list:-=!
  14.     set /a arrn+=1
  15. %end:"=%
  16. echo 包括全空情况,有%arrn% 个组合
  17. pause
复制代码

[ 本帖最后由 523066680 于 2010-2-24 21:28 编辑 ]

TOP

回复 2楼 的帖子

非递归的话,应该是掌握某规律后的解法吧。

cn-dos帖 , 当时pusofalse发的 “排列组合”  实际内容是排列。
tid=41243

WANKOILZ
来自 重庆
『第 23 楼』:  

我用“插入法”,发现效率还不错,代码也简短:

    CODE:  [Copy to clipboard]
    @echo off&setlocal enabledelayedexpansion
    set/p chr=请输入要排列的字母,以空格分开:
    for %%i in (%chr%) do set a=%%i
    set - %a%=ok&set chr=!chr:%a%=!
    for %%i in (%chr%) do call ut %%i
    for /f "delims=-= tokens=1" %%i in ('set -') do echo %%i
    pause>nul

    :out
    for /f "delims=-= tokens=1" %%i in ('set -') do (
      set - %1%%i=ok
      for %%j in (%%i) do (
        for %%k in (%%i) do (set str=!str! %%k&if %%j==%%k set str=!str! %1)
        set -!str!=ok&set str=
      )
      set -%%i=
    )



暂时没时间去理解上面的, 纵观pusofalse那个贴,我发现我的题目应该修改一下
指定了题目中数字的个数,做题的话用固定个for就可以解决了……
尤其是组合,  N重for  分别为对应该层数字存在 和不存在的状态 ,N层 重合就是了…… 排除全空状态。

===============================================
如果2天内没有人跟答题帖,那么我就自顾自地写相关的了~。

[ 本帖最后由 523066680 于 2010-2-24 12:59 编辑 ]

TOP

翻了一下当年《算法设计》这门课的作业题,排列组合用两种不同的方法实现,不过都属于递归。
插入法是什么?代码贴出来看看?
我帮忙写的代码不需要付钱。如果一定要给,请在微信群或QQ群发给大家吧。
【微信公众号、微信群、QQ群】http://bbs.bathome.net/thread-3473-1-1.html
【支持批处理之家,加入VIP会员!】http://bbs.bathome.net/thread-67716-1-1.html

TOP

返回列表