Блог

Я пытаюсь помочь кому-то написать программу, которая, как я думал, будет легкой, но, конечно, это никогда не так 🙂

Я пытаюсь составить список классов (обычно между 10-20 учениками) и эффективно объединять каждого одноклассника с другим, чтобы создать уникальные группы. Поэтому в классе из 10 человек у вас может быть 9 групп.

Он также должен уметь обрабатывать нечетное количество студентов, что еще больше усугубляет мое замешательство.

Я хотел сделать это на Java, но это очень гибко. Любые идеи по алгоритмическому способу гарантировать а)не бесконечный цикл (заканчивающийся 2 людьми, которые уже были партнерами) и б) Я стремлюсь к более эффективному времени, чем пространству, так как размер класса будет небольшим!

Спасибо!

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

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

Это необычный ответ для меня — сказать «загрузить приложение», — но вот он:

То, что вы описываете, может быть достаточно похоже на парный шахматный турнир.

Проверьте это: http://home.swipnet.se/rullchef/chessp/

Вот объяснение системы Monrad, которое может быть тем, что вам нужно:

Система Monrad

Система Монрад является очень интересной вариацией системы кубков, которая, насколько мне известно, используется только на регулярной основе в шахматных турнирах. В первом раунде все команды случайным образом разбиваются на пары. Победитель получает 1 очко, а проигравший-ноль. В каждом последующем раунде все команды с одинаковым количеством очков случайным образом спариваются (за исключением команд, которые ранее играли друг с другом, не могут быть спарены, если есть другие возможности для спаривания). Эта система имеет то преимущество, что все команды продолжают играть, в отличие от кубковой системы, и по мере продвижения сезона (или турнира) команды с одинаковой силой будут встречаться друг с другом. Нет никаких ограничений на количество раундов, которые можно сыграть, но в конечном итоге команды должны быть объединены в пары, если у них одинаковое, но не обязательно одинаковое количество очков. Команда, набравшая наибольшее количество очков после определенного набора раундов, становится победителем.

Вот псевдокод для ответа Влаона выше. Это не самый быстрый способ сделать это, но это иллюстрация концепции (спасибо, Влаон!)

 // 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)
 

Вот код на 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]) amp;amp; 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("}");
            }
        }
    }
}
 

Алгоритм, который вы просите, кажется более или менее таким же, как алгоритм подготовки расписаний для круговых турниров. Подробности можно найти в этой статье в Википедии. Вы также можете использовать генераторы, лежащие в Интернете, для быстрой проверки. Один из них можно найти здесь.

Я не знаю, точно ли это то, о чем вы просили, но вот мой взгляд на это в простом 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 и так далее.