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

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


【2013-12-20】
这边也给出一个之前的代码实现，欢迎指正，欢迎大家继续讨论~

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class PingpongGame {

    // 选手集
    private static final List<String>              teamA  = new ArrayList<String>();
    private static final List<String>              teamB  = new ArrayList<String>();

    // 结果集:teamA队员为key，teamB队员为value
    private static final Map<String, String>       result = new HashMap<String, String>();

    // 规则集：不允许集，teamA某个队员为key，不允许的对手名单列表为value
    private static final Map<String, List<String>> noMap  = new HashMap<String, List<String>>();

    // 规则集初始化
    static {
        // 队员初始化
        teamA.add("a");
        teamA.add("b");
        teamA.add("c");

        teamB.add("x");
        teamB.add("y");
        teamB.add("z");

        // a说他不和x比
        List<String> aNoList = new ArrayList<String>();
        aNoList.add("x");
        noMap.put("a", aNoList);

        // b的对手任意
        List<String> bNoList = new ArrayList<String>();
        noMap.put("b", bNoList);

        // c说他不和x,z比
        List<String> cNoList = new ArrayList<String>();
        cNoList.add("x");
        cNoList.add("z");
        noMap.put("c", cNoList);
    }

    public static void main(String[] args) {

        // 最终要得到的结果，是三队比赛场次的输出
        for (;;) {
            // 跳出循环的条件：形成三组对抗
            if (result.size() == teamA.size()) {
                break;
            }

            // 遍历A组学员
            for (String member : teamA) {
                // 若当前队员已经有对手，则跳过本次循环
                if (null != result.get(member)) {
                    continue;
                }

                // 判断当前成员的不可能对手集，若teamB去掉此集合后，仅剩下一个队员，则录入结果集
                checkNoListAnd(member, noMap.get(member));
            }
        } 
 

        // 打印结果
        for (Map.Entry<String, String> entry : result.entrySet()) {
            System.out.println("A组选手" + entry.getKey() + "的对手为B组选手" + entry.getValue());
        }
    }

    // 判断当前成员的不可能对手集，若teamB去掉此集合后，仅剩下一个队员，则录入结果集
    private static void checkNoListAnd(String member, List<String> noList) {
        // 不可能结果集为空，则不处理
        if (null == noList || 0 == noList.size()) {
            return;
        }

        // 若teamB去掉此集合后，仅剩下一个队员，则录入结果集
        List<String> teamBTmp = new ArrayList<String>(teamB);
        teamBTmp.removeAll(noList);
        if (1 == teamBTmp.size()) {
            result.put(member, teamBTmp.get(0));
            addMayBeList(teamBTmp);
        }
    }

    // 已被占用的teamB队员，加入到所有成员的不可能对手集中
    private static void addMayBeList(List<String> noBeList) {
        for (Map.Entry<String, List<String>> entry : noMap.entrySet()) {
            // 避免重复加入
            if (!entry.getValue().containsAll(noBeList)) {
                entry.getValue().addAll(noBeList);
            }
        }
    }
}

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

[解决办法]
怎么去写就不说，一般做这种题我有点偏激，喜欢往递归的方式去想
最开始学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貌似还得套循环吧，没细看。
[解决办法]
这就是一个排列组合的算法吧
[解决办法]
弱弱的问一句-------这样行么？？？？？？？？？？？、、


求轻拍,做了一个小时的.逻辑不好，算法也不好

package logic;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class Pinpang {

public static void main(String[] args) {
int size = 3;
Map<Character, List<Character>> map = new HashMap<Character, List<Character>>();
//List<Character> l1 = new ArrayList<>(1000);
//对l1初始化
List<Character> l1 = new ArrayList<>(size);
char a;
for (int i = 0 ; i < size ; i ++) {
a = (char) (i + 97);
List<Character> c = new LinkedList<>();
map.put(new Character(a), c);
l1.add(a);
}
//对l2初始化
List<Character> l2 = new ArrayList<>(size);
for (int i = 0 ; i < size ; i ++) {
l2.add((char) (i + 120));
}
for(int i = 0 ; i < size ; i ++) {
for(int j = 0 ; j < size ; j ++) {
if (checkCan(l1.get(i) , l2.get(j))){
map.get(l1.get(i)).add(l2.get(j));
}
}
}
Set<Entry<Character, List<Character>>> entry = map.entrySet();
Iterator<Entry<Character, List<Character>>> it = entry.iterator();
deal(it);
}
//塞选条件满足
static boolean checkCan(char a , char b) {
switch(a) {
case 'a' : return b != 'x';
case 'c' : return b != 'x' && b != 'z';
default : return true;
}
}
static void deal(Iterator<Entry<Character, List<Character>>> it) {
List<Entry<Character, List<Character>>> ll = new LinkedList<>();
List<Character> dd = new LinkedList<>();
boolean check = false;
while (it.hasNext()) {
char c;
Entry<Character, List<Character>> en = it.next(); 
List<Character> l = en.getValue();

if (l.size() == 1) {
check = true;
c = l.get(0);
dd.add(c);
System.out.println(en);
} else {
ll.add(en);
}
}
if (!check) {
System.out.println("无解！");
return;
}
if (ll.size() == 0) 
return ;
//删除处理
for (int i = 0 ; i < ll.size() ; i ++) {
for (int j = 0 ; j < dd.size() ; j ++) {
if (ll.get(i).getValue().contains(dd.get(j)))
ll.get(i).getValue().remove(dd.get(j));
}
}
//再来
Iterator<Entry<Character, List<Character>>> tt = ll.iterator();
deal(tt);
}
}

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

引用:

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

其实画图更好
[解决办法]
楼上给出思路的同志还是很不错的。
其实我觉得算法思路或者叫建模比较好想。难点是在如果把建模/思路用代码表示出来。
[解决办法]
能不能用面像对像的思想来看待呢？
[解决办法]
我首先想到的就是穷举，看了楼上各位牛人的想法，受益匪浅。膜拜~~
[解决办法]

引用:

Quote: 引用:

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

如何搞起？

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

这个想法有问题么，求指导。
[解决办法]
个人觉得这中类似问题用一个矩阵的可以解决
  x y z
a 1 0 0
b 0 0 0
c 1 0 1
放到矩阵中，他给定的条件放入矩阵，只要找每行（列）只有一个0的就可一匹配，然后删除此行（列），案后继续，知道删除所有。
觉得这个操作肯定有很多优化地方，随着数据增大可以用bitmap，假设如果是16位存，11111111 10111111 就可以不用循环行（列）次，直接使用数值大小判断有几位为零，可以增加效率。
仅供参考
[解决办法]
for使用太多确实容易出错的啊，但是这题貌似用for最直观
[解决办法]
暴力搜索版，其中可优化的部分很多，时间复杂度快要到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)

[解决办法]
完成了，大家看看怎么样，思路我附在代码里了，除了封装初始化数据意外，我的思路其实很简单。不知道我的思路是不是对提议理解有偏差，题目应该是每次都给出排除条件，如果这个没理解错，算法应该没问题。

public static void main(String[] args) {
List<String> team1 = new ArrayList<String>();//参赛选手
team1.add("a");
team1.add("b");
team1.add("c");
List<String> team2 = new ArrayList<String>();//参赛选手
team2.add("x");
team2.add("y");
team2.add("z");
List<String> case1 = new ArrayList<String>();//过滤条件
case1.add("a");//为了方便，我把谁说的话，放在数组第一位
case1.add("x");
List<String> case2 = new ArrayList<String>();//过滤条件
case2.add("c");
case2.add("x");
case2.add("z");
List<List<String>> caseList = new ArrayList<List<String>>();
caseList.add(case1);
caseList.add(case2);
int i=0;
/*
 *我的思路是根据条件过滤选手
 *一开始想用递归后来觉得麻烦就用循环了
 * 如果其中一个条件过滤掉只剩1个人，比如条件2
 * 那么就能确认2个队伍，唯一1个人的对阵
 * 这样，将这2个人从队伍里移除
 * 之后再循环其他条件，
 * 这个时候循环到条件1，它又满足了条件能唯一确定一个人 
 
 * 因为这个时候，2个队伍只剩2个人了
 * 最后当条件用完的时候，每个队伍应该只剩一个人
 * 就是最后的对阵
 */
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.removeAll(caseI);
team3.removeAll(caseI);
team2.removeAll(team3);
System.out.println("对阵情况:"+caseI.get(0)+"---"+team3.get(0));
caseList.remove(i);
i=0;
continue;
}
i++;
}
System.out.println("对阵情况:"+team1.get(0)+"---"+team2.get(0));
}

我大致看了下，好像跟大家的思路不太一样
[解决办法]
看了一下，想了一下。我的思路是把两队对手分别放到一个集合里，规约条件放到一个集合里(如a不和x比，就定义为a<>x),然后就拿两个集合组合和规约条件比较，然后按条件依次剔除对手集合。
[解决办法]

抽取一下题目的要求，有一个基本的功能点：
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 分组的辅助类，将任意比赛成员分组

[解决办法]
闲来无事 ，搞了一下 。


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;
}

}



[解决办法]
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++;
   }
  }
 {}{}{}{}{}{}{}{}{}找出对手矩阵了吧{}{}{}{}{}{}{}

[解决办法]
算法不太好，想了半天写了一个测试。

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比
 * 条件也为二维数组，
 * ABC
 * X-1U-1
 * Y
 * Z-1
 * 
 * 
 * 我的思路是这样的，将条件存放为一个二维数组，根据条件来说是有一列是可以直接获得一条结果的，比如
 * 例题中的X-B，这样的话可以将已经唯一对应的列和行去除。依次遍历，直到所有的列全部被去除
 * 
 * 不过局限性比较大
 */

/**
 * 这是已知条件
 * a说他不和x比，c说他不和x,z比
 * 条件也为二维数组，-1为已确定不比，0为未确定
 * ABC
 * X-10-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;
}
}



[解决办法]
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;
        }
    }


[解决办法]

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);
}


好像很麻烦的样子 

 

查看更多 下一篇