Search code examples
javalistjava-stream

Create unique pair of elements in a list based on some attribute of the class/object

I have a JSON file in the below format

[
  { "name": "John", "team": "NW", "available": true },
  { "name": "Dani", "team": "NW", "available": true },
  { "name": "Lyle", "team": "NW", "available": false },
  { "name": "Dean", "team": "W", "available": true },
  { "name": "Lyle", "team": "W", "available": true },
  { "name": "David", "team": "W", "available": true },
  { "name": "George", "team": "SW", "available": false },
  { "name": "Luke", "team": "SW", "available": false }
]

and the corresponding Java class like below:

public class Agent {
  private String name;
  private String team;
  private Boolean available;
  ...
  ...
}

I need to pair members from the list with other people on the list. The rules are that the pair has to be with a member who is available and is from a different team. Need to list the pairs of the members along with any members which could not be paired (odd number of 'pairable' members/not enough members in other teams).

I have written the code to read the JSON in a list of 'Agent' objects using Jackson and have tried the following approaches till now

  • Iterating over the list and getting the first 'available' member and fetching another one from different team (used stream API/filtering to do this)
  • Create a map of agents (key: team, value: agent list) and iterate the EntrySet to pair the agents with agents from another team.
  • Naive approach of creating anew list and adding elements from the original list as and when they are mapped)

However, I am getting a lot of agents unmapped. I wanted to write the logic in such a way that it matches/pairs maximum numbers of agents and print the remaining agents in the output alongwith the agents that were paired.

Not looking for a full blown solution - any pointers will be greatly appreciated!

Solution

  • To confirm, when running you first,

    1. Check if the agent is available.
    2. Find a matching agent from a different team (From the map of agents)
    3. And if a match is found, add the pair of agents to the list of pairs and mark both agents in the EntrySet, otherwise mark the agent as unmatched.

    Correct?

    If so, it sounds like you already have a good solution to the problem, and I would double check your code to ensure you are following these steps properly. A limitation within the data (Such as very unbalanced team sizes), could also cause you to get unbalanced results.

    If you wanted another approach though, I would suggest using a 'Maximal Matching' Algorithm, like the Hopcroft-Karp algorithm or the Edmonds' Blossom algorithm to find the maximum matching.

    In your case, the agents would be represented as nodes in the bipartite graph, Node set 1 representing available agents and Node set 2 representing unavailable agents. Then generate the edges between the two sets, where each node would represent a potential pairing.

    An overview of the algorithm can be found here; https://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-1-introduction/

    All you would need to do is generate these nodes and edges, as many implementations of the algorithm can be found online :)