私は誰かが簡単だと思ったプログラムを書くのを手伝おうとしていますが、もちろん決してそうではありません:)
クラスの名簿 (通常は 10 ～ 20 人の学生) を作成し、各クラスメートを効果的に一意にペアにして、一意のグループを作成しようとしています。したがって、10 人のクラスでは、9 つのグループを持つことができます。
奇数の学生も処理できる必要があり、混乱を招きます。
Javaでこれを行うことを検討していましたが、それは柔軟です。a）無限ループではない（すでにパートナーになっている2人で終わる）、およびb）クラスサイズが小さいため、スペースよりも効率的な時間を目指しています！
ありがとう！
各生徒をノードとして完全なグラフを作成し、エッジをランダムに選択して、それらを一意のセットに挿入します。
次の「プル」では、エッジが既に選択されている場合を除き、同じことを行い、破棄して再選択します。
これが質問を解決する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("}");
}
}
}
}
上記の 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)
あなたが求めているアルゴリズムは、ラウンドロビン トーナメントのスケジュールを準備するためのアルゴリズムとほぼ同じようです。詳細については、このウィキペディアの記事を参照してください。Web 上にあるジェネレーターを使用して、簡単に試してみることもできます。そのうちの 1 つをここで見つけることができます。
「アプリケーションをダウンロードしてください」と言うのは、私にとっては珍しい答えですが、以下をご覧ください。
あなたが説明することは、チェス トーナメント ペアリングに十分似ているかもしれません。
これをチェックしてください：http://home.swipnet.se/rullchef/chessp/
あなたが求めているかもしれないMonradシステムの説明は次のとおりです。
Monrad システムは、私の知る限り、チェス トーナメントで定期的にしか使用されていないカップ システムの非常に興味深いバリエーションです。最初のラウンドでは、すべてのチームがランダムにペアになります。勝者は 1 点、敗者は 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 でグループ化されるなどを意味します。