Group pairs of connected values into Lists

Question

So I am working on a problem, and coming up against a wall that I can't seem to find a way around. I get so much information from OS, that I thought I would ask on here, and see if there is a way to do this better than what I'm finding. Basically, I have a class that has a bunch of values in it, but for our purposes only one matters.

   public class GroupPair
   {
       public string object1 { get; set; }
       public string object2 { get; set; }
       public List<string> BothObjects
       {
           get
           {
               List<string> s= new List<string>();
               s.Add(object1);
               s.Add(object2);
               return s;
           }
  }

I have a List, and I need to be able to sort them into groups. Where it becomes tricky is that both values are not unique, and the group size and number of groups is variable. I basically need a way to say, "give me every group that can be made from this list, where each group contains all pairs that include any individual member of the group." Let me give and example... here are some pairs:

a   d
f   h
d   t
n   w
h   a
n   o
q   d
w   f
o   y

After the grouping, this is what I want:

Group 1
a   d
h   a
q   d
f   h
w   f
d   t

Group 2
n   x
n   o
o   y

Melt your brain yet? Any ideas on how this could be done, or even if there is a name for this kind of concept that I can research myself?

Answer 1

For the sake of completeness I also have a recursive solution. Near the end is the GroupPair class that acts as datacontainer with two helper methods: Add and Merge.

You invoke it like so:

var gp = GroupByPairs(
            new List<Tuple<string, string>>
                {
                    new Tuple<string, string>("a", "d"),
                    new Tuple<string, string>("f", "h"),
                    /*  you get the idea */
                }.GetEnumerator());

foreach (var groupData in gp)
{
    Console.WriteLine(groupData.ToString());
}

//recursive take on the problem
private static IEnumerable<GroupPair> GroupByPairs(
    IEnumerator<Tuple<string, string>> pairs)
{
    // result Groups
    var listGroup = new List<GroupPair>();
    if (pairs.MoveNext())
    {
        var item = pairs.Current;
        var current = new GroupPair(item);

        var subgroup = GroupByPairs(pairs); // recurse

        // loop over the groups
        GroupPair target = null;
        foreach (var groupData in subgroup)
        {
            // find the group the current item matches
            if (groupData.Keys.Contains(item.Item1) ||
                groupData.Keys.Contains(item.Item2))
            {
                // determine if we already have a target
                if (target == null)
                {
                    // add item and keep groupData
                    target = groupData;
                    groupData.Add(item);
                    listGroup.Add(groupData);
                }
                else
                {
                    // merge this with target
                    // do not keep groupData 
                    target.Merge(groupData);
                }
            }
            else
            {
                // keep groupData
                listGroup.Add(groupData);
            }
        }
        // current item not added
        // store its group in the listGroup
        if (target == null) 
        {
            listGroup.Add(current);    
        }
    }
    return listGroup;
}

public class GroupPair
{
    private static int _groupsCount = 0;
    private int id;

    public GroupPair(Tuple<string, string> item)
    {
        id = Interlocked.Increment(ref _groupsCount);
        Keys = new HashSet<string>();
        Items = new List<Tuple<string, string>>();
        Add(item);
    }

    // add the pair and update the Keys
    public void Add(Tuple<string, string> item)
    {
        Keys.Add(item.Item1);
        Keys.Add(item.Item2);
        Items.Add(item);
    }

    // Add all items from another GroupPair
    public void Merge(GroupPair groupPair)
    {
        foreach (var item in groupPair.Items)
        {
            Add(item);
        }
    }

    public HashSet<string> Keys { get; private set; }

    public List<Tuple<string, string>> Items { get; private set; }

    public override string ToString()
    {
        var build = new StringBuilder();
        build.AppendFormat("Group {0}", id);
        build.AppendLine();
        foreach (var pair in Items)
        {
            build.AppendFormat("{0} {1}", pair.Item1, pair.Item2);
            build.AppendLine();
        }
        return build.ToString();
    }
}

Answer 2

This code matches the sample input and produces the required output. Bascially I keep a HashSet of items per group and have list of remaing items to process.

private static void GroupPairs(List<Tuple<string, string>> pairs)
{
    int groupCounter = 0;

    while (pairs.Count > 0)
    {
        var onegroup = new HashSet<string>();
        Console.WriteLine("Group {0}", ++groupCounter);

        int initialGroupCount;
        do
        {
            var remainder = new List<Tuple<string, string>>();
            initialGroupCount = onegroup.Count;
            foreach (var curr in pairs)
            {
                if (onegroup.Contains(curr.Item1) ||
                    onegroup.Contains((curr.Item2)) ||
                    onegroup.Count == 0)
                {
                    Console.WriteLine("{0} {1}", curr.Item1, curr.Item2);
                    onegroup.Add(curr.Item1);
                    onegroup.Add(curr.Item2);
                }
                else
                {
                    remainder.Add(curr);
                }
            }
            pairs = remainder;
        } while (initialGroupCount < onegroup.Count);
    }
}

Answer 3

Here's my quick-and-dirty approach.

Short explanation:
The idea is to start with one pair (which can be thought of as a node in a graph). From that node, you add any adjacent nodes (pairs which have a shared member). Then you search the nodes adjacent to those nodes that you just added. All along you keep track of which nodes have been visited so you don't loop endlessly.

public static List<HashSet<GroupPair>> GetGroups(IEnumerable<GroupPair> pairs)
{
   var groups = new List<HashSet<GroupPair>();

   var unassignedPairs = new HashSet<GroupPair>(pairs);
   while (unassignedPairs.Count != 0)
   {
      var group = new HashSet<GroupPair>();
      var rootPair = unassignedPairs.First();
      group.Add(rootPair);
      unassignedPairs.Remove(rootPair);

      var membersToVisit = new Queue<string>(rootPair.BothObjects);
      var visited = new HashSet<string>();
      while (members.Count != 0)
      {
         string member = membersToVisit.Dequeue();
         visited.Add(member);
         foreach (var newPair in unassignedPairs
                 .Where(p => p.BothObjects.Contains(member)).ToList())
         {
            group.Add(newPair);
            unAssignedPairs.Remove(newPair);
            foreach (var newMember in newPair.BothObjects.Except(visited))
            {
               membersToVisit.Enqueue(newMember)
            }
         }
      }
      groups.Add(group);
   }
   return groups;
}

Answer 4

This is just an idea for a solution.

You'll need to know how many unique 'individuals' you have. For your example, it's 26.

First, you create a dictionary of 26 pairs, where key is an individual, in our case a letter, and a value is a group number where it will be in the end. For each pair, initial value should be zero.

Second, you keep a 'groupNumber' integer variable that will store the next group number. You initialise it with 1.

Then, you iterate over the list of GroupPairs. You take the first GroupPair, which contains 'a' and 'd' and set the respective values in the dictionary to '1'.

For each following GroupPair you take its individuals and look up the respective values in the dictionary.

If one of the values is non-zero, i.e. one of the individuals already belongs to a group, you set the other value to the same number, thus putting it in the same group.

If both values are zeros you set them to 'groupNumber' and increment 'groupNumber'.

If both values are non-zero, this is where it gets a bit tricky. You find all pairs in the group dictionary where value equals the second value from that pair, and set their value to the first value from that pair.

After that is done, you iterate over the list of GroupPairs once again. For each pair you look up the first individual in the group dictionary and thus find out which group the pair belongs to.

Hope that makes sense...