分组算法

Question

我试图帮助某人编写一个我认为很容易的程序，但当然它从来都不是:)

我试图采取班级名册（通常在 10-20 名学生之间）并有效地将每个同学与另一个同学有效地唯一配对建立独特的群体。 因此，一个10人的班级，可以分成9组。

它也需要能够处理奇数数量的学生，这增加了我的困惑。

我正在考虑用 Java 来做这件事，但这很灵活。 关于算法方式的任何想法都可以保证a）不是无限循环（以已经成为合作伙伴的2个人结束）和b）我的目标是时间比空间更有效，因为班级规模会很小！

谢谢！

Answer 1

我不知道这是否正是您所要求的，但这里是我用简单的 python 来实现的。
它会给出（在我的示例中）10 名学生的每个独特分组。

我猜这不是最快的事情，但它很容易实现和遵循。

from itertools import permutations

def my_sort(x):
    assert type(x) in (tuple, list)
    assert len(x)==10
    groups = x[0:2],x[2:4],x[4:6],x[6:8],x[8:10]
    groups = sorted([sorted(g) for g in groups], key=lambda k:k[0])
    return tuple(x  for g in groups for x in g )

S = set(my_sort(p) for p in permutations(list(range(10))))

"""
len(S) == 945
list(sorted(S))[-3:] == [(0, 9, 1, 8, 2, 7, 3, 4, 5, 6), (0, 9, 1, 8, 2, 7, 3, 5, 4, 6), (0, 9, 1, 8, 2, 7, 3, 6, 4, 5)]
"""

元组代表一行中的所有组：
(0, 9, 1, 8, 2, 7, 3, 4, 5, 6) 表示 0 与 9 分组，1 与 8 分组，依此类推。

Answer 2

您想要创建一个以每个学生为节点的完整图，然后随机选择边并将它们插入到唯一的集合中。

在下一次“拉动”时，您想要执行相同的操作，但现在如果边缘已被选择，则丢弃并重新选择。

Answer 3

这是解决问题的 C# 代码。

我假设您真正关心的是最大化学生配对的独特性，而不是一组可能的独特学生配对组。

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace Pairing
{
    class Program
    {
        static void Main(string[] args)
        {
            //switch these lines if you'd prefer a command line interface to a text file.
            var rgs = File.ReadAllLines("Roster.txt");
            //var rgs = args;

            var setPairs = new HashSet<HashSet<string>>();
            for (var ixrgs = 0; ixrgs < rgs.Length - 1; ixrgs++)
                for (var ixrgsSubset = ixrgs + 1; ixrgsSubset < rgs.Length; ixrgsSubset++)
                    setPairs.Add(new HashSet<string>(new string[] { rgs[ixrgs], rgs[ixrgsSubset] }));

            var setGroups = new HashSet<HashSet<HashSet<string>>>();
            var setUsedPairs = new HashSet<HashSet<string>>();
            while (setPairs.Count > 0)
            {
                var setPairsTmp = new HashSet<HashSet<string>>(setPairs);
                var setTmp = new HashSet<HashSet<string>>();
                var setUsedVariables = new HashSet<string>();

                while (setPairsTmp.Count > 0)
                {
                    //give me the first element
                    var pair = setPairsTmp.First<HashSet<string>>();
                    //store it
                    setTmp.Add(pair);
                    //add it to our set of used variables
                    setUsedVariables.UnionWith(pair);
                    //remove it from our set of available pairs.
                    setPairsTmp.RemoveWhere(set => set.Intersect<string>    (setUsedVariables).Count<string>() != 0);

                    //remove its implicated deadlocks from our set of available pairs
                    //(this step is both gross, and key. Without it, failure potential arises.)
                        var s1 = new HashSet<string>();
                        var s2 = new HashSet<string>();
                        //get the set of variables paired with the first:
                        var rgPair = pair.ToArray<string>();
                        foreach (var set in setUsedPairs)
                        {
                            if (set.Contains(rgPair[0]))
                                s1.UnionWith(set);
                            if(set.Contains(rgPair[1]))
                                s2.UnionWith(set);
                        }
                        s1.IntersectWith(s2);
                        //enumerate the pairs created by the deadlocking pairs, remove them from our available selections.
                        var rgsTmp = s1.ToArray<string>();
                        for (var ixrgs = 0; ixrgs < rgsTmp.Length - 1; ixrgs++)
                            for (var ixrgsSubset = ixrgs + 1; ixrgsSubset < rgsTmp.Length; ixrgsSubset++)
                                setPairsTmp.RemoveWhere(set => set.Contains(rgsTmp[ixrgs]) && set.Contains(rgsTmp[ixrgsSubset]));
                }
                setPairs.ExceptWith(setTmp);
                setGroups.Add(setTmp);
                setUsedPairs.UnionWith(setTmp);
            }
            //at this point, setGroups contains the set of unique group combinations.
            //the non-maximally sized groups indicate unique sets that could form provided that
            //all other students are in redundant sets.

            var enumerableGroups = setGroups.OrderByDescending<HashSet<HashSet<string>>, int>(set => set.Count);
            //Sanity Check:
            foreach (var group in enumerableGroups)
            {
                Console.Write("{");
                foreach (var pair in group)
                    Console.Write(string.Format(@"[{0},{1}]", pair.ToArray<string>()));
                Console.WriteLine("}");
            }
        }
    }
}

Answer 4

这对我来说是一个不寻常的答案 - 说“下载应用程序” - 但你就可以了：

你所描述的可能与国际象棋锦标赛配对足够相似。

看看这个：http://home.swipnet.se/rullchef/chessp/

这里是对 Monrad 系统的解释可能就是您所追求的：

蒙拉德系统

蒙拉德系统是杯赛系统的一个非常有趣的变体，据我所知，该系统仅在国际象棋锦标赛中定期使用。 在第一轮中，所有队伍都是随机配对的。 获胜者得 1 分，失败者得 0 分。 在连续的每一轮中，所有得分相同的球队将被随机配对（除非之前交手过的球队如果还有其他配对的可能性，则不能配对）。 与杯赛系统相比，这种系统的优点是所有球队都可以继续比赛，并且随着赛季（或锦标赛）的推进，实力相当的球队将相互相遇。 可以进行的轮数没有限制，但如果分数相似但不一定相同的球队最终必须配对。 在一组预定义的回合后得分最多的团队是获胜者。

Answer 5

这是上面 Vlion 答案的伪代码。 这不是最快的方法，但它是概念的说明（感谢 Vlion！）

// create all the edges
for i := 1 to number_of_students - 1
  for j := i + 1 to number_of_students
    edges.add(new Edge(i,j))

// select all groups from the edges
for x := 1 to number_of_students - 1
  used_nodes.clear
  group.clear

  for y := 1 to number_of_students div 2
    do
      current_edge = edges.get_next
    while (current_edge.n1 not in used_nodes) and
          (current_edge.n2 not in used_nodes)

    used_nodes.add(current_edge.n1)
    used_nodes.add(current_edge.n2)

    group.add(current_edge)

    edges.remove(current_edge)

  groups.add(group)

Answer 6

您要求的算法似乎与准备循环赛赛程的算法或多或少相同。 详细信息可以在这篇维基百科文章中找到。 您还可以使用网上的生成器进行快速试用。 其中之一可以在此处找到。