【代码思维锻炼】关于一个简单逻辑题编码实现的思考

怎么都没人？

算法我很弱。这种题我一般是先推出最小范围，然后再枚举。
抛砖引玉吧：

char[] chars = { 'x','y','z' };



		for (int i = 0; i < chars.length; i++) {

			for (int j = 0; j < chars.length; j++) {

				for (int k = 0; k < chars.length; k++) {

					char a = chars[i];

					char b = chars[j];

					char c = chars[k];

					

					// 满足所有条件

					if ((a != b) && (b!=c) && (a!=c) & (a!='x') && (c!='x') && (c!='z')) {

						System.out.println("a," + a);

						System.out.println("b," + b);

						System.out.println("c," + c);

					}

				}

			}

		}

好吧 ,我承认我算法一般,本能的就想到了穷举所有情况再排除,
基本这就是最低效的方法了.

Quote: 引用 3 楼 sj178220709 的回复:

好吧 ,我承认我算法一般,本能的就想到了穷举所有情况再排除,
基本这就是最低效的方法了.

我的理由是,穷举/遍历/递归这些本来就是计算机擅长的,用这种写法,代码量少,思路简单,模型易抽象.
而如果用人脑思维去分析和考虑各种状态,各种前后逻辑的关联与互斥,其实是在用人脑思维去帮助计算机优化计算模型,
所以谈到这里,大家应该明白了,这其实归根结底也是运行效率和开发效率的取舍,无所谓优劣,关键还是看需求...

怎么去写就不说，一般做这种题我有点偏激，喜欢往递归的方式去想
最开始学java之前做过java50题，每一道题我都认真的自己做出来了，虽然那时候由于能力浅，花了足足一个小时，不过感觉还是很有帮助的。

以前看过一个类此问题，印象有点模糊，好像可以利用位运算知识，具体忘了。

楼主说的好！非常精彩！支持楼主！！！为了混点分我容易么？

先不考虑特殊条件，直接用for循环嵌套获取三人任意组合名单，使用链表或数组保存名单，然后遍历名单，剔除特殊条件的组合。

跟数独类似，设一个2维数组，数组值只能是0,1，最后保证每行每列只有一个1.

我是觉得，首先要规定输入的格式，假设输入的格式为
a    b
意味着a不和b玩
那我们可以有一个struct
{
    char player[n];
    int times[n];
}
times用来存每个player被对手小伙伴抛弃的次数，被抛弃的次数多的找到对手越是简单，可以按照times大小排序来做。
这似乎是最直观的做法？

自己没啥想法，来看看大家怎么想的。 

可以用分支定界法解决。比如对于a来说，他有三个分支可以选，就是x、y、z，但是他说他不打x，那么x分支就剪掉，然后对b、c同理。最后只剩三条分支，就是他们分别对阵谁。这样的一个好处是即使在条件不全的时候，分支法也能找到所有可能的对阵。

public static void main(String[] args) {

        String[] a = {"a","b","c"};

        String[] b = {"x","y","z"};

        List<String> ab = new ArrayList();

        List<String> list = new ArrayList();

        for (int i=0,l=a.length;i<l;i++) {

            String ai = a[i];

            for (int j=0,k=b.length;j<k;j++) {

                String bi = b[j];

                ab.add(ai+bi+",");

                list.add(ai+bi+",");

            }

        }

        //列出所有比赛组合  这个算法人数没限制，可以不是3VS3

        for (int i=0,l=a.length-1;i<l;i++) {

            list = ass(list,ab);

        }

        //根据条件过滤

        for (int i=0,l=list.size();i<l;i++) {

            String all = list.get(i);

            if (all.indexOf("ax")<0&&all.indexOf("cx")<0&&all.indexOf("cz")<0) {

                System.out.println(all);

            }

        }

    }



    public static List<String> ass(List<String> list,List<String> ab) {

        List<String> result = new ArrayList();

        for (int i=0,l=list.size();i<l;i++) {

            String all = list.get(i);

            for (int j=0,k=ab.size();j<k;j++) {

                String s = ab.get(j);

                String _a = s.substring(0,1);

                String _b = s.substring(1,2);

                if (all.indexOf(s)<0&&all.indexOf(_a)<0&&all.indexOf(_b)<0) {

                    String[] alls = (all+s).split(",");

                    int al=alls.length;

                    boolean b = true;

                    for (int ri=0,rl=result.size();ri<rl;ri++) {

                        int an=0;

                        for (int ai=0;ai<al;ai++) {

                            if (result.get(ri).indexOf(alls[ai])>=0) {

                                an++;

                            }

                        }

                        if (an==al) {

                            b = false;

                        }

                    }

                    if (b) {

                        result.add(all+s);

                    }

                }

            }

        }

        return result;

    }

在有限的集合以及有限的条件限定下，求一组解。
这个是关键，我觉得没必要想太复杂，把组合全列出来，在判断下就好。2楼算法换成4V4貌似还得套循环吧，没细看。

你的思路主方法上看，是想先将所有的对阵组合先拿出来，然后再一点点过滤是吧？
这边的疑问主要是：为啥循环调用ass方法a.lenth-1次？ass方法内部的三重for循环具体思路是做什么？

最后提点建议哈：比较复杂的处理、循环、判断处，给出注释；方法体也最好能注释说明下主要作用。注释多了，能够更清晰的表达出你的思路啊~

对于逻辑稍微复杂而且脑子里面一下子设计不出来的这种我就在纸上话，先写汉字，再通过汉字变成代码

Quote: 引用 27 楼 MrsFeng 的回复:

对于逻辑稍微复杂而且脑子里面一下子设计不出来的这种我就在纸上话，先写汉字，再通过汉字变成代码

伪代码就是这么生成的~

大概意思就是依据每个人可能的对手，如果每个人都有两个或者以上的对手，那该题无解，不知道这个理解对不对

Quote: 引用 26 楼 qyp199312 的回复:

大概意思就是依据每个人可能的对手，如果每个人都有两个或者以上的对手，那该题无解，不知道这个理解对不对

能自己动手就很好~
看了下代码，大致思路是：
1. 在限定条件下，将abc可能的对手放到list中
2. 递归处理abc以及其对应的list，若list内只有一个对手，则加入结果集，并且将这个对手从其它成员的对手列表中去掉。

感觉checkCan方法单独抽出来，作为限定条件，这种抽取思想很好。还有deal的递归处理也不错。
看到你对map的循环操作挺纠结的，这里给提供个更高效的遍历方式供参考：

for(Map.Entry<Character, List<Character>> oneEntry:map.entrySet()){

            oneEntry.getKey();//键

            oneEntry.getValue();//值

        }

（其实我的处理和你类似，只是我用的循环，你用递归实现了）

对于逻辑稍微复杂而且脑子里面一下子设计不出来的这种我就在纸上话，先写汉字，再通过汉字变成代码

Quote: 引用 19 楼 zxcvbnm11920 的回复:

public static void main(String[] args) {

        String[] a = {"a","b","c"};

        String[] b = {"x","y","z"};

        List<String> ab = new ArrayList();

        List<String> list = new ArrayList();

        for (int i=0,l=a.length;i<l;i++) {

            String ai = a[i];

            for (int j=0,k=b.length;j<k;j++) {

                String bi = b[j];

                ab.add(ai+bi+",");

                list.add(ai+bi+",");

            }

        }

        //列出所有比赛组合  这个算法人数没限制，可以不是3VS3

        for (int i=0,l=a.length-1;i<l;i++) {

            list = ass(list,ab);

        }

        //根据条件过滤

        for (int i=0,l=list.size();i<l;i++) {

            String all = list.get(i);

            if (all.indexOf("ax")<0&&all.indexOf("cx")<0&&all.indexOf("cz")<0) {

                System.out.println(all);

            }

        }

    }



    public static List<String> ass(List<String> list,List<String> ab) {

        List<String> result = new ArrayList();

        for (int i=0,l=list.size();i<l;i++) {

            String all = list.get(i);

            for (int j=0,k=ab.size();j<k;j++) {

                String s = ab.get(j);

                String _a = s.substring(0,1);

                String _b = s.substring(1,2);

                if (all.indexOf(s)<0&&all.indexOf(_a)<0&&all.indexOf(_b)<0) {

                    String[] alls = (all+s).split(",");

                    int al=alls.length;

                    boolean b = true;

                    for (int ri=0,rl=result.size();ri<rl;ri++) {

                        int an=0;

                        for (int ai=0;ai<al;ai++) {

                            if (result.get(ri).indexOf(alls[ai])>=0) {

                                an++;

                            }

                        }

                        if (an==al) {

                            b = false;

                        }

                    }

                    if (b) {

                        result.add(all+s);

                    }

                }

            }

        }

        return result;

    }

在有限的集合以及有限的条件限定下，求一组解。
这个是关键，我觉得没必要想太复杂，把组合全列出来，在判断下就好。2楼算法换成4V4貌似还得套循环吧，没细看。

感谢兄台的分享。
你的思路主方法上看，是想先将所有的对阵组合先拿出来，然后再一点点过滤是吧？
这边的疑问主要是：为啥循环调用ass方法a.lenth-1次？ass方法内部的三重for循环具体思路是做什么？

最后提点建议哈：比较复杂的处理、循环、判断处，给出注释；方法体也最好能注释说明下主要作用。注释多了，能够更清晰的表达出你的思路啊~

Quote: 引用 18 楼 coolbamboo2008 的回复:

可以用分支定界法解决。比如对于a来说，他有三个分支可以选，就是x、y、z，但是他说他不打x，那么x分支就剪掉，然后对b、c同理。最后只剩三条分支，就是他们分别对阵谁。这样的一个好处是即使在条件不全的时候，分支法也能找到所有可能的对阵。

分支定界，顶一个~
这里试着整理下你的算法：
1. 根据限定条件，得到初始化分支对应情况：a可能的分支有{y,z}，b可能的分支有{x,y,z}，c可能的分支有{y}
2. 遍历abc的对阵分支
3. 记录遍历元素个数numBefore
4. 若i(为a/b/c)的对阵能唯一确定为j(为x/y/z)，则将i从abc遍历集合中去掉（因为他的分支已唯一，不需再遍历），其他成员的分支中去掉j
5. 记录遍历元素剩余个数numAfter，若numAfter==numBefore则跳出循环；否则重复2到5步
6. 得到abc所有可能对阵选手的分支集合

也不知道这总结的还算不算分支定界了

楼上给出思路的同志还是很不错的。
其实我觉得算法思路或者叫建模比较好想。难点是在如果把建模/思路用代码表示出来。

能不能用面像对像的思想来看待呢？

Quote: 引用 38 楼 u010684923 的回复:

能不能用面像对像的思想来看待呢？

如何搞起？

Quote: 引用 39 楼 oh_Maxy 的回复:

Quote: 引用 38 楼 u010684923 的回复:

能不能用面像对像的思想来看待呢？

如何搞起？

我正在思索中，我是想把这问题中如球队（Team）,球员（player）都对像化，然后在比赛的方法中传球队甲和乙做为参数，把所有可能出现的球员对阵都放入一个Set中，再用一个方法根据条件把这个Set中的匹配，这样就把满足条件的和不满足条件的都分离出来了，结果也就出来了。
这个想法有问题么，求指导。

个人觉得这中类似问题用一个矩阵的可以解决
  x y z
a 1 0 0
b 0 0 0
c 1 0 1
放到矩阵中，他给定的条件放入矩阵，只要找每行（列）只有一个0的就可一匹配，然后删除此行（列），案后继续，知道删除所有。
觉得这个操作肯定有很多优化地方，随着数据增大可以用bitmap，假设如果是16位存，11111111 10111111 就可以不用循环行（列）次，直接使用数值大小判断有几位为零，可以增加效率。
仅供参考

Quote: 引用 43 楼 Trageday 的回复:

个人觉得这中类似问题用一个矩阵的可以解决
  x y z
a 1 0 0
b 0 0 0
c 1 0 1
放到矩阵中，他给定的条件放入矩阵，只要找每行（列）只有一个0的就可一匹配，然后删除此行（列），案后继续，知道删除所有。
觉得这个操作肯定有很多优化地方，随着数据增大可以用bitmap，假设如果是16位存，11111111 10111111 就可以不用循环行（列）次，直接使用数值大小判断有几位为零，可以增加效率。
仅供参考

嗯，你的2维数组的思路，和14L蛮像的。需要优化一点：在删除此行时，需要根据取值，将其它行的对应列的值设置为1，否则影响剩余行的判定。
另外，bitmap的思路，能否再详细解释下？

Quote: 引用 44 楼 oh_Maxy 的回复:

Quote: 引用 43 楼 Trageday 的回复:

个人觉得这中类似问题用一个矩阵的可以解决
  x y z
a 1 0 0
b 0 0 0
c 1 0 1
放到矩阵中，他给定的条件放入矩阵，只要找每行（列）只有一个0的就可一匹配，然后删除此行（列），案后继续，知道删除所有。
觉得这个操作肯定有很多优化地方，随着数据增大可以用bitmap，假设如果是16位存，11111111 10111111 就可以不用循环行（列）次，直接使用数值大小判断有几位为零，可以增加效率。
仅供参考

嗯，你的2维数组的思路，和14L蛮像的。需要优化一点：在删除此行时，需要根据取值，将其它行的对应列的值设置为1，否则影响剩余行的判定。
另外，bitmap的思路，能否再详细解释下？

我想知道这个比赛名单一定是唯一的吗，那么如果不是唯一的情况，如何遍历所有情况的比赛名单？

for使用太多确实容易出错的啊，但是这题貌似用for最直观

跟数独类似，设一个2维数组，数组值只能是0,1，最后保证每行每列只有一个1.

暴力搜索版，其中可优化的部分很多，时间复杂度快要到n!了，期望有高手来个O（n^2）的

#!/usr/bin/python3.3



"""

 在执行前请填充游戏比赛名单

 名单表如下：

     x    y   z

  a  0   -1  -1

  b -1   -1  -1

  c  0   -1   0

  其中0表示不可能，-1表示未知，1表示可以

  根据已知信息其中填充0的地方为不可能与之比赛，填充-1的地方

  表示有可能与其比赛

"""

game_list = [

        [0,-1,-1],

        [-1,-1,-1],

        [0,-1,0]

        ]



member_num = 3

"""

判断是否为一种比赛列表的可能并打印

"""

def judge():

    # check row

    for row in range(member_num):

        row_sum = 0

        for col in range(member_num):

            row_sum += game_list[row][col]

        if 1 != row_sum:

            return

    # check col

    for col in range(member_num):

        col_sum = 0

        for row in range(member_num):

            col_sum += game_list[row][col]

        if 1 != col_sum:

            return

    print("find ",game_list)

    return

"""

进行剪枝

"""

def cut(pos):

    for i in range(pos):

        if -1 == game_list[i // member_num][i % member_num]:

            return False;

    return True

"""

算法所要做的工作是搜索每一行每一列只能填充一个1的情况

因此我们使用深度优先搜索

"""

def dfs(pos):

    #print("pos",pos)

    if cut(pos) == False:

        return

    for i in range(pos,member_num ** 2):

        #print("i",i)

        row = i // member_num

        col = i % member_num

        #print("row:",row,"col",col)

        old_value = game_list[row][col]

        if -1 == old_value:

            game_list[row][col] = 0

            dfs(i + 1)

            game_list[row][col] = 1

            dfs(i + 1)

            game_list[row][col] = old_value

    judge()

    return



dfs(0)

Quote: 引用 54 楼 p569354158 的回复:

暴力搜索版，其中可优化的部分很多，时间复杂度快要到n!了，期望有高手来个O（n^2）的

#!/usr/bin/python3.3



"""

 在执行前请填充游戏比赛名单

 名单表如下：

     x    y   z

  a  0   -1  -1

  b -1   -1  -1

  c  0   -1   0

  其中0表示不可能，-1表示未知，1表示可以

  根据已知信息其中填充0的地方为不可能与之比赛，填充-1的地方

  表示有可能与其比赛

"""

game_list = [

        [0,-1,-1],

        [-1,-1,-1],

        [0,-1,0]

        ]



member_num = 3

"""

判断是否为一种比赛列表的可能并打印

"""

def judge():

    # check row

    for row in range(member_num):

        row_sum = 0

        for col in range(member_num):

            row_sum += game_list[row][col]

        if 1 != row_sum:

            return

    # check col

    for col in range(member_num):

        col_sum = 0

        for row in range(member_num):

            col_sum += game_list[row][col]

        if 1 != col_sum:

            return

    print("find ",game_list)

    return

"""

进行剪枝

"""

def cut(pos):

    for i in range(pos):

        if -1 == game_list[i // member_num][i % member_num]:

            return False;

    return True

"""

算法所要做的工作是搜索每一行每一列只能填充一个1的情况

因此我们使用深度优先搜索

"""

def dfs(pos):

    #print("pos",pos)

    if cut(pos) == False:

        return

    for i in range(pos,member_num ** 2):

        #print("i",i)

        row = i // member_num

        col = i % member_num

        #print("row:",row,"col",col)

        old_value = game_list[row][col]

        if -1 == old_value:

            game_list[row][col] = 0

            dfs(i + 1)

            game_list[row][col] = 1

            dfs(i + 1)

            game_list[row][col] = old_value

    judge()

    return



dfs(0)

好吧，沸腾版的代码，当做shell看了。。

这边看了你的代码，大概思路是将任意-1不确定的地方，分别设置为0不可能或1确定，递归下去，最终产生的数组只有0或1，通过judge的校验是否为符合要求的结果。如果有多种解，可以全部得到。

这个的算法复杂度看了下，dfs是递归加调用cut和judge，但是dfs的递归应该是每个i都要遍历一遍，复杂度应该还是n，感觉总复杂度应该是n*(n+2n^2)，为n^3。空间复杂度，因为是递归遍历数组每一个元素，这个空间复杂度可能算是n!了。不晓得分析的对不对。。。

Quote:

建模思路很清晰，代码实现也很具有目的性，要顶~ --------------------编程问答--------------------

引用 59 楼 fangmingshijie 的回复:

看了一下，想了一下。我的思路是把两队对手分别放到一个集合里，规约条件放到一个集合里(如a不和x比，就定义为a<>x),然后就拿两个集合组合和规约条件比较，然后按条件依次剔除对手集合。

是了，思路差不多，感觉建模还是有点出入。a<>x这种方式，可能导致实现的时候代码会复杂些（因为要解析）。
还有一个关键点，就是一旦某一对选手确定了，那么就隐含着这对选手将不会在其它对中出现了。（假设c和y确认为一对对手，那么y将不会出现在a、b可能的对手集中了）。 --------------------编程问答--------------------

引用 62 楼 lwb314 的回复:

		while(caseList.size()>0){

			List<String> caseI = caseList.get(i);

			List<String> team3 = new ArrayList<String>();

			team3.addAll(team2);//复制一份team2因为要从team2里移除队员，不能把模型破坏了

			if(team2.size()-caseI.size()==0){//因为第一个位置是说话的人，所以不会被移除

				team1.remove(caseI.get(0));//队伍1，把条件第一个位置移除，就是说话的那个人

				team3.removeAll(caseI);//复制的队伍2，把case里说的不跟自己对阵的人都移除，这样只剩1个人

				team2.remove(team3.get(0));//队伍2把复制队伍2也就是队伍3里的人移除，因为他已经跟队伍1里的人对阵了

				System.out.println("对阵情况:"+caseI.get(0)+"---"+team3.get(0));

				caseList.remove(i);//条件满足了就把这个条件移除

				i=0;

				continue;

			}

			i++;

			if(i==caseList.size()){

				i=0;//第一个满足的条件可能在所有条件中间，一次循环条件集合不足以实现，所以到头以后需要从头再来

			}

		}

又加了点注释

感觉最大的亮点是注释详细，这个要给你32个赞~

case1、case2、caseList的这种建模，关系挺松散的，这边有个实现方式看看会不会简单点：Map<String,List<String>> map;// key为team1的选手，value为其不可能对手集。
相当于把case1、case2、caseList合并起来了。

还有一个瑕疵的地方是，不是所有的对阵情况都在循环体内得到的。看了下，感觉是因为循环、判断条件依赖list的size来比较，而非list的内容。这种处理方式在处理复杂问题的时候，容易出错。
--------------------编程问答--------------------

引用 65 楼 oh_Maxy 的回复:

Quote: 引用 62 楼 lwb314 的回复:

		while(caseList.size()>0){

			List<String> caseI = caseList.get(i);

			List<String> team3 = new ArrayList<String>();

			team3.addAll(team2);//复制一份team2因为要从team2里移除队员，不能把模型破坏了

			if(team2.size()-caseI.size()==0){//因为第一个位置是说话的人，所以不会被移除

				team1.remove(caseI.get(0));//队伍1，把条件第一个位置移除，就是说话的那个人

				team3.removeAll(caseI);//复制的队伍2，把case里说的不跟自己对阵的人都移除，这样只剩1个人

				team2.remove(team3.get(0));//队伍2把复制队伍2也就是队伍3里的人移除，因为他已经跟队伍1里的人对阵了

				System.out.println("对阵情况:"+caseI.get(0)+"---"+team3.get(0));

				caseList.remove(i);//条件满足了就把这个条件移除

				i=0;

				continue;

			}

			i++;

			if(i==caseList.size()){

				i=0;//第一个满足的条件可能在所有条件中间，一次循环条件集合不足以实现，所以到头以后需要从头再来

			}

		}

又加了点注释

感觉最大的亮点是注释详细，这个要给你32个赞~

case1、case2、caseList的这种建模，关系挺松散的，这边有个实现方式看看会不会简单点：Map<String,List<String>> map;// key为team1的选手，value为其不可能对手集。
相当于把case1、case2、caseList合并起来了。

还有一个瑕疵的地方是，不是所有的对阵情况都在循环体内得到的。看了下，感觉是因为循环、判断条件依赖list的size来比较，而非list的内容。这种处理方式在处理复杂问题的时候，容易出错。

谢谢楼主点评，可能是我还没完全理解提议，Map<String,List<String>>我一开想用这种，但是后来嫌麻烦，而且我以为一个人只能发表一次讲话，你的意识是key如果是a,后边的List里有2个case,那么说明他说过2次话，他先说不跟X对阵，后边可能又说了不跟Y对阵，这种情况我没考虑。
第2个问题我用数组长度，而不用内容也是基于这个原因，我理解的是每个人说的都是他的全部不对阵表，如果有没说到的人，是因为那个人已经被在另外一个人的条件中覆盖到了，所以他不再说了，现在想想，a也可能说出不与x,y对阵的这种话，c说不与x,z对阵这种话是吗？这种情况我也没考虑，这样就复杂，算法需要改，不过基于每个人说的话去过滤的这个思路我觉得好像没问题，谢谢楼主给我赞 --------------------编程问答-------------------- 研究一下 --------------------编程问答--------------------
抽取一下题目的要求，有一个基本的功能点：
1. 比赛成员
队员、小队、分组(两个任意成员)、赛程(一组分组、即题目的一个解)。
2. 分组功能
将比赛成员排列组合成分组、赛程。
3. 评判功能
判断分组是否有效

大概设计了一下，主要分了3个包+1个工具包
model包：对象包，抽象比赛元素
-BaseElement 基础比赛成员，抽象类
-Member 队员，比赛个人类
-Team 小队，比赛队伍
-Group 分组，两个比赛成员的分组结果
-ContestList 赛程，一组分组结果

grouping包：分组包，实现参赛成员的分组配对功能
-ElementGrouping 分组接口，约定了分组规则的初始化方法、任意比赛成员的分组方法
-AbstractElementGrouping 抽象分组类，聚合了分组评判规则，实现任意比赛成员的分组，比赛成员的自动归类
-DefaultElementGrouping 默认分组类，实现了小队之间的分组，队员之间的分组，以及分组算法

validate包：评判包，实现分组条件的判断
-Judging 评判接口，约定了排除条件的初始化方法、任意成员之间的条件判断方法
-AbstractModelJudging 抽象对象评判类，实现了初始化排除名单的方法、聚合排除列表
-NameJudging 按名称的分组评判类
-TwoElementJudging 任意两成员间的分组评判类

util包：一些工具方法
-algorithm包下的PermutationUtil 提供全排列算法
-ContestListUtil 赛程输出方法
-JudgingUtil 评判的辅助类，选用了一票否决制算法，即任意条件不满足，则评判不通过，赛程作废
-ModelUtil 分组的辅助类，将任意比赛成员分组
--------------------编程问答-------------------- 好像不能直接上传代码包啊，看来只能一个一个类帖上来了。 --------------------编程问答-------------------- grouping包：
ElementGrouping.java

package hinanai.tenshi.contest.grouping;



import hinanai.tenshi.contest.model.BaseElement;

import hinanai.tenshi.contest.model.ContestList;

import hinanai.tenshi.contest.validate.Judging;



import java.util.List;



/**

 * 

 * @description: 分组接口

 * @Date 2013-12-18 下午5:00:21

 * 

 */

public inte易做图ce ElementGrouping {



	/**

	 * 

	 * <p>

	 * 初始化赛程分组规则

	 * </p>

	 * 

	 * @param judgings

	 *            赛程分组规则接口

	 */

	public void initJudgings(List<Judging> judgings);



	/**

	 * 

	 * <p>

	 * 参赛成员分组

	 * </p>

	 * 

	 * @param elements

	 *            参数成员

	 * @return 全部可能的赛程

	 */

	public List<ContestList> mateAllElement(List<BaseElement> elements);

}

AbstractElementGrouping.java

package hinanai.tenshi.contest.grouping;



import hinanai.tenshi.contest.model.BaseElement;

import hinanai.tenshi.contest.model.ContestList;

import hinanai.tenshi.contest.model.Group;

import hinanai.tenshi.contest.model.Member;

import hinanai.tenshi.contest.model.Team;

import hinanai.tenshi.contest.validate.Judging;



import java.util.ArrayList;

import java.util.Collections;

import java.util.List;



/**

 * 

 * @description: 分组抽象类

 * @Date 2013-12-18 下午5:07:52

 * 

 */

public abstract class AbstractElementGrouping implements ElementGrouping {



	/**

	 * 赛程分组评判规则

	 */

	protected List<Judging> judgings;



	/**

	 * 

	 * <p>

	 * 初始化评判规则

	 * </p>

	 * 

	 * @param judgings

	 *            评判规则

	 */

	@Override

	public void initJudgings(List<Judging> judgings) {

		this.judgings = judgings;

	}



	/**

	 * 

	 * <p>

	 * 分组

	 * </p>

	 * 

	 * @param elements

	 *            参数成员

	 * @return 全部可能赛程

	 */

	@Override

	public List<ContestList> mateAllElement(List<BaseElement> elements) {

		// safe

		if (elements == null) {

			throw new NullPointerException("elements is null.");

		}

		// init

		List<Team> teams = new ArrayList<Team>();

		List<Member> members = new ArrayList<Member>();

		List<ContestList> contestLists = new ArrayList<ContestList>();



		// 参数成员分类

		for (BaseElement element : elements) {

			// 小队

			if (element instanceof Team) {

				teams.add((Team) element);

			}

			// 队员

			if (element instanceof Member) {

				members.add((Member) element);

			}

		}

		// 小队赛程安排

		contestLists.addAll(this.mateAllTeam(teams));

		// 成员赛程安排

		contestLists.addAll(this.mateAllMember(members));

		return contestLists;

	}



	/**

	 * 

	 * <p>

	 * 全部小队赛程安排

	 * </p>

	 * 

	 * @param teams

	 * @return

	 */

	protected List<ContestList> mateAllTeam(List<Team> teams) {

		// safe

		if (teams == null || teams.isEmpty()) {

			return Collections.emptyList();

		}

		// init

		List<ContestList> list = new ArrayList<ContestList>();



		// 单轮赛

		for (Team team1 : teams) {

			for (Team team2 : teams) {

				// 小队分组

				List<ContestList> contestLists = this.mateTeam(team1, team2);

				// 小队分组无解

				if (contestLists == null) {

					continue;

				}

				// 小队分组完成、加入全部赛程列表

				list.addAll(contestLists);

			}

		}

		return list;

	}



	/**

	 * 

	 * <p>

	 * 队员分组

	 * </p>

	 * 

	 * @param members

	 *            队员集合

	 * @return 分组赛程

	 */

	protected List<ContestList> mateAllMember(List<Member> members) {

		// safe

		if (members == null || members.isEmpty()) {

			return Collections.emptyList();

		}

		// init

		List<ContestList> list = new ArrayList<ContestList>();



		// 单轮赛

		// TODO 非组队队员单轮赛算法有bug 2013-12-19

		for (Member member1 : members) {

			ContestList contestList = new ContestList();

			contestList.setGroups(new ArrayList<Group>());

			for (Member member2 : members) {

				// 队员分组

				Group group = this.mateMember(member1, member2);

				// 分组无解

				if (group == null) {

					continue;

				}

				// 队员分组加入赛程

				contestList.getGroups().add(group);

			}

			// 加入赛程

			list.add(contestList);

		}

		return list;

	}



	/**

	 * 

	 * <p>

	 * 小队赛程安排

	 * </p>

	 * 

	 * @param team1

	 *            参赛小队

	 * @param team2

	 *            参赛小队

	 * @return 全部可能的赛程列表

	 */

	protected abstract List<ContestList> mateTeam(Team team1, Team team2);



	/**

	 * 

	 * <p>

	 * 队员赛程安排

	 * </p>

	 * 

	 * @param member1

	 *            队员

	 * @param member2

	 *            队员

	 * @return 分组结果

	 */

	protected abstract Group mateMember(Member member1, Member member2);

}

DefaultElementGrouping.java

package hinanai.tenshi.contest.grouping;



import hinanai.tenshi.contest.model.ContestList;

import hinanai.tenshi.contest.model.Group;

import hinanai.tenshi.contest.model.Member;

import hinanai.tenshi.contest.model.Team;

import hinanai.tenshi.contest.utils.JudgingUtil;

import hinanai.tenshi.contest.utils.algorithm.PermutationUtil;



import java.util.ArrayList;

import java.util.Collections;

import java.util.Iterator;

import java.util.List;



/**

 * 

 * @description: 默认比赛分组类

 * @Date 2013-12-18 下午5:45:31

 * 

 */

public class DefaultElementGrouping extends AbstractElementGrouping implements

		ElementGrouping {



	/**

	 * 

	 * <p>

	 * 小队分组

	 * </p>

	 * 

	 * @param team1

	 *            小队

	 * @param team2

	 *            小队

	 * @return 全部可能的赛程列表

	 */

	@Override

	protected List<ContestList> mateTeam(Team team1, Team team2) {

		// safe

		if (team1 == null || team2 == null) {

			throw new NullPointerException("team is null.");

		}

		// 小队分组

		Group teamGroup = JudgingUtil.doJudging(judgings, team1, team2);

		// 小队分组无解

		if (teamGroup == null) {

			return Collections.emptyList();

		}

		// 小队分组成功，安排队员分组

		List<ContestList> contestLists = this.mateTeamMember(teamGroup, team1,

				team2);

		return contestLists;

	}



	/**

	 * 

	 * <p>

	 * 队员分组

	 * </p>

	 * 

	 * @param member1

	 *            队员

	 * @param member2

	 *            队员

	 * @return 分组

	 */

	@Override

	protected Group mateMember(Member member1, Member member2) {

		if (member1 == null || member2 == null) {

			throw new NullPointerException("member is null.");

		}

		// 两队员分组

		return JudgingUtil.doJudging(judgings, member1, member2);

	}



	/**

	 * 

	 * <p>

	 * 小队队员分组

	 * </p>

	 * 

	 * @param teamGroup

	 *            小队分组

	 * @param team1

	 *            小队

	 * @param team2

	 *            小队

	 * @return 赛程

	 */

	private List<ContestList> mateTeamMember(Group teamGroup, Team team1,

			Team team2) {

		// safe

		if (team1.getMembers() == null || team2.getMembers() == null) {

			return Collections.emptyList();

		}

		// 两小队的队员排列组合

		List<ContestList> list = this.permutation(team1.getMembers(),

				team2.getMembers());

		// 队员分组赛程前插入小队分组结果

		for (ContestList contestList : list) {

			contestList.getGroups().add(0, teamGroup);

		}

		return list;

	}



	/**

	 * 

	 * <p>

	 * 两队队员排列组合

	 * </p>

	 * 

	 * @param members1

	 *            小队队员1

	 * @param members2

	 *            小队队员2

	 * @return 赛程

	 */

	private List<ContestList> permutation(List<Member> members1,

			List<Member> members2) {

		// init

		List<ContestList> contestLists = new ArrayList<ContestList>();

		// 小队1队员全排列

		List<List<Member>> fullpermutation1 = PermutationUtil

				.fullpermutation(members1);

		// 小队2队员全排列

		List<List<Member>> fullpermutation2 = PermutationUtil

				.fullpermutation(members2);

		// 全排列求解

		for (List<Member> permutationmembers1 : fullpermutation1) {

			for (List<Member> permutationmembers2 : fullpermutation2) {

				// 当前排列赛程队员组合

				ContestList contestList = this.combination(permutationmembers1,

						permutationmembers2);

				// 组合无解

				if (contestList == null) {

					continue;

				}

				// 组合赛程加入赛程列表

				contestLists.add(contestList);

			}

		}

		return contestLists;

	}



	/**

	 * 

	 * <p>

	 * 两小队队员组合

	 * </p>

	 * 

	 * @param members1

	 *            小队队员

	 * @param members2

	 *            小队队员

	 * @return

	 */

	private ContestList combination(List<Member> members1, List<Member> members2) {

		// init

		ContestList contestList = new ContestList();

		Iterator<Member> iterator2 = members2.iterator();

		// 遍历小队1

		for (Member member1 : members1) {

			// 小队2有出战成员、则进行分组

			if (iterator2.hasNext()) {

				Member member2 = iterator2.next();

				// 两队员分组

				Group group = this.mateMember(member1, member2);

				// 分组无解

				if (group == null) {

					// 单轮赛：一次分组失败、本次赛程作废

					return null;

				}

				// 分组加入赛程

				contestList.getGroups().add(group);

			}

		}

		return contestList;

	}



}

--------------------编程问答-------------------- 原来csdn还有不能连续回复3次的要求。

model包：
BaseElement.java

package hinanai.tenshi.contest.model;



/**

 * 

 * @description: 基础参赛成员抽象类

 * @Date 2013-12-18 下午4:01:07

 * 

 */

public abstract class BaseElement {



	public BaseElement() {

	}



	public BaseElement(String name) {

		this.name = name;

	}



	/**

	 * 成员名称

	 */

	protected String name;



	/**

	 * 成员类型名称

	 */

	protected String typeName;



	public String getName() {

		return name;

	}



	public void setName(String name) {

		this.name = name;

	}



	public String getTypeName() {

		return typeName;

	}

}

Member.java

package hinanai.tenshi.contest.model;



/**

 * 

 * @description: 队员

 * @Date 2013-12-18 下午3:56:28

 * 

 */

public class Member extends BaseElement {



	public Member() {

	}



	public Member(String name) {

		super(name);

		this.typeName = "member";

	}

}

Team.java

package hinanai.tenshi.contest.model;



import java.util.ArrayList;

import java.util.List;



/**

 * 

 * @description: 小队

 * @Date 2013-12-18 下午3:55:14

 * 

 */

public class Team extends BaseElement {



	public Team() {

	}



	public Team(String name) {

		super(name);

		this.typeName = "team";

	}



	/**

	 * 小队队员

	 */

	private List<Member> members = new ArrayList<Member>();



	public List<Member> getMembers() {

		return members;

	}



	public void setMembers(List<Member> members) {

		this.members = members;

	}

}

Group.java

package hinanai.tenshi.contest.model;



/**

 * 

 * @description: 赛程分组

 * @Date 2013-12-18 下午5:02:07

 * 

 */

public class Group {



	/**

	 * 参数成员1

	 */

	private BaseElement element1;



	/**

	 * 参数成员2

	 */

	private BaseElement element2;



	public BaseElement getElement1() {

		return element1;

	}



	public void setElement1(BaseElement element1) {

		this.element1 = element1;

	}



	public BaseElement getElement2() {

		return element2;

	}



	public void setElement2(BaseElement element2) {

		this.element2 = element2;

	}

}

ContestList.java

package hinanai.tenshi.contest.model;



import java.util.ArrayList;

import java.util.List;



/**

 * 

 * @description: 赛程

 * @Date 2013-12-18 下午5:25:40

 * 

 */

public class ContestList {



	/**

	 * 赛程分组列表

	 */

	private List<Group> groups = new ArrayList<Group>();



	public List<Group> getGroups() {

		return groups;

	}



	public void setGroups(List<Group> groups) {

		this.groups = groups;

	}

}

test包：

package hinanai.tenshi.contest.test;



import hinanai.tenshi.contest.grouping.DefaultElementGrouping;

import hinanai.tenshi.contest.grouping.ElementGrouping;

import hinanai.tenshi.contest.model.BaseElement;

import hinanai.tenshi.contest.model.ContestList;

import hinanai.tenshi.contest.model.Member;

import hinanai.tenshi.contest.model.Team;

import hinanai.tenshi.contest.utils.ContestListUtil;

import hinanai.tenshi.contest.validate.Judging;

import hinanai.tenshi.contest.validate.NameJudging;

import hinanai.tenshi.contest.validate.TwoElementJudging;



import java.util.ArrayList;

import java.util.List;



/**

 * 

 * @description: 组队比赛

 * @Date 2013-12-18 上午10:19:13

 * 

 */

public class TeamContest {



	/**

	 * 分组接口

	 */

	private ElementGrouping elementGrouping;



	/**

	 * 参赛成员

	 */

	private final List<BaseElement> elements = new ArrayList<BaseElement>();



	/**

	 * 

	 * <p>

	 * 初始化

	 * </p>

	 */

	public void init() {

		// 初始化

		initGrouping();

		// 初始化小队和赛程判断规则

		initTeamsAndJudging();

	}



	/**

	 * 

	 * <p>

	 * 初始化分组接口

	 * </p>

	 */

	protected void initGrouping() {

		elementGrouping = new DefaultElementGrouping();

	}



	/**

	 * 

	 * <p>

	 * 初始化队伍和赛程评判规则

	 * </p>

	 */

	protected void initTeamsAndJudging() {

		// jia team

		Team team1 = new Team("jia");

		Member a = new Member("a");

		Member b = new Member("b");

		Member c = new Member("c");

		team1.getMembers().add(a);

		team1.getMembers().add(b);

		team1.getMembers().add(c);



		// yi team

		Team team2 = new Team("yi");

		Member x = new Member("x");

		Member y = new Member("y");

		Member z = new Member("z");

		team2.getMembers().add(x);

		team2.getMembers().add(y);

		team2.getMembers().add(z);



		// 加入为比赛成员

		elements.add(team1);

		elements.add(team2);



		// 赛程评判规则

		List<Judging> list = new ArrayList<Judging>();

		// 队员名称评判规则

		Judging memberJudging = new NameJudging();

		// a except x

		memberJudging.initExceptElement(a, x);

		// c except x,z

		memberJudging.initExceptElement(c, x);

		memberJudging.initExceptElement(c, z);

		// 加入规则

		list.add(memberJudging);



		// 双成员评判规则

		Judging teamJudging = new TwoElementJudging();

		list.add(teamJudging);

		// 初始化所有规则

		elementGrouping.initJudgings(list);

	}



	/**

	 * 

	 * <p>

	 * 两队比赛

	 * </p>

	 */

	public void twoTeam() {

		// 赛程安排、获得所有可能的赛程列表

		List<ContestList> contestLists = elementGrouping

				.mateAllElement(elements);

		// 打印全部赛程

		ContestListUtil.printContestLists(contestLists);

	}



	public static void main(String[] args) {

		TeamContest contest = new TeamContest();

		// 初始化

		contest.init();

		// 两队比赛

		contest.twoTeam();

	}

}

utils包:
ContestListUtil.java

package hinanai.tenshi.contest.utils;



import hinanai.tenshi.contest.model.ContestList;

import hinanai.tenshi.contest.model.Group;



import java.util.List;



/**

 * 

 * @description: 赛程工具类

 * @Date 2013-12-18 上午10:34:57

 * 

 */

public abstract class ContestListUtil {



	/**

	 * 

	 * <p>

	 * 输出全部赛程

	 * </p>

	 * 

	 * @param list

	 *            赛程集合

	 */

	public static void printContestLists(List<ContestList> list) {

		if (list == null || list.isEmpty()) {

			return;

		}

		int index = 1;

		for (ContestList contestList : list) {

			System.out.println("=======================");

			System.out.println("Print ContestList " + index);

			System.out.println("=======================");

			printContestList(contestList);

			index++;

		}

	}



	/**

	 * 

	 * <p>

	 * 输出赛程

	 * </p>

	 * 

	 * @param contestList

	 *            赛程

	 */

	public static void printContestList(ContestList contestList) {

		if (contestList == null || contestList.getGroups() == null

				|| contestList.getGroups().isEmpty()) {

			return;

		}

		for (Group group : contestList.getGroups()) {

			System.out.println(group.getElement1().getTypeName() + "-"

					+ group.getElement1().getName() + " vs "

					+ group.getElement1().getTypeName() + "-"

					+ group.getElement2().getName());

		}

	}

}

JudgingUtil.java

package hinanai.tenshi.contest.utils;



import hinanai.tenshi.contest.model.BaseElement;

import hinanai.tenshi.contest.model.Group;

import hinanai.tenshi.contest.validate.Judging;



import java.util.List;



/**

 * 

 * @description: 评判工具类

 * @Date 2013-12-18 下午6:29:35

 * 

 */

public abstract class JudgingUtil {



	/**

	 * 

	 * <p>

	 * 评判并分组

	 * </p>

	 * 

	 * @param judgings

	 *            评判条件

	 * @param element1

	 *            成员

	 * @param element2

	 *            成员

	 * @return 分组

	 */

	public static Group doJudging(List<Judging> judgings, BaseElement element1,

			BaseElement element2) {

		// safe

		if (element1 == null || element2 == null) {

			throw new NullPointerException("member is null.");

		}

		System.out.print("doJudging:" + element1.getName() + " and "

				+ element2.getName());// out - elements



		// 无条件

		if (judgings == null) {

			// out - result

			System.out.println("  ;result=enable;");

			// 创建分组

			return ModelUtil.buildGroup(element1, element2);

		}

		// 遍历全部条件

		for (Judging judging : judgings) {

			// 评判

			boolean judgingFlag = judging.judging(element1, element2);

			// 评判不通过

			if (!judgingFlag) {

				System.out.println("  ;result=disable;");// out - result

				// 一票否决制：任意条件不通过，分组无解

				return null;

			}

		}

		// 通过评判

		System.out.println("  ;result=enable;");// out - result

		// 创建分组

		return ModelUtil.buildGroup(element1, element2);

	}



}

ModelUtil.java

package hinanai.tenshi.contest.utils;



import hinanai.tenshi.contest.model.BaseElement;

import hinanai.tenshi.contest.model.Group;



/**

 * 

 * @description: 对象工具类

 * @Date 2013-12-18 下午6:14:47

 * 

 */

public abstract class ModelUtil {



	/**

	 * 

	 * <p>

	 * 创建分组

	 * </p>

	 * 

	 * @param element1

	 *            成员

	 * @param element2

	 *            成员

	 * @return 分组

	 */

	public static Group buildGroup(BaseElement element1, BaseElement element2) {

		// safe

		if (element1 == null || element2 == null) {

			return null;

		}

		// 创建分组

		Group group = new Group();

		group.setElement1(element1);

		group.setElement2(element2);

		return group;

	}

}

PermutationUtil.java

package hinanai.tenshi.contest.utils.algorithm;



import java.util.ArrayList;

import java.util.List;



/**

 * 

 * @description: 排列工具类

 * @Date 2013-12-18 下午4:12:45

 * 

 */

public abstract class PermutationUtil<T> {



	/**

	 * 

	 * <p>

	 * 全排列

	 * </p>

	 * 

	 * @param tList

	 *            待排列集合

	 * @return 全排列集合

	 */

	@SuppressWarnings("unchecked")

	public static <T> List<List<T>> fullpermutation(List<T> tList) {

		// array init

		Object[] array = new Object[tList.size()];

		tList.toArray(array);

		// init

		List<List<T>> fullpermutation = new ArrayList<List<T>>();

		// 试探法

		heuristic((T[]) array, 0, tList.size(), fullpermutation);

		return fullpermutation;

	}



	/**

	 * 

	 * <p>

	 * 试探法全排列算法

	 * </p>

	 * 

	 * @param ts

	 *            待排列数组

	 * @param m

	 *            起点

	 * @param n

	 *            试探点

	 * @param fullpermutation

	 *            全排列集合

	 */

	public static <T> void heuristic(T[] ts, int m, int n,

			List<List<T>> fullpermutation) {

		/*

		 * 抄来的试探法全排列算法

		 */

		int i;

		T t;

		if (m < n - 1) {

			heuristic(ts, m + 1, n, fullpermutation);

			for (i = m + 1; i < n; i++) {

				t = ts[m];

				ts[m] = ts[i];

				ts[i] = t;

				heuristic(ts, m + 1, n, fullpermutation);

				t = ts[m];

				ts[m] = ts[i];

				ts[i] = t;

			}

		} else {

			List<T> tList = new ArrayList<T>();

			// System.out.print("array:");

			for (T tp : ts) {

				// System.out.print(tp.toString());

				tList.add(tp);

			}

			// System.out.println();

			fullpermutation.add(tList);

			// fullpermutation.add(Arrays.asList(ts));

		}

	}



}

--------------------编程问答-------------------- validate包：

Judging.java

package hinanai.tenshi.contest.validate;



import hinanai.tenshi.contest.model.BaseElement;



/**

 * 

 * @description: 比赛评判接口

 * @Date 2013-12-18 下午4:00:39

 * 

 */

public inte易做图ce Judging {



	/**

	 * 

	 * <p>

	 * 初始化评判排除条件

	 * </p>

	 * 

	 * @param origin

	 *            参赛成员

	 * @param except

	 *            参赛成员

	 */

	public void initExceptElement(BaseElement origin, BaseElement except);



	/**

	 * 

	 * <p>

	 * 评判

	 * </p>

	 * 

	 * @param origin

	 *            参赛成员

	 * @param target

	 *            参赛成员

	 * @return

	 */

	public boolean judging(BaseElement origin, BaseElement target);



}

AbstractModelJudging.java

package hinanai.tenshi.contest.validate;



import hinanai.tenshi.contest.model.BaseElement;



import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Set;



/**

 * 

 * @description: 成员评判抽象类

 * @Date 2013-12-18 下午4:11:27

 * 

 */

public abstract class AbstractModelJudging implements Judging {



	/**

	 * 分组评判的排除名单

	 */

	protected final Map<BaseElement, Set<BaseElement>> exceptElementMap = new HashMap<BaseElement, Set<BaseElement>>();



	@Override

	public abstract boolean judging(BaseElement origin, BaseElement target);



	/**

	 * 

	 * <p>

	 * 初始化排除名单

	 * </p>

	 * 

	 * @param origin

	 *            成员

	 * @param except

	 *            排除成员

	 */

	@Override

	public void initExceptElement(BaseElement origin, BaseElement except) {

		// safe

		if (origin == null || except == null) {

			return;

		}



		// 排除

		this.addExcept(origin, except);



		// 单轮赛，互斥：如果a排除b，那么b必然排斥a

		this.addExcept(except, origin);

	}



	/**

	 * 

	 * <p>

	 * 加入排除列表

	 * </p>

	 * 

	 * @param key

	 * @param element

	 */

	protected void addExcept(BaseElement key, BaseElement element) {

		// 排除方

		if (!this.exceptElementMap.containsKey(key)) {

			this.exceptElementMap.put(key, new HashSet<BaseElement>());

		} else if (this.exceptElementMap.get(key) == null) {

			this.exceptElementMap.put(key, new HashSet<BaseElement>());

		}

		// 被排除成员列表

		Set<BaseElement> value = this.exceptElementMap.get(key);

		// 被排除成员已经存在

		if (value.contains(element)) {

			return;

		}

		// 加入被排除成员

		exceptElementMap.get(key).add(element);

	}



}

NameJudging.java

package hinanai.tenshi.contest.validate;



import hinanai.tenshi.contest.model.BaseElement;

import hinanai.tenshi.contest.model.Member;

import hinanai.tenshi.contest.model.Team;



import java.util.Iterator;

import java.util.Set;



/**

 * 

 * @description: 名称评判

 * @Date 2013-12-18 下午4:44:10

 * 

 */

public class NameJudging extends AbstractModelJudging implements Judging {



	/**

	 * 

	 * <p>

	 * 评判

	 * </p>

	 * 

	 * @param origin

	 *            参赛成员

	 * @param target

	 *            参赛成员

	 * @return 评判结果：true-通过;false-不通过

	 */

	@Override

	public boolean judging(BaseElement origin, BaseElement target) {

		// safe

		if (origin == null || target == null) {

			throw new NullPointerException("groupElement is null.");

		}

		// 不在排除条件中

		if (!exceptElementMap.containsKey(origin)) {

			return true;// 通过

		}

		// 成员排除名单

		Set<BaseElement> exceptElementLists = exceptElementMap.get(origin);

		// 遍历名单

		Iterator<BaseElement> iterator = exceptElementLists.iterator();

		while (iterator.hasNext()) {

			BaseElement element = iterator.next();

			// 名称评判

			boolean result = this.judgingName(target, element);

			// 评判不通过

			if (!result) {

				return false;

			}

		}

		// 全部条件通过

		return true;

	}



	/**

	 * 

	 * <p>

	 * 名称评判

	 * </p>

	 * 

	 * @param target

	 *            参赛成员

	 * @param except

	 *            参赛成员

	 * @return 评判结果：true-通过;false-不通过

	 */

	protected boolean judgingName(BaseElement target, BaseElement except) {

		// 小队直接通过

		if (target instanceof Team) {

			return true;

		}

		if (except instanceof Team) {

			return true;

		}

		// 评判双方都是成员

		if (target instanceof Member && except instanceof Member) {

			// safe

			if (target.getName() == null || except.getName() == null) {

				throw new NullPointerException("name is null.");

			}

			// 候选成员在排除名单中

			if (target.getName().equals(except.getName())) {

				// 不通过

				return false;

			}

		}

		// 全部条件通过

		return true;

	}

}

TwoElementJudging.java

package hinanai.tenshi.contest.validate;



import hinanai.tenshi.contest.model.BaseElement;



/**

 * 

 * @description: 双成员评判规则

 * @Date 2013-12-18 下午2:04:37

 * 

 */

public class TwoElementJudging implements Judging {



	/**

	 * 

	 * <p>

	 * 初始化评判规则

	 * </p>

	 * 

	 * @param origin

	 * @param except

	 */

	@Override

	public void initExceptElement(BaseElement origin, BaseElement except) {

		// 无需初始化

	}



	/**

	 * 

	 * <p>

	 * 分组评判

	 * </p>

	 * 

	 * @param origin

	 *            成员

	 * @param target

	 *            成员

	 * @return 是否符合条件：true-符合;false-不符合

	 */

	@Override

	public boolean judging(BaseElement origin, BaseElement target) {

		// 任何成员不和自己比赛

		if (origin == target) {

			return false;

		}

		return true;

	}



}

--------------------编程问答-------------------- 忘记说了。还有个test包，里面灌入了题目要求的条件，用来执行取得符合题意的解。因为题目没有明确说明，我偷懒按照出场做了区分（也就是说“甲vs乙”和“乙vs甲”被看做2种解）。

大概说一下我的设计过程：
1. 尽可能的封装和模块化。面向对象的程序设计本来就不长于高性能计算，而在于抽象之后简化复杂的物理世界。这样以完全用程序化的思维考虑问题，在开发的同时能脱离现实场景，不把人脑的解答代入程序中，以期望针对特定要求的解答也能具备一定的通用性。
出于这个目的，我没有用精简的代码和使用数组一类的实现，在算法上也放弃了时间和空间复杂度较低的算法，而采用适用范围和性能更稳定的全排列算法。

2. 设计先于开发，编码的同时写注释。
用在画uml图上的时间大概和编码的时间一样长，写注释的时间差不多是半个编码的时间。（全排列算法类除外，这个是直接从算法书上抄的）

3. 既然是练习题，尽可能实践面向对象的五大原则：单一职责；对扩展开放、对修改封闭；Liskov替换原则；依赖倒置；接口隔离。
所以针对3个功能点，我设计了2个接口(Judging、GroupingElement)和1个抽象类(BaseElement)。所有的实现都尽量围绕这三者完成而不涉及具体实现，除非是有针对性的实现方法（比如分组实现类里的小队分组和队员分组方法）。

就我自己看来预留下的扩展点：
1. 基于model。
可以增加队伍的复杂性。除了可以任意增加小队和队员数量，还能增加其他成员类型。
比如引入“地区赛/总决赛”模式，只需要为小队增加一个“国家”属性，再继承评判接口实现一个“国家”属性的评判实现类。也可以增加一个“国家队”对象，聚合“小队”对象，再增加一个继承分组接口的国家分组实现类，实现为国家分组。
比如引入“性别”，只需要为“队员”增加一个性别属性，再继承评判接口，实现一个性别评判实现类。

2. 基于grouping
可以任意增加分组的实现。
比如题目是求全部可能的赛程，增加一个随机算法就能实现随机安排赛程。
比如“循环赛”，只用修改抽象分组类就能实现。

3. 基于judging
可以任意增加排除算法。
比如排除条件不再是一票否决，而是赛程允许容错指定次数的违背条件分组。
比如增加性别，实现男单、女单、混合单打。也能扩展出“双打”，group对象扩展一下就行。

更复杂的场景：
比如单人竞技常见的“擂台赛”(胜者不下场)、主将赛（最后一人能参赛两次的主将赛），
例如世界杯采用的“复合赛”（地区赛循环赛->分组循环赛->淘汰赛）
电子竞技常见的“胜败组”（循环赛->胜组循环赛and败组循环赛->复活赛->四强淘汰赛）。

这些场景最多就是重写grouping、judging两个包的一个到四个实现类，扩展model里对象的属性、或者增加新对象。

总之就是把设计做灵活点，编码量大一些。然后简化扩展的难度，提高程序的弹性，让新的修改尽量不用重新设计。 --------------------编程问答--------------------

引用 69 楼 HinanaiTenshi 的回复:

好像不能直接上传代码包啊，看来只能一个一个类帖上来了。

兄弟真行，哥们先看会儿再评论。。。 --------------------编程问答--------------------

引用 73 楼 u013220807 的回复:

忘记说了。还有个test包，里面灌入了题目要求的条件，用来执行取得符合题意的解。因为题目没有明确说明，我偷懒按照出场做了区分（也就是说“甲vs乙”和“乙vs甲”被看做2种解）。

大概说一下我的设计过程：
1. 尽可能的封装和模块化。面向对象的程序设计本来就不长于高性能计算，而在于抽象之后简化复杂的物理世界。这样以完全用程序化的思维考虑问题，在开发的同时能脱离现实场景，不把人脑的解答代入程序中，以期望针对特定要求的解答也能具备一定的通用性。
出于这个目的，我没有用精简的代码和使用数组一类的实现，在算法上也放弃了时间和空间复杂度较低的算法，而采用适用范围和性能更稳定的全排列算法。

2. 设计先于开发，编码的同时写注释。
用在画uml图上的时间大概和编码的时间一样长，写注释的时间差不多是半个编码的时间。（全排列算法类除外，这个是直接从算法书上抄的）

3. 既然是练习题，尽可能实践面向对象的五大原则：单一职责；对扩展开放、对修改封闭；Liskov替换原则；依赖倒置；接口隔离。
所以针对3个功能点，我设计了2个接口(Judging、GroupingElement)和1个抽象类(BaseElement)。所有的实现都尽量围绕这三者完成而不涉及具体实现，除非是有针对性的实现方法（比如分组实现类里的小队分组和队员分组方法）。

就我自己看来预留下的扩展点：
1. 基于model。
可以增加队伍的复杂性。除了可以任意增加小队和队员数量，还能增加其他成员类型。
比如引入“地区赛/总决赛”模式，只需要为小队增加一个“国家”属性，再继承评判接口实现一个“国家”属性的评判实现类。也可以增加一个“国家队”对象，聚合“小队”对象，再增加一个继承分组接口的国家分组实现类，实现为国家分组。
比如引入“性别”，只需要为“队员”增加一个性别属性，再继承评判接口，实现一个性别评判实现类。

2. 基于grouping
可以任意增加分组的实现。
比如题目是求全部可能的赛程，增加一个随机算法就能实现随机安排赛程。
比如“循环赛”，只用修改抽象分组类就能实现。

3. 基于judging
可以任意增加排除算法。
比如排除条件不再是一票否决，而是赛程允许容错指定次数的违背条件分组。
比如增加性别，实现男单、女单、混合单打。也能扩展出“双打”，group对象扩展一下就行。

更复杂的场景：
比如单人竞技常见的“擂台赛”(胜者不下场)、主将赛（最后一人能参赛两次的主将赛），
例如世界杯采用的“复合赛”（地区赛循环赛->分组循环赛->淘汰赛）
电子竞技常见的“胜败组”（循环赛->胜组循环赛and败组循环赛->复活赛->四强淘汰赛）。

这些场景最多就是重写grouping、judging两个包的一个到四个实现类，扩展model里对象的属性、或者增加新对象。

总之就是把设计做灵活点，编码量大一些。然后简化扩展的难度，提高程序的弹性，让新的修改尽量不用重新设计。

你为何这么易做图！ --------------------编程问答--------------------

引用 69 楼 HinanaiTenshi 的回复:

好像不能直接上传代码包啊，看来只能一个一个类帖上来了。

不说别的，你的面向对象的思想，建模工具的使用，以及功能可扩展性的预见，很值得我学习。
此外还有注释，它是体现程序员编码过程中的思维过程，是代码可用性的一个要素，这也是值得看重的地方。

这边也大致看了下各个类，对于算法上面，建议在全排列过程中，考虑某一对选手确定后，对其他队员选择对手的影响，会简化一些不必要的排列。
还有编码上的一些小细节，可以注意改良下，比如一个类的定义，先写成员属性，再写构造方法，最后写其它成员方法。
最后提醒一下：练习归练习，如果工作中碰到类似简单的业务类问题，建议不要过于发散。
当然，如果从事平台、组件开发工作，这种发散思维难能可贵。

非常感谢兄台的分享！
--------------------编程问答--------------------    等下来细看 --------------------编程问答-------------------- 闲来无事 ，搞了一下 。

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;



public class MyText {

	private List<String> aTeam = new ArrayList<String>();//第一支队伍

	private List<String> bTeam = new ArrayList<String>();//第二支队伍

	private List<MyRule> rule = new ArrayList<MyRule>();//对手规则 集合

	/**

	 * @param aTeam

	 * @param bTeam

	 * @param rule :如果没有规则传null

	 * 

	 */

	public MyText(List<String> aTeam, List<String> bTeam, List<MyRule> rule) {

		this.aTeam = aTeam;

		this.bTeam = bTeam;

		this.rule = rule;

	}

	public MyRule getMyRule(String play, List<MyRule> rule) {

		if (rule == null||rule.size() == 0)

			return null;

		for (MyRule m : rule) {

			if (m.getPlayer().equals(play))

				return m;

		}

		return null;

	}

	/**

	 * @return

	 * 根据规则取得每个人所有对手的对手组合

	 * 格式 当前人名字：对手名字

	 */

	public List<Opponent> getGroupMap() {

		List<Opponent> ls = new ArrayList<Opponent>();

		MyRule mr;

		for (String s : aTeam) {

			mr = getMyRule(s, rule);

			Opponent lf = new Opponent();

			if (mr == null) {

				for (String s2 : bTeam) {

					lf.getOpponList().add(s + ":" + s2);

				}

			} else {

				if (mr.getYesplayer()!=null&&mr.getYesplayer().size() > 0) {

					for (String m : mr.getYesplayer()) {

						lf.getOpponList().add(s + ":" + m);

					}

				} else if (mr.getNoplayer()!=null&&mr.getNoplayer().size() > 0) {

					for (String s3 : bTeam) {

						if (!mr.getNoplayer().contains(s3))

							lf.getOpponList().add(s + ":" + s3);

					}

				}

			}

			ls.add(lf);

		}

		Collections.sort(ls, new Opponent()); 

		//这里用到一个排序，主要把组合数目最少的人，放在集合的前边，防止他的对手被别人抢了.

		return ls;

	}

	/**

	 * @param s

	 * @param ls

	 * 移除特定对手的组合。

	 */

	public void removeOpton(String s, List<Opponent> ls) {

		String end=s.split(":")[1];

		for (Opponent op : ls) {

			String rem=null;

			for(String sp:op.getOpponList()){

				if(end.equals(sp.split(":")[1]))

					rem=sp;

			}

			if(rem!=null)

			op.getOpponList().remove(rem);



		}

	}

	/**

	 * @param ls

	 * @return

	 * 获取了每个人的对手组合拿到了，这个方法就是

	 * 开始组织比赛名单了。

	 */

	public List<String> getPant(List<Opponent> ls) {

		List<String> lo = new ArrayList<String>();

		for (Opponent op : ls) {

			lo.add(op.getOpponList().get(0));

			//从最少的组合数的开始，只取第一个匹配，这个对手被占用后，这把其他人的组合中和这个对手有关的组合去掉。

			removeOpton(op.getOpponList().get(0), ls);



		}

		return lo;



	}

	/**

	 * @return

	 * 符合规则的情况下，随机的取得一组比赛名单

	 * 可能会有多中组合的名单

	 */

	public List<String> getPanel() {

		if (aTeam.size() == 0 || bTeam.size() == 0)

			return null;

		List<String> panel = new ArrayList<String>();

			panel = getPant(getGroupMap());

			return panel;

	}

//还是看主方法吧 

	public static void main(String[] args) {

		List<String> a=new ArrayList<String>();//定义比赛小队A

		List<String> b=new ArrayList<String>();//定义比赛小队B

		//添加队员，同队的不要重名，俩对人员数相同即可

		a.add("张三");

		a.add("张");

		a.add("三");

		a.add("张小三");

		a.add("小三");

		a.add("张小");

		

		b.add("李四");

		b.add("李");

		b.add("四");

		b.add("李小四");

		b.add("小四");

		b.add("李小");

		

		//下边是添加规则

		List<MyRule> rulelist=new ArrayList<MyRule>();//定义规则集合

		//规则集合可以有多个 

		List<String> y=new ArrayList<String>();//规则1

		List<String> n=new ArrayList<String>();//规则2

		//规则人员添加

		y.add("李四");

		y.add("四");

		

		n.add("四");

		n.add("李小四");

		

		//下边就是把某个规则，添加到某个队员

		//这个一个队员只能用一个规则 ，写多个也会随机的取到一个规则，没有做合并。

		//定义规则不要定义成最后 俩个人只能和同一个人比赛。

		

		MyRule rule=new MyRule("张三",n,null);//这个是定义 张三 不能同“李四”和“四”比赛

		MyRule rule1=new MyRule("张小三",null,y);//这个是定义 张小三 只能同 “四”，"李小四" 比赛。

		//把规则添加到规则集合。

		rulelist.add(rule);

		rulelist.add(rule1);

		

		MyText t=new MyText(a,b,rulelist);

		List<String> df=t.getPanel();

		for(String s:df){

			System.out.println(s);

			

		}

		

	}



}

import java.util.ArrayList;

import java.util.List;



/**

 * @author Administrator

 *  定义规则：

 *  比如某个人，不想和谁成为对手，把这些人添加到 Noplayer集合

 *  比如某个人，只想和谁成为对手，把这些人添加到 Yesplayer集合

 *  player：是定义当前人的名字。

 *  

 */

public class MyRule {



	private String player;

	private List<String> Noplayer = new ArrayList<String>();

	private List<String> Yesplayer = new ArrayList<String>();



	public MyRule() {

	}



	/**

	 * @param player

	 * @param Noplayer

	 * @param Yesplayer

	 */

	public MyRule(String player, List<String> Noplayer, List<String> Yesplayer) {

		this.Noplayer = Noplayer;

		this.player = player;

		this.Yesplayer = Yesplayer;

	}



	public String getPlayer() {

		return player;

	}



	@Override

	public boolean equals(Object o) {

		if (this == null) {

			return true;

		} else if (o == null) {

			if (this.player == null)

				return true;

			else if (this.Noplayer.size() == 0 && this.Yesplayer.size() == 0) {

				return true;

			}

		}



		return true;



	}



	public void setPlayer(String player) {

		this.player = player;

	}



	public List<String> getNoplayer() {

		return Noplayer;

	}



	public void setNoplayer(List<String> noplayer) {

		Noplayer = noplayer;

	}



	public List<String> getYesplayer() {

		return Yesplayer;

	}



	public void setYesplayer(List<String> yesplayer) {

		Yesplayer = yesplayer;

	}



}

import java.util.ArrayList;

import java.util.Comparator;

import java.util.List;



/**

 * @author Administrator

 * 主要用于保存每个参赛人员，所有对手组合。

 * 实现排序接口，方便从最小组合开始选取一组名单。

 *

 */

public class Opponent implements Comparator<Opponent> {

	

	private List<String> opponList=new ArrayList<String>();



	public int compare(Opponent o1, Opponent o2) {

		

		return o1.getOpponList().size()-o2.getOpponList().size();

	}



	public List<String> getOpponList() {

		return opponList;

	}



	public void setOpponList(List<String> opponList) {

		this.opponList = opponList;

	}



}

--------------------编程问答--------------------

引用 14 楼 feixuyue 的回复:

跟数独类似，设一个2维数组，数组值只能是0,1，最后保证每行每列只有一个1.

靠谱。 --------------------编程问答-------------------- 题中说a不和x比，那a肯定和y,z中的一个比了，题中又说c不和x,z比那c肯定和y比了，这样a只能和z比了，剩下的b只能和x比了。 --------------------编程问答--------------------

Quote: 引用 78 楼 u012463264 的回复:

闲来无事 ，搞了一下 。

Quote:

又看到一个注释详细且抽象细致的，很给力，中国好猿猿~

看了下，似乎你扩散了下问题，挺好的。另外算法思想是先找匹配条件最少的，然后任取一个结果，并且将取得的对手从其他人对手列表中去掉，这个思路最终会得到一个解。如果有多个解的话，会漏掉其它解。顶一个~ --------------------编程问答--------------------

引用 78 楼 u012463264 的回复:

闲来无事 ，搞了一下 。

又看到一个注释详细且抽象细致的，很给力，中国好猿猿~

看了下，似乎你扩散了下问题，挺好的。另外算法思想是先找匹配条件最少的，然后任取一个结果，并且将取得的对手从其他人对手列表中去掉，这个思路最终会得到一个解。如果有多个解的话，会漏掉其它解。顶一个~ --------------------编程问答--------------------

引用 80 楼 a289121428 的回复:

题中说a不和x比，那a肯定和y,z中的一个比了，题中又说c不和x,z比那c肯定和y比了，这样a只能和z比了，剩下的b只能和x比了。

恭喜你答对了~
但是如何代码实现你的思路捏？ --------------------编程问答-------------------- int【】【】 ac=new int 【3】【3】；
ac={0,1,1
   1,1,1
   0,1,0}
int i,j,k=0,m=0;
for(int n=0;n<3;n++)
for(i=0;i<3;i++)
  for(j=0;j<3;j++)
   if(ac[i][j]=0)
   {
    k++;
    if(k=2)
    {
     if(j=1)
     {for(int p=0;p<3;p++)
      ac[p][2]=0;
      ac[i][2]=1;
     }
    else
     {for(int p=0;p<3;p++)
      ca[p][1]=0;
      ca[i][1]=1;
     }
    m++;
   }
  }
 {}{}{}{}{}{}{}{}{}找出对手矩阵了吧{}{}{}{}{}{}{}
--------------------编程问答-------------------- 学习. --------------------编程问答--------------------

引用 84 楼 was22491686 的回复:

int【】【】 ac=new int 【3】【3】；
ac={0,1,1
   1,1,1
   0,1,0}
int i,j,k=0,m=0;
for(int n=0;n<3;n++)
for(i=0;i<3;i++)
  for(j=0;j<3;j++)
   if(ac[i][j]=0)
   {
    k++;
    if(k=2)
    {
     if(j=1)
     {for(int p=0;p<3;p++)
      ac[p][2]=0;
      ac[i][2]=1;
     }
    else
     {for(int p=0;p<3;p++)
      ca[p][1]=0;
      ca[i][1]=1;
     }
    m++;
   }
  }
 {}{}{}{}{}{}{}{}{}找出对手矩阵了吧{}{}{}{}{}{}{}

if(j=1)
if(k=2)
还有ca[][]
这，真心不好猜。。。 --------------------编程问答-------------------- 算法不太好，想了半天写了一个测试。

package demo;

import java.util.HashMap;

import java.util.LinkedHashMap;

import java.util.Map;

import org.junit.Test;



public class SortTeam {

	@Test

	public void t(){

		/**

		 * a说他不和x比，c说他不和x,z比

		 * 条件也为二维数组，

		 * 		A	B	C

		 * 	X	-1	U	-1

		 * 	Y	

		 * 	Z			-1

		 * 

		 * 

		 * 我的思路是这样的，将条件存放为一个二维数组，根据条件来说是有一列是可以直接获得一条结果的，比如

		 * 例题中的X-B，这样的话可以将已经唯一对应的列和行去除。依次遍历，直到所有的列全部被去除

		 * 

		 * 不过局限性比较大

		 */

		

		/**

		 * 这是已知条件

		 * a说他不和x比，c说他不和x,z比

		 * 条件也为二维数组，-1为已确定不比，0为未确定

		 * 		A	B	C

		 * 	X	-1	0	-1

		 * 	Y	

		 * 	Z			-1

		 */

		int condition[][] = {

				{-1,0,-1},

				{0,	0, 0},

				{0,	0,-1}

		};

		//下标和队名对应MAP

		Map<Integer,String> bTeam = new HashMap();

		bTeam.put(0, "A");

		bTeam.put(1, "B");

		bTeam.put(2, "C");

		Map<Integer,String> aTeam = new HashMap();

		aTeam.put(0, "X");

		aTeam.put(1, "Y");

		aTeam.put(2, "Z");

		Map<Integer,Integer> m = sortT(condition);

		for(Map.Entry<Integer,Integer> entry : m.entrySet()){

			System.out.println(aTeam.get(entry.getKey())+" vs "+bTeam.get(entry.getValue()));

		}

	}

	

	//排列方法

	public Map<Integer,Integer> sortT(int condition[][]){

		Map<Integer,Integer> result = new LinkedHashMap();	//存放结果集

		int i = 0;

		for(;i<condition.length; i++){

			if(condition[i][0]==2){	//证明第i行已排除，不查找

				continue;

			}

			int index = ismatch(condition[i]);//是否满足条件

			if(index!=-1){

				result.put(i, index);	//将二满足条件坐标放入结果集

				condition[i][0] = 2;

				i = 0;			//i重置为0

				for(int j=0; j<condition.length; j++){	//将已排除的列全置为-1

					if(condition[j][0]==2){	//已排除行不操作

						continue;

					}

					condition[j][index] = -1;

				}

			}

		}

		return result;

	}

	//是否可排除，只要当前行有且只有一个元素不为-1，则认为已对应

	public int ismatch(int arr[]){

		int f = 0;

		int index = -1;

		for(int i=0; i<arr.length; i++){

			if(f<2 && arr[i]==-1){

				f++;

			}else{

				index =	i;

			}

		}

		if(f==arr.length-1){

			return index;

		}

		return -1;

	}

}

--------------------编程问答--------------------

引用 87 楼 u011687117 的回复:

condition[j][index] = -1;
这个是亮点~

i = 0; //i重置为0
这个操作更厉害，使得节省了原本要嵌套的一层循环。这样算来，你的算法复杂度只有O(n^2)，厉害~

（建议改为i=-1，否则如果第0行和第1行调换位置，会有bug）

还有一个疑似瑕疵的地方：condition[i][0]==2这个判断的处理，2应该当做一个标志了，这个似乎破坏了condition的原始含义。建议不做这个判断，或者扩展condition[3][3]为condition[3][4]，多处的一列（不妨为最后一列）专门用户放置标识2

总之，你的算法，应该算是LS已出现的，复杂度最低的算法了！ --------------------编程问答-------------------- a说他不和x比，c说他不和x,z比，其实就是 a可能和y，z比，c可能和y比。
那我直接考虑用{y,z},{x,y,z},{z},即可，我是上过几天培训班，一年经验不到的菜鸟，代码不好请勿嘲笑。

            //测试1

            Dictionary<string, List<string>> groups = new Dictionary<string, List<string>>();

            groups.Add("a", new List<string> { "x", "z" });   //a对手可能是 x,z

            groups.Add("b", new List<string> { "x", "y", "z" });  //b对手可能是 x,y,z

            groups.Add("c", new List<string> { "y" });         //c 对手可能是y

            PingPongGame p = new PingPongGame { Groups = groups };

            List<Dictionary<string, string>> newGroup = p.Get();

            for (int i = 0; i < newGroup.Count; i++)

            {

                Response.Write("组合:" + (i + 1) + "<br/>");

                foreach (var kv in newGroup[i])

                {

                    Response.Write(kv.Key + "=>" + kv.Value + "<br/>");

                }

            }

            //组合:1

            //a=>z

            //b=>x

            //c=>y

            //组合:2

            //a=>x

            //b=>z

            //c=>y

            //测试1

            Dictionary<string, List<string>> groups2 = new Dictionary<string, List<string>>();

            groups2.Add("a", new List<string> { "y", "z" });

            groups2.Add("b", new List<string> { "x", "y", "z" });

            groups2.Add("c", new List<string> { "y" });

            PingPongGame p2 = new PingPongGame { Groups = groups2 };

            List<Dictionary<string, string>> newGroup2 = p2.Get();

            for (int i = 0; i < newGroup2.Count; i++)

            {

                Response.Write("组合:" + (i + 1) + "<br/>");

                foreach (var kv in newGroup[i])

                {

                    Response.Write(kv.Key + "=>" + kv.Value + "<br/>");

                }

            }

            //组合:1

            //a=>z

            //b=>x

            //c=>y

public class PingPongGame

    {

        public Dictionary<string, List<string>> Groups { get; set; }

        public List<Dictionary<string, string>> Get()

        {

            // a{x,y},b{x,y,z},z{y}

            List<Dictionary<string, string>> matchingGroups = new List<Dictionary<string, string>>();

            foreach (var member in this.Groups)

            {

                matchingGroups = this.Get(matchingGroups, member);

                if (matchingGroups.Count == 0)

                    break;

            }

            return matchingGroups;

        }



        //oldMatchGroups和keyValuePair进行组合，返回合理的组合

        private List<Dictionary<string, string>> Get(List<Dictionary<string, string>> oldMatchGroups, KeyValuePair<string, List<string>> keyValuePair)

        {

            List<Dictionary<string, string>> matchGroups = new List<Dictionary<string, string>>();

            foreach (var v in keyValuePair.Value)

            {

                if (oldMatchGroups.Count == 0)  //首轮遍历,所有的元素皆为合理的组合

                {

                    Dictionary<string, string> dic = new Dictionary<string, string>();

                    dic.Add(keyValuePair.Key, v);

                    matchGroups.Add(dic);

                }

                else

                {

                    foreach (var matchGroup in oldMatchGroups)   //遍历上轮合理组合

                    {

                        if (!matchGroup.ContainsValue(v)) //加入当前组合不包含的元素

                        {

                            Dictionary<string, string> dic = matchGroup.Select(a => a).ToDictionary(a => a.Key, a => a.Value);

                            dic.Add(keyValuePair.Key, v);

                            matchGroups.Add(dic);

                        }

                    }

                }

            }

            return matchGroups;

        }

    }

--------------------编程问答--------------------

引用 89 楼 l易做图s1212 的回复:

a说他不和x比，c说他不和x,z比，其实就是 a可能和y，z比，c可能和y比。
那我直接考虑用{y,z},{x,y,z},{z},即可，我是上过几天培训班，一年经验不到的菜鸟，代码不好请勿嘲笑。

互相学习罢了~

继python版本之后，又来了C#版~

不过你的结果似乎有两个？实际上结果，在本题中应该是唯一的。
--------------------编程问答-------------------- 测试1 ，和测试2。 第一个是{x,z},{x,y,z}{z},第二个是{y,z}{x,y,z},{z}，题目的是第二种情况。 
只是测试而已。有时候不会只有一个解的。。 --------------------编程问答--------------------

引用 90 楼 oh_Maxy 的回复:

Quote: 引用 89 楼 l易做图s1212 的回复:

a说他不和x比，c说他不和x,z比，其实就是 a可能和y，z比，c可能和y比。
那我直接考虑用{y,z},{x,y,z},{z},即可，我是上过几天培训班，一年经验不到的菜鸟，代码不好请勿嘲笑。

互相学习罢了~

继python版本之后，又来了C#版~

不过你的结果似乎有两个？实际上结果，在本题中应该是唯一的。

--------------------编程问答-------------------- 好, --------------------编程问答--------------------

引用 91 楼 l易做图s1212 的回复:

测试1 ，和测试2。 第一个是{x,z},{x,y,z}{z},第二个是{y,z}{x,y,z},{z}，题目的是第二种情况。 
只是测试而已。有时候不会只有一个解的。。

嗯看来我误解了。

再问下：比如c已经确认和z对阵了，那么对于a、b可能的对手集是否有影响，需要将z从中剔除？感觉这样会简化操作的~ --------------------编程问答-------------------- 不是很懂，有点晕 --------------------编程问答-------------------- 除 --------------------编程问答-------------------- 原来是穷举，的确比lz的短

------------------------------------------------------AutoCSDN签名档------------------------------------------------------ --------------------编程问答--------------------

引用 97 楼 hankcs 的回复:

原来是穷举，的确比lz的短

------------------------------------------------------AutoCSDN签名档------------------------------------------------------ --------------------编程问答--------------------

String[] arr1 = {"a","b","c"};

		String[] arr2 = {"x","y","z"};



		Map<String,List<String>> map = new LinkedHashMap<String,List<String>>();

		

		for(int i = 0; i < arr1.length; i ++) {

			for(int k = 0; k < arr2.length; k ++) {

		      

			   if("a".equals(arr1[i]) && "x".equals(arr2[k])){

				   continue;

			   }

			   else if("c".equals(arr1[i]) && ("x".equals(arr2[k]) || "z".equals(arr2[k]))) {

				   continue;

			   }

			   else {

				   if(map.containsKey(arr1[i])) {

					   map.get(arr1[i]).add(arr2[k]);

				   }

				   else {

					  List<String> list = new ArrayList<String>();

					  list.add(arr2[k]);

					  map.put(arr1[i], list);

				   }

			   }

		   }

		}

		

		for(Entry<String, List<String>> entry1 : map.entrySet()) {

			List<String> value1 = entry1.getValue();

			for(Entry<String, List<String>> entry2 : map.entrySet()) {

				List<String> value2 = entry2.getValue();

				

				if(value1 == value2) {

					continue;

				}

				else if(value1.size() == 1) {

					map.put(entry1.getKey(), value1);

					break;

				}

				else if(value1.size() >= value2.size()){

					value1.removeAll(value2);

				}

				else if(value2.size() < value2.size()) {

					value2.removeAll(value1);

					map.put(entry2.getKey(), value2);

				}

			}

			

			map.put(entry1.getKey(), value1);

			System.out.println(entry1.getKey() + value1);

		}

好像很麻烦的样子 --------------------编程问答--------------------

引用 99 楼 u013276062 的回复:

String[] arr1 = {"a","b","c"};

		String[] arr2 = {"x","y","z"};



		Map<String,List<String>> map = new LinkedHashMap<String,List<String>>();

		

		for(int i = 0; i < arr1.length; i ++) {

			for(int k = 0; k < arr2.length; k ++) {

		      

			   if("a".equals(arr1[i]) && "x".equals(arr2[k])){

				   continue;

			   }

			   else if("c".equals(arr1[i]) && ("x".equals(arr2[k]) || "z".equals(arr2[k]))) {

				   continue;

			   }

			   else {

				   if(map.containsKey(arr1[i])) {

					   map.get(arr1[i]).add(arr2[k]);

				   }

				   else {

					  List<String> list = new ArrayList<String>();

					  list.add(arr2[k]);

					  map.put(arr1[i], list);

				   }

			   }

		   }

		}

		

		for(Entry<String, List<String>> entry1 : map.entrySet()) {

			List<String> value1 = entry1.getValue();

			for(Entry<String, List<String>> entry2 : map.entrySet()) {

				List<String> value2 = entry2.getValue();

				

				if(value1 == value2) {

					continue;

				}

				else if(value1.size() == 1) {

					map.put(entry1.getKey(), value1);

					break;

				}

				else if(value1.size() >= value2.size()){

					value1.removeAll(value2);

				}

				else if(value2.size() < value2.size()) {

					value2.removeAll(value1);

					map.put(entry2.getKey(), value2);

				}

			}

			

			map.put(entry1.getKey(), value1);

			System.out.println(entry1.getKey() + value1);

		}

好像很麻烦的样子

兄弟这样的算法，不够灵活，都是按条件写死了的。如果改变了条件，对代码影响很大。建议参考下LS们的，看看有什么差别。

补充：Java ,  Java EE