1

所以我正在解决一个问题，并且遇到了我似乎无法找到解决方法的墙。我从操作系统获得了很多信息，我想我会在这里问，看看是否有比我发现的更好的方法来做到这一点。基本上，我有一个类，其中包含一堆值，但就我们的目的而言，只有一个很重要。

   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

融化你的大脑了吗？关于如何做到这一点的任何想法，或者即使我可以自己研究这种概念的名称？

4

4 回答 4

1

这是我的快速而肮脏的方法。

简短说明：
这个想法是从一对开始（可以将其视为图中的一个节点）。从该节点，您添加任何相邻节点（具有共享成员的对）。然后搜索与刚刚添加的节点相邻的节点。一直以来，您都会跟踪访问过哪些节点，这样您就不会无休止地循环。

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;
}
于 2013-05-29T17:58:45.953 回答
0

这只是一个解决方案的想法。

你需要知道你有多少独特的“个体”。对于您的示例，它是 26。

首先，您创建一个包含 26 对的字典，其中 key 是一个个体，在我们的例子中是一个字母，而 value 是一个组号，它将在最后。对于每一对，初始值应为零。

其次，您保留一个将存储下一个组号的“groupNumber”整数变量。你用 1 初始化它。

然后，您遍历 GroupPairs 列表。您采用第一个 GroupPair，其中包含“a”和“d”，并将字典中的相应值设置为“1”。

对于后面的每个 GroupPair，您可以获取其个体并在字典中查找相应的值。

如果其中一个值不为零，即其中一个人已经属于一个组，则将另一个值设置为相同的数字，从而将其放在同一组中。

如果两个值都为零，则将它们设置为“groupNumber”并增加“groupNumber”。

如果两个值都不为零，这就是有点棘手的地方。您在组字典中找到所有对，其中 value 等于该对中的第二个值，并将它们的值设置为该对中的第一个值。

完成后，您再次遍历 GroupPairs 列表。对于每一对，您在组字典中查找第一个个体，从而找出这对属于哪个组。

希望这是有道理的...

于 2013-05-29T17:52:31.597 回答
0

此代码匹配示例输入并生成所需的输出。基本上，我为每个组保留一个 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);
    }
}
于 2013-05-29T18:52:01.053 回答
0

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();
    }
}
于 2013-06-01T12:09:11.697 回答