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

523066680

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

先描述描述，了解或者更了解的话 可以补充，或者跳过:

排列举例，现在有abc 三个字符，3位排列的结果是：
abc
acb
bac
bca
cab
cba
排列的个数为 3*2*1=6 个  这个式子我是这么理解的:
第一位可选3个字符，现有三个开头，
第二位可选剩下的2个字符，3分别*2=6
第三位可以剩下1个字符选，所以共有6*1=6个结果。
从逐位选择字符的思路来做，我选择了递归调用。上次也看过别人说插入法做的，当时没理解代码。

应用举例: 比如你给定一个带有 减 或者 除的运算式子(除或者减，数字调换一下结果就不同的嘛)，
                以及给定参与运算的那些数，
                可以用排列找出运算结果为N时，数字的排列方式。  比如算24点，就可以用到。
                (不过我见过最简洁的算24点是直接递归深入运算，当时理解了很久，其实也是隐含了排列的。
   想批处理算24点的话，必须模拟一下分数，因为计算中可能一些分数被取整，结果就不精确。
   事实上原分数乘某数=24)

  密码: 如果知道密码个数和密码元素范围，个数不多的话，可以排列元素并尝试攻破密码
(但现在都限制错误输入次数了呢)
复制代码

组合举例:
给定一个数组{1,2,3,4}，列出所有子组合(包括{1,2,3,4}，元素调换并不能算另一个组合，如:{2,1,3,4} ): 
1 
1 2 
1 2 3 
1 2 3 4 
1 2 4 
1 3 
1 3 4 
1 4 
2 
2 3 
2 3 4 
2 4 
3 
3 4 
4 
n个数的组合的个数应该=（2的n次方）-1  
在高中必修中对该个数的解释有两种, 为了方便我说运算比较直接的那种(上面那个2^n-1的):
四个数供选择，也就存在4个位{【1】,【2】,【3】,【4】}
而组合本身的性质就是: 列出各位的数在或者不在时造成的各种不同子组合，
就像概率计算，
第一位有两种情况，2
在第一位固定的情况下，第二位有两种情况，前2位就有2*2种情况，
依次类推，共4位，得到 2的4次方，而全部位为空的时候，没有组合，排除它，-1。
(就是讲给没了解到的人的，这个概率计算类似: 给N个位,用0或者1表示，算出能产生多少个不同的数字，
 人家000...也算进了，想像一下就挺直观的~)

应用举例: 可以用来找出  一组数字中，"和" 或者 "积" 为指定结果的那些组合
比如:1至9中， 和为15 的组合有
1+2+3+4+5
1+2+3+9
1+2+4+8
1+2+5+7
1+3+4+7
1+3+5+6
1+5+9
1+6+8
2+3+4+6
2+4+9
2+5+8
2+6+7
3+4+8
3+5+7
4+5+6
6+9
7+8
复制代码

哈上面不知道算不算交代清楚了，话说网上资料更全，
希望上面没有误导人的地方，如果有，还请知情人士及时告知。

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

2月24日早上，考虑到指定个数的话，该题目可以用for- n 层  来解决，而我本意
是希望未接触递归的人可以初步用递归解题，以此了解一种解题技能。
当然对于未知元素个数时的排列组合，欢迎各种解法~  
现题目升级一下

    
1-2. 排列用户输入的字符(9个以内不重复)
2-2. 对用户输入的n个不同的数字进行组合，找出其中和为30的数字。没有则提示未找到结果。
为了方便处理，用户输入字符的格式由程序决定。
 
复制代码

已经很熟悉的话，难度可以增加的( 做有好东东的人要分享下哦)~

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

523066680

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 编辑 ]

sgaizxt001

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

523066680

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

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

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

batman

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

523066680

来组合来了。
写了两个方案的， 都是从计算结果个数的原理 为出发点
一种是从排列的基础上修改
一种是从(2的n次方-1) 的理解上写的递归， 他就是每一层次中占一个位
最终结果就是其中某个位存在或者不存在时造成的各种结果。

@echo off
setlocal enabledelayedexpansion

call :func "abcd" "" 0
pause &exit


:func
if not %2=="" (echo %2)
if %1=="" (goto :eof)
setlocal
  set strnow=%~1
  set /a lp=0,lpb=lp+1
  :lp
    call :func "!strnow:~%lpb%!" "%~2!strnow:~%lp%,1!"
  if not "!strnow:~%lpb%!"=="" (
    set /a lp+=1,lpb=lp+1
    goto :lp
  )
endlocal
复制代码

二:

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

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

523066680

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

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

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

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

terse

效率高点不？
想不去CAII的 那样更好
另 变量字符长度有限制  权当交流

@echo off
set /p str=请输入字符:
setlocal enabledelayedexpansion
set /a max=8190,min=0
for /l %%a in (1,1,14) do (
    set /a "n=(max+min)/2"
    for /f "delims=" %%b in ("!n!") do if "!str:~%%b!" equ "" (set /a max=n) else set /a min=n
    )
    set/a "n-=1"
for /l %%i in (0 1 %n%) do (
    if %%i equ 0 endlocal
    set/a n=%%i+1
    call:lp %%i
)
setlocal enabledelayedexpansion
    for /l %%i in (0 1 %n%) do set _%%i=!str:~%%i,1!&set "v0=!v0! %%i"
    %v%for %%%n% in (!v%n%!) do echo;%vr%!_%%%n%!&set/a t+=1
    echo %t%
    pause&exit
:lp
set "v=%v%for %%%1 in (!v%1!) do set v%n%=!v%1:%%%1=!&"
    set "vr=%vr%!_%%%1!"
复制代码

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

523066680

时间到，那么我自顾自地写了
一种开启变量域的  输入几个普通字符并排列

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

还有一种是以前学习批处理不够深入，利用参数记录了各层的处理信息，返回的时候利用各层
参数对应的性质，还原变量并继续处理。

这样的代码并不正规，所以没有设置输入，直接示范。

@echo off&setlocal enabledelayedexpansion
call :func "0" "" "abcdef"
pause &exit


:func
set str=%~3
if "%str:~1%"=="" (set /a na=%~1+1
                   echo,%~2%str%
                   goto :eof)
set na=0
:loop
 set /a nb=na+1
 call :func "%na%" "%~2!str:~%na%,1!" "!str:~0,%na%!!str:~%nb%!"
 set str=%~3
 if not "!str:~%na%!"=="" goto :loop
 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 编辑 ]

523066680

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

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

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

sgaizxt001

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

523066680

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

先抢发一个不符合题意的，已知元素个数的组合~ :

@echo off
setlocal enabledelayedexpansion

set /a n=6
set /a x1=1,x2=2,x3=3,x4=4,x5=5,x6=6

for /l %%a in (1,1,%n%) do (
  set fo="!fo! for %%%%a in (!x%%a! -) do ("
  set end="!end!)"
  set echo=!echo!%%%%a
)

set /a arrn=0
%fo:"=%
    set list=%%1%%2%%3%%4%%5%%6
    echo _!list:-=!
    set /a arrn+=1
%end:"=%
echo 包括全空情况，有%arrn% 个组合
pause
复制代码

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

523066680

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

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 编辑 ]

Batcher

翻了一下当年《算法设计》这门课的作业题，排列组合用两种不同的方法实现，不过都属于递归。
插入法是什么？代码贴出来看看？