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

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

zhouyongjun

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

zhouyongjun

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

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