4

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

我正在尝试制定班级名册（通常在 10 到 20 名学生之间），并有效地将每个同学与另一个同学配对，以组成独特的小组。因此，在一个 10 人的班级中，您可以有 9 个小组。

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

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

谢谢！

4

6 回答 6

2

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

在下一次“拉动”时，你想做同样的事情，除了现在如果边缘已经被选中，丢弃并重新选择。

于 2008-10-14T01:11:49.147 回答
1

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

您所描述的可能与国际象棋锦标赛配对非常相似。

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

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

蒙拉德系统

Monrad 系统是杯子系统的一个非常有趣的变体，据我所知，它仅在国际象棋锦标赛中定期使用。在第一轮中，所有队伍随机配对。胜者得 1 分，较松者得 0 分。在随后的每一轮中，所有得分相同的球队随机配对（除了之前交手过的球队，如果有其他配对的可能性，则不能配对）。与杯赛系统相比，该系统的优势在于所有球队都在继续比赛，并且随着赛季（或锦标赛）的推进，实力相同的球队将相互交锋。可以玩的回合数没有限制，但如果球队的分数相似但不一定相同，最终必须配对。

于 2008-10-14T01:29:38.910 回答
1

这是上面 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)
于 2008-10-14T03:11:15.927 回答
1

这是解决问题的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("}");
            }
        }
    }
}
于 2008-10-14T07:39:03.640 回答
1

您要求的算法似乎或多或少与为循环锦标赛准备时间表的算法相同。详细信息可在此 Wikipedia 文章中找到。您还可以使用网络上的生成器进行快速试用。其中之一可以在这里找到。

于 2008-10-14T14:35:53.503 回答
0

我不知道这是否正是你所要求的，但在这里我用简单的 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 分组，依此类推。

于 2019-03-25T11:39:50.117 回答