对对象进行分组的算法

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<>>，这样内部列表是所有至少有 1 个普通玩家的运动（Transitive 属性适用于此）。在上面的例子中，输出应该是，

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

关于解决此 and/or 伪代码的任何建议？

Answer 1

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

创建一个图（无向），其中人是节点，到目前为止没有边
我会研究运动，对于每项运动，如果人们参加相同的运动，我会在他们之间建立优势（例如，在处理运动 1 时，它会在 Sam 和 Dylan 之间产生优势，在处理运动 3 时，它会在迪伦和卡特之间做边缘）
作为最后一步，我将采用最终图表的组成部分（在您的示例中，Sam-Dylan-Carter-Frank、Kane-Michael、Tyler-John）和 "apply the sports to them" - 这意味着对于每个 boy/girl 在组件中，我会将所有运动 he/she 添加到 "inner" 列表中（我更喜欢 Set 所以每项运动都存在一次）。

所以图表会这样增长：

处理足球：Sam-Dylan
处理篮球：Sam-Dylan，Tyler-John
处理棒球：Sam-Dylan-Carter、Tyler-John
处理曲棍球：Sam-Dylan-Carter、Tyler-John、Kane-Michael
处理足球：Sam-Dylan-Carter-Frank、Tyler-John、Kane-Michael

和"applying sports"：

山姆（橄榄球）、迪伦（橄榄球、棒球）、卡特（棒球、足球）、弗兰克（足球）=>（橄榄球、棒球、足球）
泰勒（篮球），约翰（篮球）=>（篮球）
凯恩（曲棍球）、迈克尔（曲棍球）=>（曲棍球）

==>（橄榄球、棒球、英式足球）、（篮球）、（曲棍球）

编辑： 您可以选择优化每个组件的算法，您将记住与之相关的运动。换句话说，在创建边缘时，您将向组件的运动集合中添加一项运动。然后 "apply sports" 步骤将不再需要。一个简单的规则，当两个组件连接时，您将在添加新运动之前合并运动集合。然后算法会去：

正在处理足球：Sam-Dylan(Football)
处理篮球：Sam-Dylan（足球），Tyler-John（篮球）
处理棒球：Sam-Dylan-Carter（橄榄球，棒球），Tyler-John（篮球）
处理曲棍球：Sam-Dylan-Carter（足球，棒球），Tyler-John（篮球），Kane-Michael（曲棍球）
处理足球：Sam-Dylan-Carter-Frank（足球，棒球，足球），Tyler-John（篮球），凯恩-迈克尔（曲棍球）

请注意，图表的使用不是必需的。您仍然可以使用简单的集合，但图形似乎是最简洁的方法和算法最佳的方法。它还允许进一步的扩展，因为它以自然的方式对数据进行建模——例如，您可以进一步找出为什么 Sam 和 Carter 在一起（因为他们的共同朋友 Dylan 和他们一起玩不同的运动）。

Answer 2

Create HashMap<People, List<Sport>> pList
for each Sport s in sportList
   for each People p in peopleWhoPlayThisSport 
      if p present in pList,
          pList.get(p).add(s)      
      else,
          pList.put(p,s)

Iterate on pList 
    If list size of Sport Objects for a People > 1
        Add to Set of Sport Objects which have at least 1 common 


Create another Set from first sportList
Do a Set minus to get Sports without any common player

Answer 3

我使用与@Somabrata 所述类似的方法完成了这项工作。

Map<People, Set<Sport>> mapping = new HashMap<>();
for (Sport s : sports) {
    for (People p : s.getPeopleWhoPlayThisSport()) {
        Set<Sport> sportByPeople = mapping.get(p);
        if (sportByPeople == null) {
            sportByPeople = new HashSet<>();
            mapping.put(p, sportByPeople);
        }
        sportByPeople.add(s);
    }
}

List<Set<Sport>> groupings = new ArrayList<>();
outer: for (Set<Sport> sportSet : mapping.values()) {
    for (Set<Sport> group : groupings) {
        for (Sport s : sportSet) {
            if (group.contains(s)) {
                group.addAll(sportSet);
                continue outer;
            }
        }
    }
    groupings.add(sportSet);
}
System.out.println(groupings);

Answer 4

我为你实现了代码。如果你看到方法 "group"，你就会明白。所以这些将不需要伪代码。输出将是：

[[Football, Baseball, Soccer], [Basketball], [Hockey]]

我还添加了一个新条目：

sport6 - Handball, < Tyler, Reza >

为多个常见列表测试算法。输出将是：

[[Football, Baseball, Soccer], [Basketball, Handball], [Hockey]]

代码如下：

public class GroupObjects {
int uniqueIdCounter = 1;

People p1 = new People("Sam",uniqueIdCounter++);
People p2 = new People("Dylan",uniqueIdCounter++);
People p3 = new People("Tyler",uniqueIdCounter++);
People p4 = new People("John",uniqueIdCounter++);
People p5 = new People("Carter",uniqueIdCounter++);
People p6 = new People("Kane",uniqueIdCounter++);
People p7 = new People("Michael",uniqueIdCounter++);
People p8 = new People("Frank",uniqueIdCounter++);
People p9 = new People("Reza",uniqueIdCounter++);


Sport s1 = new Sport("Football", Arrays.asList(p1,p2));
Sport s2 = new Sport("Basketball", Arrays.asList(p3,p4));
Sport s3 = new Sport("Baseball", Arrays.asList(p5,p2));
Sport s4 = new Sport("Hockey", Arrays.asList(p6,p7));
Sport s5 = new Sport("Soccer", Arrays.asList(p5,p8));
Sport s6 = new Sport("Handball", Arrays.asList(p3,p9));

List<Sport> sports = Arrays.asList(s1,s2,s3,s4,s5,s6);

public List<List<Sport>> group(List<Sport> sports){
    List<List<Sport>> answerList = new ArrayList<>();
    while (!sports.isEmpty()) {
        List<Sport> common = new ArrayList<>();
        List<Sport> toBeRemoved = new ArrayList<>();
        List<People> people = new ArrayList<>();
        people.addAll(sports.get(0).getPeopleWhoPlayThisSport());
        common.add(sports.get(0));
        toBeRemoved.add(sports.get(0));
        for (int i = 1; i < sports.size(); i++) {
            for (People p : sports.get(i).getPeopleWhoPlayThisSport()) {
                if (people.contains(p)) {
                    people.addAll(sports.get(i).getPeopleWhoPlayThisSport());
                    common.add(sports.get(i));
                    toBeRemoved.add(sports.get(i));
                    break;
                }
            }
        }
        sports = sports.stream().filter(sp->!toBeRemoved.contains(sp)).collect(Collectors.toList());
        answerList.add(common);
    }
    return answerList;
}
public static void main(String[] args) {
    GroupObjects groupObjects = new GroupObjects();
    List<List<Sport>> answer = groupObjects.group(groupObjects.sports);
    System.out.println(answer);
}

class Sport {
...

@Override
public String toString() {
    return sportsName;
}

另请注意，我在代码中使用了 Java-8 流 API。因此，如果您不使用 Java-8，请更改该行。

祝你好运！

对对象进行分组的算法

Algorithm to group objects

java

algorithm

grouping