java - 分组对象的算法

我有以下类(class):

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<>>，以使内部列表是所有具有至少1个公共(public)玩家的体育项目(在这里适用Transitive属性)。在上面的示例中，输出应为

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

对解决此和/或伪代码有什么建议吗？

最佳答案

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

创建一个图(无向)，其中人是节点，到目前为止没有边缘。

我将参加体育运动，并且如果每项运动我都参加相同的运动，我将在人与人之间取得优势(例如，在处理运动1时，它将在Sam和Dylan之间建立优势；在处理运动3时，将在Dylan之间实现优势。和卡特)

作为最后一步，我将获取最终图形的组成部分(在您的示例中为Sam-Dylan-Carter-Frank，Kane-Michael，Tyler-John)，并“对他们应用体育运动”-这意味着对于每个男孩/女孩组件中，我会将他/她所做的所有运动都添加到“内部”列表中(我希望Set可以使每个运动都存在一次)。

因此，图形将以这种方式增长:

处理足球: Sam-Dylan

处理篮球:Sam-Dylan，泰勒-约翰

处理棒球:Sam-Dylan- 卡特，Tyler-John

处理曲棍球:Sam-Dylan-Carter，Tyler-John，凯恩·迈克尔

处理足球:Sam-Dylan-Carter- Frank ，Tyler-John，Kane-Michael

和“应用体育”:

Sam(足球)，Dylan(足球，棒球)，Carter(棒球，足球)，Frank(足球)=>(橄榄球，棒球，足球)

泰勒(篮球)，约翰(篮球)=>(篮球)

凯恩(曲棍球)，迈克尔(曲棍球)=>(曲棍球)

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

编辑:
您可以选择优化算法，以使每个组件都记住与之相关的运动。换句话说，创建边时，将运动添加到组件的运动集合中。然后，将不再需要“应用体育”步骤。一个简单的规则是，当两个组件连接在一起时，您将在添加新运动之前合并运动集合。然后该算法将执行:

处理足球: Sam-Dylan(橄榄球)

处理篮球:Sam-Dylan(橄榄球)，泰勒-约翰(篮球)

处理棒球:Sam-Dylan- 卡特(橄榄球，棒球)，Tyler-John(篮球)

处理曲棍球:Sam-Dylan-Carter(橄榄球，棒球)，Tyler-John(篮球)， Kane-Michael(曲棍球)

处理足球:Sam-Dylan-Carter- Frank (足球，棒球，足球)，Tyler-John(篮球)，Kane-Michael(曲棍球)

请注意，没有必要使用图表。您仍然可以使用简单的集合，但是图形似乎是最干净的方法，也是算法的最佳选择。它还以自然的方式对数据进行建模，因此还具有进一步的可扩展性-例如，您可以进一步找出Sam为何与Carter在一起(因为他们的共同 friend Dylan与他们一起从事不同的运动)。