[挑战]批处理求集合的交集与并集

zhouyongjun

如题
集合A、B为有限集，即A、B中元素为有限个数，且为正整数、最大值不超过100000。
A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}
B={2,5,31,[300,500],[8000,9000],9500}
求A∪B、A交非B 的集合。
A∪B={[1,6],10,[20,60],[200,3000],5000,[6000,9000],9500}
A交非B={1,[3,4],6,10,[20,30],[32,60],[200,299],[501,3000],5000,[6000,7999]}

要求：
1.结果如上例所示，连续元素必须采用闭区间（“[]”）表示；
2.同一集合中，各元素不能重复，例如不能{[2,3],[3,4]}，应为{[2,4]}；
3.上面集合所包含元素单纯为举例，不能就题解题；
4.方法不限，效率第一。

PS:闭区间即为包括边界；题中交代集合元素为正整数，所以(20,30)表示为[21,29],不考虑开区间
交集（∩）：以属于A且属于B的元素为元素的集合称为A与B的交（集），记作A∩B（或B∩A），读作“A交B”（或“B交A”），即A∩B={x|x∈A,且x∈B}
并集（∪）：以属于A或属于B的元素为元素的集合称为A与B的并（集），记作A∪B（或B∪A），读作“A并B”（或“B并A”），即A∪B={x|x∈A,或x∈B}
非B：为B的补集即1-100000中除开B以外的元素。

现把集合元素上限改为100000以降低难度；若不考虑上限也能解出，可忽略上限。

[ 本帖最后由 zhouyongjun 于 2010-4-14 20:16 编辑 ]

namejm

　　十多年没碰这些集合符号了，都有点忘记了这些符号的含义，楼主最好能在顶楼说一下各种符号的具体含义，比如我对 [20,30] 和 [20-30] 之间的差别都不甚了解。
　　另，这些集合中是否可能存在 (20,30) 这种不包含边界数值的情形？请一并明示。

zhouyongjun

[20-30]是我书写错误，现已改正

namejm

　　尝试着用纯批处理写了段代码。

　　思路：
　　1、把每个集合展开，列举集合中的每一个数，分别放入临时文件A.txt和B.txt，并求出每一集合中的最大数值max_A和max_B；
　　2、求合集时：
　　　　① 先把展开的数据放入同一临时文件tmpAB.txt，以tmpAB.txt中每行数据为变量名的一部分，对变量 num_%%i 赋值，从而得到变量名合集；
　　　　② 求出max_A和max_B中的最大值max，然后，检测从1到max的变量 num_%%i 是否已被赋值，把已经赋值过的数字输出到临时文件tmpAB↑.txt，从而得到升序排列的A和B的交集数据文本；
　　　　③ 读取tmpAB↑.txt中的数据，按照格式输出A和B的和集表达式；
　　3、求A交非B的交集时：
　　　　① 读取B.txt，对每一行数据赋值，赋值方法同第2点第②小点，然后，从1到max_B列举数值，把那些没有赋值过的数据输出到临时文件 —B.txt ；
　　　　② 用 findstr /beg:—B.txt A.txt 得到按照升序排列的A交非B的数据文本 tmpA—B↑.txt
　　　　③ 按照格式输出交集表达式

　　使用限制：
　　1、应为使用了 set /a 操作，可处理的数值范围为 1～2^32-1；
　　2、因为通过判断变量是否被赋值来排序，而系统有变量名个数的限制，从而导致实际能检测到的数值范围进一步缩小，具体范围尚未测试出来。

　　代码：

@echo off
set A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}
set B={2,5,31,[300,500],[8000,9000],9500}
md tmp 2>nul
pushd tmp 2>nul||exit
setlocal enabledelayedexpansion

echo %time%
call :expand_num A %A:~1,-1%
call :expand_num B %B:~1,-1%

set /p=A∪B={<nul
call :A∪B A B

:—B
:: 生成非B集合数据文本
for /f "delims==" %%i in ('set num_ 2^>nul') do set %%i=
for /f %%i in (B.txt) do set num_%%i=0
(for /l %%i in (1,1,%max_B%) do (
    if not defined num_%%i echo %%i
))>—B.txt
findstr /beg:—B.txt A.txt>tmpA—B↑.txt

set /p=A交非B={<nul
call :format_str A —B
popd
pause
exit

:A∪B
:: 合并两文本，对每个数值赋值，然后从1开始检测哪些数值已经被赋值，由小到大写入临时文件
copy %1.txt+%2.txt tmp%1%2.txt>nul
if %max_A% gtr %max_B% (
    set max=%max_A%
) else set max=%max_B%
for /f "delims==" %%i in ('set num_ 2^>nul') do set %%i=
for /f %%i in (tmp%1%2.txt) do set num_%%i=0
(for /l %%i in (1,1,%max%) do (
    if defined num_%%i echo %%i
))>tmp%1%2↑.txt

:format_str
:: 检测相邻两行数值的差值是否为1，若为1，则是连续数；若不为1，则数值不连续
set /p num=<tmp%1%2↑.txt
set begin=
for /f %%i in (tmp%1%2↑.txt) do (
    if %%i neq !num! (
        set /a diff=%%i-!num!
        call :judge_range %%i !num! !diff!
    )
    set num=%%i
)
if defined begin (
    set /p=[!begin!,%num%]}<nul
) else set /p=%num%}<nul
echo,&echo %time%
goto :eof

:expand_num
:: 把字符串格式化，然后按顺序展开
set begin=&set end=
(for /f "tokens=1*" %%i in ("%*") do (
    for %%x in (%%j) do (
        set str=%%x
        if "!str:~0,1!"=="[" (
            set num_begin=!str:~1!&set begin=yes
        )
        if "!str:~-1!"=="]" (
            set num_end=!str:~0,-1!&set end=yes
        )
        if not defined begin echo %%x
        if defined end (
            for /l %%y in (!num_begin!,1,!num_end!) do echo %%y
            set begin=&set end=
        )
        set max_%1=%%x
    )
))>%1.txt
goto :eof

:judge_range
:: 判断数值范围的临界值，根据临界值输出格式化字符串
if %3 equ 1 (
    if not defined begin set begin=%2
) else (
    if defined begin (
        set /p=[!begin!,%2],<nul
        set begin=
    ) else (
        set /p=%2,<nul
    )
)
goto :eof
复制代码

　　由于有大量的 set /a 操作，速度比较慢，当数据量增大时尤其明显，暂时只把功能完成，尚未优化。

523066680

我看到题目我畏惧了，看到寂寞大师出马了，我佩服了！
(关于寂寞二字属个人言论，并非真正本名，切勿模仿 )

[ 本帖最后由 523066680 于 2010-4-14 22:00 编辑 ]

neorobin

看到题目我起劲了, 回一个楼主, 关于 "非B", 对集合是补运算吧, 而 "非" 是逻辑运算

neorobin

提到了 "列举集合中的每一个数", 这样是不能高效的, 建议思路是, 将每个集合当成若干个子集来处理, 每个子集都有一个下限和一个上限, 求运算时, 依序对两个操作数 集合 的两个子集 的 4 个上下限进行比较, 依据运算生成结果 集合 的子集的上下限, 直到结果集合的全部子集上下限都生成, 最后再来一个 "相邻" 子集合并, 即 如 [3,19] 和 [20, 37] 就合并成 [3,37], 当然这个合并不是必要的, 其中子集处理中, 即使是一个 单独的数, 也可以看成一个集合, 如 1 看成 [1,1], 这样就去除了单独数的特殊性.

zhouyongjun

我也采用过这个办法，跟你的思路完全一样，以数组的形式用set排序，后面判断时感觉很复杂，只能求出部分情况。
这个问题我是从工作中延伸出来的，最初我便是采用定义变量法，思路和jm的略同但不采用临时文件，区间大时效率甚低，想了很久没好办法，特发出来大家讨论一下。

netbenton

有点难搞，只做了个并集的，效率不错，不知道是否通用，还待测试~~~

@echo off&setlocal enabledelayedexpansion
set A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8000],9000,9500}
set B={2,5,31,[300,500],[8000,9000],9500}


::拆分A 和 B的数据集
set/a n=0,m=0

set Av=!a:[=]!
set Av=!Av:]="!

for %%a in (%Av:~1,-1%) do (
	set a!n!=%%~a
	set/a n+=1
)

set Bv=!B:[=]!
set Bv=!Bv:]="!


for %%a in (%Bv:~1,-1%) do (
	set B!m!=%%~a
	set/a m+=1
)


::设置上限
set /a A!n!=2000000000
set /a B!m!=2000000000


::根据a和b总项数来确定循环次，根据并集规则，进行判断重组
set/a mn=m+n,n=0,m=0
for /l %%a in (0,1,!mn!) do (
	for /f "tokens=1,2" %%m in ("!m! !n!") do (
		for /f "delims=," %%x in ("!A%%n!") do (
		for /f "delims=," %%o in ("!B%%m!") do (

		if %%x gtr %%o (set var=!B%%m!&set cur=m) else (set var=!A%%n!&set cur=n)

		for /f "tokens=1,2 delims=," %%1 in ("!var!,!var!") do (
			if !next! lss %%1 (
				if !fa! equ !end! (set aUb=!aUb!,!fa!) else (set aUb=!aUb!,[!fa!,!end!])
				set fa=%%1
			)

			set ben=%%1
			if !end! lss %%2 set end=%%2
		)))

		set /a !cur!=!cur!+1,next=end+1
	)
)
echo;并集计算：
echo;AUB={!aUb:~2!}

pause
复制代码

batman

我也跟一个并集的，自我感觉效率还可以：

@echo off&setlocal enabledelayedexpansion
set "num=1 3-6 10 20-30 32-60 200-3000 5000 6000-8000 9000 9500 2 5 31 300-500 8000-9000 9500"
for %%a in (%num%) do (
    for /f "tokens=1,2 delims=-" %%b in ("%%a") do (
        if "%%c" equ "" (
           if not defined _%%b set "_%%b=a"
           ) else (
           for /l %%d in (%%b,1,%%c) do if not defined _%%d set "_%%d=a"
        )
    )
)
for /l %%a in (1,1,10000) do (
    if defined _%%a (
       set "str=%%a"&set /a strs=str+1
       if not defined _!strs! (
          if not defined flag (
             set "nums=!nums!%%a,"
             ) else (
             set "nums=!nums!%%a],"&set "flag="
          )
          ) else (
          if not defined flag set "nums=!nums![%%a,"&set "flag=a"
       )
    )
)
echo A和B的并集：{!nums:~,-1!}&pause>nul 
复制代码

[ 本帖最后由 batman 于 2010-4-15 09:55 编辑 ]

netbenton

交集处理，在并集处理的模版改为交集的处理而已，没有多少变化。

@echo off&setlocal enabledelayedexpansion
set A={1,[3,6],10,[20,30],[32,60],[200,3000],5000,[6000,8002],9000,9500}
set B={2,5,31,[45,49],55,[300,500],[8000,9000],9500}
::为了处理更多的情况，在楼主的例子上加了一些数据


::拆分A 和 B的数据集
set/a n=0,m=0

set Av=!a:[=]!
set Av=!Av:]="!

for %%a in (%Av:~1,-1%) do (
	set a!n!=%%~a
	set/a n+=1
)

set Bv=!B:[=]!
set Bv=!Bv:]="!


for %%a in (%Bv:~1,-1%) do (
	set B!m!=%%~a
	set/a m+=1
)


::设置上限
set /a A!n!=2000000000
set /a B!m!=2000000000


::根据a和b总项数来确定循环次，根据交集规则，进行判断重组
set/a mn=m+n,n=0,m=0
for /l %%a in (0,1,!mn!) do (
	for /f "tokens=1,2" %%m in ("!m! !n!") do (
		for /f "delims=," %%x in ("!A%%n!") do (
		for /f "delims=," %%o in ("!B%%m!") do (

		if %%x gtr %%o (set var=!B%%m!&set cur=m) else (set var=!A%%n!&set cur=n)

		for /f "tokens=1,2 delims=," %%1 in ("!var!,!var!") do (
			if !end! geq %%1 (
				if !end! geq %%2 (
					if %%1 equ %%2 (set aNb=!aNb!,%%1) else (set aNb=!aNb!,[%%1,%%2])
				) else (
					if %%1 equ !end! (set aNb=!aNb!,%%1) else (set aNb=!aNb!,[%%1,!end!])
				)
			)
			if !end! lss %%2 set ben=%%1&set end=%%2

		)))

		set /a !cur!=!cur!+1
	)
)

echo;交集计算:
echo;aNb={!aNb:~1!}

pause
复制代码

zhouyongjun

这两天学习gawk，尝试用gawk来处理一下，虽然是枚举速度还是比纯P的枚举快很多。
其实工作中我的上限不会超过10000，用gawk还是很快的。枚举还有个好处就是代码很健壮，比如不用考虑原集合里元素的顺序，同一集合出现重复元素的错误也可以避免。

@echo off
::下面代码只包括核心部分，其他处理已被忽略

::先把A、B转换成如下形式
set A=1-1,3-6,10-10,20-30,32-60,200-3000,5000-5000,6000-8000,9000-9000,9500-9500
set B=2-2,5-5,31-31,300-500,8000-9000,9500-9500
::求A交非B
echo %A%,交非,%B%|gawk "BEGIN{FS=\"-\";RS=\",\";ORS=\",\"}{{if($0==\"交非\"){m=1}}{if(m!=1){for(i=$1;i<=$2;i++)a[i]=i}}{if(m==1){for(i=$1;i<=$2;i++)delete a[i]}}}END{x=asort(a,z);for(j=1;j<=x;j++){if(z[j-1]!=z[j]-1||j==1){print \"[\"z[j]}if(z[j+1]!=z[j]+1)print z[j]\"]\"}}"
echo;
::求A∪B
echo %A%,%B%|gawk "BEGIN{FS=\"-\";RS=\",\";ORS=\",\"}{{for(i=$1;i<=$2;i++)a[i]=i}}END{x=asort(a,z);for(j=1;j<=x;j++){if(z[j-1]!=z[j]-1||j==1){print \"[\"z[j]}if(z[j+1]!=z[j]+1)print z[j]\"]\"}}"
echo;
::获取结果后去掉末尾的逗号，把用区间形式的独数重新表示
pause
复制代码

batman

新方法：
　　先将A、B集合中的数字进行排序，结果中也包括了子集合符号，其中集合开始用＊－表示，集合结束用－＊表示，然后再进行判断，效率自是提高了很多：

@echo off&setlocal enabledelayedexpansion
set "a=1 3-6 10 20-30 32-60 200-3000 5000 6000-8000 9000 9500 2 5 31 300-500 8000-9000 9500"
for %%a in (%a:-= %) do (
    set /a n+=1
    for %%b in (%a:-= %) do if %%a geq %%b set /a _%%a+=1
　　set ".!_%%a!=%%a"
)
for /l %%a in (1,1,%n%) do set "num=!num! !.%%a!"
for %%a in (%a%) do (
    for /f "tokens=1,2 delims=-" %%b in ("%%a") do (
        if "%%c" neq "" (
           set "#%%b=%%b-"&set "#%%c=-%%c"
           ) else (
           set "#%%b=%%b"
        )
    )
)
set /p=排序后为：<nul&set /a n=0,m=1
for %%a in (%num%) do set /p=!#%%a! <nul&set /a n+=1&set "$!n!=!#%%a!"
for %%a in (%num%) do (
    set "str=!#%%a!"&set /a m+=1,strs=!str:-=!+1
    if "!str:-=!" equ "!str!" (
       if not defined #!strs! (
          if not defined flag set "nums=!nums!%%a,"
          ) else (
          if not defined flag set "nums=!nums![%%a,"&set "flag=a"
       )
       ) else (
       if "!str:~-1,1!" equ "-" (
          if not defined flag set "nums=!nums![%%a,"&set "flag=a"
          ) else (
          for %%b in (!m!) do (
              set "var=!$%%b!"
              if "!var:~,1!" neq "-" if not defined #!strs! if defined flag set "nums=!nums!%%a],"&set "flag="
          )
       )
    )
)
echo.&echo.&echo AB集合的并集为：{!nums:~,-1!}
pause>nul
复制代码

[ 本帖最后由 batman 于 2010-4-16 09:58 编辑 ]

qzwqzw

哦，so sorry
我说的不是4的问题
而是以下的集合会出错
set "a=1 3-6 10 20-30 32-60 200-3000 5000 6000-7999 9002 9500 2 5 31 300-500 8000-9001 9500"

neorobin

先做个并集的, 以后再抽空做个交集的, 补集难度较小, 暂不支持元素重复, 逆序排列

@echo off&setlocal enabledelayedexpansion
set /p debug=要以调试方式运行吗?[y/n][直接回车=n]:

set LMin=1
:getLUFlag
  set /a "LMin<<=1"
  if %LMin% lss 0 set /a UMax=-(LMin+1)&goto :endLUFlag
goto :getLUFlag
:endLUFlag
echo 小于全集下限的标志数值=%LMin%, 大于全集上限的标志数值=%UMax%

set "X={[-71,-54],[3,6],10,[20,30],  [32,60],[200,  3000  ],5000,[6000,8000],9000,9500}"
set "Y={-66,-33,2,5,31,[300,500],[8000,9000],9500, 9876, 9932}"
(call :initSet X&call :outputSet X&call :initSet Y&call :outputSet Y)
(call :Union X Y XUY&call :outputSet XUY)
echo 任意键退出&pause>nul
exit /b

:initSet
set "%1=!%1: =!" & set "%1=!%1:{=!" & set "%1=!%1:}=!"
set "pnt%1=0" & set "flag=CN"
for %%i in (!%1!) do (
  set "tt=%%i"
  if "!tt:~0,1!"=="[" (
    if "!flag!" equ "L" (echo 集合%1语法错误:%%i&pause&goto :err)
    set "flag=L"
    set /a pnt%1+=1&set "%1L!pnt%1!=!tt:~1!"
  ) else if "!tt:~-1!"=="]" (
    if "!flag!" neq "L" (echo 集合%1语法错误:%%i&pause&goto :err)
    set "flag=R"
    set "%1U!pnt%1!=!tt:~0,-1!"  
  ) else if "!flag!" equ "L"  (echo 集合%1语法错误:%%i&pause&goto :err
  ) else set /a pnt%1+=1&set "%1L!pnt%1!=!tt!"&set "%1U!pnt%1!=!tt!"&set "flag=CN"
)
set /a pnt%1+=1&set "%1L!pnt%1!=!UMax!"&set "%1U!pnt%1!=!UMax!"
exit /b

:Union A B A∪B
(call :copySet %1 A&call :copySet %2 B)
set /a "pntA=1,pntB=1,pntR=0"&(set RL0=%LMin%&set RU0=%LMin%)

:UnionLoop
if "!RL%pntR%!"=="!UMax!" echo 并集完成&goto :returnUnionValue
:UnionSch1
if !AU%pntA%! leq !RU%pntR%! set /a "pntA+=1"&goto :UnionSch1
if !AL%pntA%! leq !RU%pntR%! set "RU!pntR!=!AU%pntA%!"
:UnionSch2
if !BU%pntB%! leq !RU%pntR%! set /a "pntB+=1"&goto :UnionSch2
if !BL%pntB%! leq !RU%pntR%! set "RU!pntR!=!BU%pntB%!"

set "intersec=Y"
if !AL%pntA%! gtr !BU%pntB%! (set "intersec=N") else (
  if !BL%pntB%! gtr !AU%pntA%! set "intersec=N")

set /a pntR+=1
(call :min !AL%pntA%! !BL%pntB%! RL!pntR!)
if "!intersec!"=="Y" (call :max !AU%pntA%! !BU%pntB%! RU!pntR!) else (
  call :min !AU%pntA%! !BU%pntB%! RU!pntR!) 

if /i "!debug!"=="y" (
  echo pntA=!pntA!,pntB=!pntB!,pntR=!pntR!,intersec=!intersec!
  call :outputSet R
)
goto :UnionLoop

:returnUnionValue
(call :copySet R %3)
exit /b

:copySet src dest
for /l %%i in (1 1 10000) do (
  if "!%1L%%i!"=="" (exit /b) else (set %2L%%i=!%1L%%i!&set %2U%%i=!%1U%%i!)
)
exit /b

:min a b min (a,b 以串值调用, min 以变量名调用)
if %1 lss %2 (set %3=%1) else (set %3=%2)
exit /b

:max a b max (a,b 以串值调用, max 以变量名调用)
if %1 gtr %2 (set %3=%1) else (set %3=%2)
exit /b

:outputSet
set /p=%1=<nul
for /l %%i in (1 1 10000) do (
  if "!%1L%%i!"=="" (echo  &exit /b) else set /p=[!%1L%%i!,!%1U%%i!],<nul
)
exit /b

:err
echo 错误, 任意键退出&pause
exit /b
复制代码