Групповые пары подключенных значений в списках

Question

Итак, я работаю над проблемой и приступаю к стене, и я не могу найти способ обойти ее. Я получаю так много информации от ОС, что я думал, что попрошу здесь, и посмотреть, есть ли способ сделать это лучше, чем то, что я нахожу. В принципе, у меня есть класс, в котором есть куча ценностей, но для наших целей имеет значение только одно.

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; 
      } 
    } 

У меня есть список, и мне нужно иметь возможность сортировать их по группам. Там, где становится сложно, оба значения не уникальны, а размер группы и количество групп являются переменными. Мне в основном нужен способ сказать: «Дайте мне каждую группу, которая может быть сделана из этого списка, где каждая группа содержит все пары, которые включают в себя любого отдельного члена группы». Позвольте мне привести пример, и ... вот некоторые пары:

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

После группировки, это то, что я хочу:

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

Group 2 
n x 
n o 
o y 

Растопить ваш мозг еще? Любые идеи о том, как это можно сделать, или даже если есть название такого понятия, которое я могу исследовать сам?

Answer 1

Это всего лишь идея для решения.

Вам нужно знать, сколько уникальных «индивидуумов» у вас есть. Для вашего примера это 26.

Во-первых, вы создаете словарь из 26 пар, где ключ является индивидуальным, в нашем случае буквой, а значение представляет собой номер группы, где он будет в конце. Для каждой пары начальное значение должно быть равным нулю.

Во-вторых, вы сохраняете целочисленную переменную 'groupNumber', которая будет хранить следующий номер группы. Вы инициализируете его с помощью 1.

Затем вы перебираете список GroupPairs. Вы берете первый GroupPair, который содержит «a» и «d» и устанавливает соответствующие значения в словаре на «1».

Для каждой следующей группы GroupPair вы берете своих физических лиц и просматриваете соответствующие значения в словаре.

Если одно из значений отличное от нуля, то есть один из лиц уже принадлежит группе, вы устанавливаете другое значение на одно и то же число, тем самым помещая его в ту же группу.

Если оба значения являются нулями, вы устанавливаете их в «groupNumber» и увеличиваете «groupNumber».

Если оба значения отличны от нуля, здесь он становится немного сложным. Вы находите все пары в словаре групп, где значение равно второму значению из этой пары и устанавливает их значение в первое значение из этой пары.

После этого вы снова инете перебираете список GroupPairs. Для каждой пары вы просматриваете первого человека в групповом словаре и, таким образом, узнаете, к какой группе принадлежит пара.

Надежда, что имеет смысл ...

Answer 2

Вот мой быстрый и грязный подход.

Краткое описание:
Идея состоит в том, чтобы начать с одной пары (которую можно рассматривать как узел на графике). С этого узла вы добавляете любые соседние узлы (пары, которые имеют общий член).Затем вы просматриваете узлы, смежные с теми узлами, которые вы только что добавили. Все время вы отслеживаете, какие узлы были посещены, чтобы вы не зацикливались бесконечно.

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 3

Этот код соответствует образцу ввода и производит требуемый выход. Баснически я сохраняю HashSet элементов для каждой группы и имею список перепрограммируемых элементов для обработки.

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 4

Для полноты у меня также есть рекурсивное решение. Ближе к концу это класс GroupPair, который действует как datacontainer с двумя вспомогательными методами: Add и Merge.

вы вызываете его следующим образом:

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(); 
    } 
}