用于分组对象的算法

Question

我有以下课程:

class Sport {
    private String sportsName;
    private List<People> peopleWhoPlayThisSport;
    //...
}

class People {
    private String name;
    private long uniqueId;
   // ...
}

我的输入是运动对象列表,为简单起见,请考虑以下示例:

sport1 - Football,   <Sam, Dylan>
sport2 - Basketball, <Tyler, John>
sport3 - Baseball,   <Carter, Dylan>
sport4 - Hockey,     <Kane, Michael>
sport5 - Soccer,     <Carter, Frank>

我必须创建一个List<List<>>,这样内部列表就是所有具有至少一个普通玩家的体育项目(此处适用传递属性).在上面的例子中,输出应该是,

<<sport1,sport3,sport5> , <sport2> , <sport4>>

有关解决此问题和/或伪代码的任何建议吗？

Answer 1

对我来说听起来像图形问题.我要做的是:

1. 创建一个图(无向),其中人是节点,到目前为止没有边
2. 我会经历体育运动,对于每项运动,如果他们玩同样的运动,我会在人与人之间做一个优势(例如,在处理运动1时,它会在Sam和Dylan之间产生优势,在处理运动3时,它会在Dylan和卡特)
3. 作为最后一步,我将采用最终图形的组成部分(在您的示例中,Sam-Dylan-Carter-Frank,Kane-Michael,Tyler-John)和"将运动应用于他们" - 这意味着对于每个男孩/女孩组件,我会将他/她所做的所有运动添加到"内部"列表中(我更喜欢Set,所以每项运动都有一次).

所以图表会以这种方式增长:

1. 处理足球:Sam-Dylan
2. 加工篮球:Sam-Dylan,Tyler-John
3. 加工棒球:Sam-Dylan- Carter,Tyler-John
4. 处理曲棍球:Sam-Dylan-Carter,Tyler-John,Kane-Michael
5. 处理足球:Sam-Dylan-Carter- Frank,Tyler-John,Kane-Michael

和"运动":

1. 山姆(足球),迪伦(足球,棒球),卡特(棒球,足球),弗兰克(足球)=>(足球,棒球,足球)
2. 泰勒(篮球),约翰(篮球)=>(篮球)
3. 凯恩(曲棍球),迈克尔(曲棍球)=>(曲棍球)

==>(足球,棒球,足球),(篮球),(曲棍球)

编辑: 您可以选择优化每个组件的算法,您将记住与之相关的运动.换句话说,在创建边缘时,您将为该组件的运动集合添加运动.然后将不再需要"应用运动"步骤.一个简单的规则,当两个组件连接时,您将在添加新运动之前结合运动系列.然后算法会:

1. 加工足球:Sam-Dylan(足球)
2. 加工篮球:Sam-Dylan(足球),Tyler-John(篮球)
3. 加工棒球:Sam-Dylan- Carter(足球,棒球),Tyler-John(篮球)
4. 处理曲棍球:Sam-Dylan-Carter(足球,棒球),Tyler-John(篮球),Kane-Michael(曲棍球)
5. 处理足球:Sam-Dylan-Carter- Frank(足球,棒球,足球),Tyler-John(篮球),Kane-Michael(曲棍球)

请注意,图表的使用不是必需的.您仍然可以使用简单的集合,但图表似乎是最干净的方法和算法最佳方式.它还允许进一步的可扩展性,因为它以自然的方式对数据进行建模 - 例如,您可以进一步找出Sam与Carter在一起的原因(因为他们的共同朋友Dylan与他们两人一起玩不同的运动).