Алгоритм группировки

Question

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

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

Нужно уметь справляться и с нечетным количеством студентов, что еще больше усложняет ситуацию.

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

Спасибо!

Answer 1

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

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

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

Вот псевдокод ответа Влиона выше. Это не самый быстрый способ сделать это, но это иллюстрация концепции (спасибо 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 5

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

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

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

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

Система Монрад

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

Answer 6

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