Нахождение определенных аранжировок всех 2-комбинаций для данного списка

Учитывая список L четного числа (2k) элементов, я ищу алгоритм для создания списка 2k-1 подсписков со следующими свойствами:

  1. каждый подсписок включает ровно k 2-комбинации (пары, где порядок не имеет значения) элементов из L,
  2. каждый подсписок включает в себя все элементы из L ровно один раз, и
  3. объединение всех элементов из всех подсписков - это в точности множество всех возможных 2-комбинаций элементов из L.

Например, если входной список L = [a, b, c, d], мы имеем k = 2 с 3 подсписками, каждый из которых включает 2 пары. Возможное решение будет выглядеть как [[ab, cd], [ac, bd], [ad, bc]]. Если мы проигнорируем порядок для всех элементов в списках (представим, что все списки являются множествами), то окажется, что это также единственное решение для k = 2.

Моя цель сейчас не только найти единственное решение, но и все возможные решения. Поскольку число задействованных комбинаций растет довольно быстро, было бы неплохо, чтобы все результаты были построены умным способом, а не генерировали огромный список кандидатов и удаляли из него элементы, которые не удовлетворяют заданным свойствам. Такой наивный алгоритм может выглядеть следующим образом:

  1. Найти множество C всех 2-комбинаций для L.
  2. Найти множество D всех k-комбинаций для C.
  3. Выберите все множества из D, в которых объединение равно L, назовите новый набор D'.
  4. Найти множество E всех (2k-1)-комбинаций для D'.
  5. Выберите все множества из E, в которых объединение является множеством C, и пусть новый набор будет конечным результатом.

Этот алгоритм легко реализовать, но он невероятно медленен для больших входных списков. Так есть ли способ построить список результатов более эффективно?

Изменить: Вот результат для L = [a,b,c,d,e,f] с k = 3, рассчитанный по вышеуказанному алгоритму:

[[[ab,cd,ef],[ac,be,df],[ad,bf,ce],[ae,bd,cf],[af,bc,de]],
 [[ab,cd,ef],[ac,bf,de],[ad,be,cf],[ae,bc,df],[af,bd,ce]],
 [[ab,ce,df],[ac,bd,ef],[ad,be,cf],[ae,bf,cd],[af,bc,de]],
 [[ab,ce,df],[ac,bf,de],[ad,bc,ef],[ae,bd,cf],[af,be,cd]],
 [[ab,cf,de],[ac,bd,ef],[ad,bf,ce],[ae,bc,df],[af,be,cd]],
 [[ab,cf,de],[ac,be,df],[ad,bc,ef],[ae,bf,cd],[af,bd,ce]]]

Все свойства выполнены:

  1. каждый подсписок имеет k = 3 2-комбинации,
  2. каждый подсписок включает каждый элемент только один раз, и
  3. объединение всех 2k-1 = 5 подсписков для одного решения является в точности набором всех возможных 2-комбинаций для L.

Редактировать 2: Основываясь на ответе пользователя 58697, я улучшил алгоритм расчета, используя расписание турниров с круговым турниром:

  1. Пусть S будет набором результатов, начиная с пустого набора, а P будет множеством всех перестановок L.
  2. Повторите следующее, пока P не станет пустым:
    • Выберите произвольную перестановку из P
    • Выполните полное планирование RRT для этой перестановки. В каждом раунде расположение элементов из L формирует перестановку L. Удалите все эти 2k перестановок из P.
    • Добавьте полученный график в S.
  3. Удалите все списки из S, если объединение их подсписков имеет повторяющиеся элементы (т.е. не суммирует все 2-комбинации L).

Этот алгоритм гораздо более производительный, чем первый. Я смог рассчитать количество результатов для k = 4 как 960 и k = 5 как 67200. Тот факт, что для этой последовательности, похоже, нет результата OEIS, заставляет меня задуматься о том, действительно ли числа верны, т.е. если алгоритм производит полный набор решений.

Источник

2 ответа

Решение

Это был интересный вопрос. В процессе ответа на него (в основном после написания программы, включенной ниже, и поиска последовательности в OEIS), я узнал, что у проблемы есть имя и богатая теория: вам нужно сгенерировать все 1-факторизации полного графа К 2к.

Давайте сначала сформулируем проблему на этом языке:

Вам дается число k и список (набор) L размером 2k. Мы можем рассматривать L как множество вершин полного графа K 2k.

  • Например, при k=3 L может быть { a, b, c, d, e, f }

1-фактор (или идеальное совпадение) - это разбиение L на неупорядоченные пары (наборы размера 2). То есть это набор из k пар, чье несвязное объединение есть L.

  • Например, ab - cd - ef является 1-фактором L = { a, b, c, d, e, f }. Это означает, что a соответствует b, c соответствует d, а e соответствует f. Таким образом, L был разбит на три набора { a, b }, { c, d } и { e, f }, объединение которых равно L.

Пусть S (в вопросе называется C) обозначает все пары пар элементов L. (В терминах полного графа, если L - его множество вершин, S - его множество ребер.) Обратите внимание, что S содержит (2k выберите 2) = k(2k-1) пар. Таким образом, для k = 0, 1, 2, 3, 4, 5, 6… S имеет размер 0, 1, 6, 15, 28, 45, 66….

  • Например, S = { ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, ef } для нашего L выше (k = 3, поэтому |S| = k(2k-1) = 15).

1-факторизация - это разбиение S на множества, каждое из которых само является 1-фактором (идеальное совпадение). Обратите внимание, что поскольку каждое из этих сопоставлений имеет k пар, а S имеет размер k(2k-1), раздел имеет размер 2k-1 (т. Е. Состоит из сопоставлений 2k-1).

  • Например, это 1-факторизация: { ab - cd - ef, ac - be - df, ad - bf - ce, ae - bd - cf, af - bc - de }

Другими словами, каждый элемент S (каждая пара) встречается ровно в одном элементе 1-факторизации, и каждый элемент L встречается ровно один раз в каждом элементе 1-факторизации.

Задача просит сгенерировать все 1-факторизации.

Обозначим через M множество всех 1-факторов (всех совершенных соответствий) в L. Легко доказать, что M содержит (2k)!/(K!2^k) = 1×3×5×…×(2k-1) совпадения. Для k = 0, 1, 2, 3, 4, 5, 6… размер M равен 1, 1, 3, 15, 105, 945, 10395….

  • Например, для нашего L выше, M = { ab- cd- ef, ab- ce- df, ab- cf- de, ac- bd- ef, ac- be- df, ac- bf- de, ad- bc - ef, ad- be- cf, ad- bf- ce, ae- bc- df, ae- bd- cf, ae- bf- cd, af- bc- de, af- bd- ce, af- be- cd } (Для k=3 это число 15 совпадает с числом пар, но это просто совпадение, как вы можете из других чисел: это число растет намного быстрее, чем количество пар.)

М легко генерировать:

def perfect_matchings(l):
    if len(l) == 0:
        yield []
    for i in range(1, len(l)):
        first_pair = l[0] + l[i]
        for matching in perfect_matchings(l[1:i] + l[i+1:]):
            yield [first_pair] + matching

Например, позвонив perfect_matchings('abcdef') дает 15 элементов ['ab', 'cd', 'ef'], ['ab', 'ce', 'df'], ['ab', 'cf', 'de'], ['ac', 'bd', 'ef'], ['ac', 'be', 'df'], ['ac', 'bf', 'de'], ['ad', 'bc', 'ef'], ['ad', 'be', 'cf'], ['ad', 'bf', 'ce'], ['ae', 'bc', 'df'], ['ae', 'bd', 'cf'], ['ae', 'bf', 'cd'], ['af', 'bc', 'de'], ['af', 'bd', 'ce'], ['af', 'be', 'cd'] как и ожидалось.

По определению 1-факторизация - это разбиение S на элементы из M. Или, эквивалентно, любые (2k-1) непересекающиеся элементы из M образуют 1-факторизацию. Это поддается простому алгоритму возврата:

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

В коде:

matching_list = []
pair_used = defaultdict(lambda: False)
known_matchings = []  # Populate this list using perfect_matchings()
def extend_matching_list(r, need):
    """Finds ways of extending the matching list by `need`, using matchings r onwards."""
    if need == 0:
        use_result(matching_list)
        return
    for i in range(r, len(known_matchings)):
        matching = known_matchings[i]
        conflict = any(pair_used[pair] for pair in matching)
        if conflict:
            continue  # Can't use this matching. Some of its pairs have already appeared.
        # Else, use this matching in the current matching list.
        for pair in matching:
            pair_used[pair] = True
        matching_list.append(matching)
        extend_matching_list(i + 1, need - 1)
        matching_list.pop()
        for pair in matching:
            pair_used[pair] = False

Если вы называете это с extend_matching_list(0, len(l) - 1) (после заполнения known_matchings), он генерирует все 1-факторизации. Я поместил полную программу, которая делает это здесь. С k=4 (конкретно, список 'abcdefgh') выдает 6240 1-факторизаций; полный вывод здесь.

Именно в этот момент я ввел последовательность 1, 6, 6240 в OEIS и обнаружил OEIS A000438, последовательность 1, 1, 6, 6240, 1225566720, 252282619805368320,…. Это показывает, что при k=6 число решений ≈2,5 × 10 17 означает, что мы можем оставить надежду на генерацию всех решений. Даже для k=5 ≈1 млрд. Решений (напомним, что мы пытаемся найти 2k-1=9 непересекающихся множеств из соответствий |M|=945) потребуют некоторых тщательно оптимизированных программ.

Первая оптимизация (которую, как ни странно, я позже понял только при внимательном рассмотрении вывода трассировки для k=4), заключается в том, что (при естественной лексикографической нумерации) индекс первого совпадения, выбранного в разделе, не может быть больше, чем число совпадений для K-1. Это потому, что лексикографически первый элемент S (например, " ab ") встречается только в этих сопоставлениях, и если мы начнем позже, чем этот, мы никогда не найдем его снова в любом другом сопоставлении.

Вторая оптимизация проистекает из того факта, что узким местом программы обратного отслеживания обычно является проверка того, является ли текущий кандидат приемлемым. Нам нужно эффективно проверить дизъюнктность: не пересекается ли данное совпадение (в нашей частичной факторизации) с объединением всех предыдущих совпадений. (Является ли любая из его k пар одной из пар, уже охваченных предыдущими сопоставлениями.) При k=5 оказывается, что размер S, который равен (2k выберите 2) = 45, меньше 64, поэтому мы может компактно представить совпадение (которое в конце концов является подмножеством S) в 64-битном целочисленном типе: если мы нумеруем пары от 0 до 44, то любое совпадение может быть представлено целым числом, имеющим 1 в позициях, соответствующих элементам это содержит. Тогда проверка на дизъюнктность - это простая побитовая операция над целыми числами: мы просто проверяем, равняется ли значение побитового И текущего совпадения-кандидата и накопительного объединения (побитового ИЛИ) предыдущих совпадений в нашей частичной факторизации.

Программа на C++, которая делает это, находится здесь, и только часть возврата (специализированная для k=5) не нуждается в каких-либо функциях C++, поэтому она извлекается здесь как программа на C. Он работает около 4-5 часов на моем ноутбуке и находит все 1225566720 1-факторизаций.

Другой способ взглянуть на эту проблему - сказать, что два элемента M имеют ребро между ними, если они пересекаются (имеют общую пару (элемент S)), и что мы ищем все максимально независимые множества в M. Опять же, самый простой способ решить эту проблему - это, вероятно, вернуться назад (мы бы написали ту же программу).

Наши программы можно сделать намного более эффективными, если использовать симметрию в нашей задаче: например, мы можем выбрать любое совпадение в качестве нашего первого 1-фактора в 1-факторизации (а затем сгенерировать остальное путем перемаркировки, стараясь не допустить дубликаты). Так рассчитывалось число 1-факторизаций для K 12 (текущая запись).

Заметка о мудрости генерации всех решений

В книге "Искусство компьютерного программирования", том 4А, в конце раздела 7.2.1.2 " Генерация всех перестановок" Кнут дает следующий важный совет:

Подумайте дважды, прежде чем переставлять. Мы видели несколько привлекательных алгоритмов для генерации перестановок в этом разделе, но известно много алгоритмов, с помощью которых можно найти перестановки, которые являются оптимальными для конкретных целей, не используя все возможности. Например, […] лучший способ упорядочить записи в последовательном хранилище […] - это всего O (n log n) шагов. […] Задача присваивания, которая спрашивает, как переставить столбцы квадратной матрицы так, чтобы сумма диагональных элементов была максимизирована […] может быть решена не более чем за O (n 3) операций, так что было бы глупо используйте метод порядка n! если п очень мало. Даже в тех случаях, как, например, проблема путешествующих продаж, когда эффективный алгоритм не известен, мы обычно можем найти гораздо лучший подход, чем изучение каждого возможного решения. Генерация перестановок лучше всего используется, когда есть веская причина рассматривать каждую перестановку индивидуально.

Вот что, по-видимому, произошло здесь (из комментариев ниже вопроса):

Я хотел рассчитать все решения для запуска различных атрибутных метрик на них и найти необязательное соответствие […]. Поскольку число результатов растет быстрее, чем ожидалось, это нецелесообразно.

Как правило, если вы пытаетесь "сгенерировать все решения", и у вас нет очень веских причин для рассмотрения каждого из них (а один почти никогда не делает этого), существует множество других подходов, которые предпочтительнее, начиная от непосредственной попытки до решить проблему оптимизации, генерировать случайные решения и смотреть на них, или генерировать решения из некоторого подмножества (что, по-видимому, вы и сделали).

дальнейшее чтение

Последующие рекомендации OEIS привели к богатой истории и теории.

  • О 1-факторизации полного графа и связи с циклическими расписаниями, Геллинг (М.А. Тезис), 1973

  • О числе 1-факторизаций полного графа Чарльза С. Линднера, Эрика Мендельсона, Александра Розы (1974?) - это показывает, что число неизоморфных 1-факторизаций на K 2n стремится к бесконечности, а n - к бесконечности.

  • Э. Мендельсон и А. Роза. О некоторых свойствах 1-факторизаций полных графов. Congr. Нумер, 24 (1979): 739–752

  • Э. Мендельсон и А. Роза. Одна факторизация полного графа: опрос. Журнал теории графов, 9 (1985): 43–65 (Еще в 1985 году этот точный вопрос был изучен достаточно хорошо, чтобы потребовать исследования!)

  • Через документы Динитиз:

    • DK Garnick и JH Dinitz, О числе однофакторизаций полного графа на 12 точках, Congressus Numerantium, 94 (1993), с. 159-168. Они объявили, что вычисляют число неизоморфных 1-факторизаций K 12. Их алгоритм был в основном с возвратом.
    • Джеффри Х. Диниц, Дэвид К. Гарник, Брендан Д. Маккей: существует 526 915 620 неизоморфных однофакторизаций K12 (также здесь), Journal of Combinatorial Designs 2 (1994), с. 273 - 285: они завершили вычисления, и сообщили числа, которые они нашли для K 12 (526 915 620 неизоморфных, всего 252 282 619 805 368 320).

  • Различные однофакторизации полных графов по Gopal, Kothapalli, Venkaiah, Subramanian (2007). Документ, который имеет отношение к этому вопросу, и имеет много полезных ссылок.

  • WD Wallis, Введение в комбинаторные конструкции, второе издание (2007). Глава 10 - "Однофакторизация", Глава 11 - "Применение однофакторизации". Оба очень актуальны и имеют много полезных ссылок.

  • Чарльз Дж. Колборн и Джеффри Х. Диниц, Справочник по комбинаторным проектам, второе издание (2007). Золотая жила. См. Главы VI.3 Сбалансированные дизайны турниров, VI.51 Планирование турнира, VII.5 Факторизация графов (включая разделы 5.4 Перечисление и таблицы, 5.5 Некоторые 1-факторизации полных графов), VII.6 Вычислительные методы в теории дизайна (6.2 Исчерпывающий поиск). Эта последняя глава ссылается на:

    • [715] Как рассчитывалось K 12 ("упорядоченный алгоритм"), обратный ход - упомянутая выше статья Диница-Гарника-Маккея
    • [725] "Содержит, среди многих других предметов, связанных с факторизацией, быстрый алгоритм для нахождения 1-факторизаций K 2n." ("Квадраты комнат и связанные схемы", JH Dinitz и SR Stinson)
    • [1270] (P. Kaski и PRJ Östergård, Однофакторизация регулярных графов порядка 12, Электрон. J. Comb. 12, Исследовательская работа 2, 25 с. (2005))
    • [1271] "Содержит 1-факторизацию полных графов до порядка 10 в электронном виде". (P. Kaski и PRJ Östergård, Классификационные алгоритмы для кодов и конструкций, Springer, Berlin, 2006.)
    • [1860] "Обзор совершенных 1-факторизаций K 2n " (Е.С. Сеа, Совершенные однофакторизации полного графа. Обзор, Bull. Inst. Combin. Appl. 1 (1991) 59–70)
    • [2107] "Обзор 1-факторизации полных графов, включающий большую часть материала этой главы". У.Д. Уоллис, Однофакторизация полных графов, в работе Диница и Стинсона (ред.), Теория современного дизайна, 1992
    • [2108] "Книга по 1-факторизации графов". У.Д. Уоллис, "Однофакторизация", Kluwer, Dordrecht, 1997

Некоторые другие вещи:

Источник

Это расписание кругового турнира:

  1. Пара - это спичка,
  2. Список - это раунд (каждая команда играет с какой-то другой командой)
  3. Набор списка - это целый турнир (каждая команда играет одну команду ровно один раз).

Посмотрите здесь.

Источник
Другие вопросы по тегам