У меня есть набор пар. Каждая пара имеет форму (x, y), так что x, y принадлежат целым числам из диапазона [0,n)
.
Итак, если n равно 4, то у меня есть следующие пары:
(0,1) (0,2) (0,3)
(1,2) (1,3)
(2,3)
У меня уже есть пары. Теперь я должен построить комбинацию, используя n/2
пары, чтобы ни одно из целых чисел не повторялось (другими словами, каждое целое число появляется хотя бы один раз в финальной комбинации). Ниже приведены примеры правильной и неправильной комбинации для лучшего понимания.
1. (0,1)(1,2) [Invalid as 3 does not occur anywhere]
2. (0,2)(1,3) [Correct]
3. (1,3)(0,2) [Same as 2]
Может кто-нибудь предложить мне способ генерировать все возможные комбинации, как только у меня есть пары.
algorithms
graphics
data-structures
computational-geometry
operating-systems
process-scheduling
algorithms
sorting
database-theory
relational-algebra
finite-model-theory
logic
automata
linear-temporal-logic
buchi-automata
complexity-theory
np-complete
decision-problem
machine-learning
algorithms
pattern-recognition
logic
formal-languages
formal-grammars
context-free
Анкит
источник
источник
Ответы:
Один прямой путь - это рекурсивная процедура, которая выполняет следующие действия при каждом вызове. Входные данные для процедуры - это список пар, которые уже были выбраны, и список всех пар.
Способ визуализации этого алгоритма заключается в дереве, пути которого представляют собой последовательности неперекрывающихся пар. Первый уровень дерева содержит все пары, которые содержат 0. Для приведенного выше примера дерево
В этом примере все пути через дерево фактически дают правильные коллекции, но, например, если бы мы пропустили пару (1,2), то самый правый путь имел бы только один узел и соответствовал бы неудаче поиска на шаге 3.
Поисковые алгоритмы этого типа могут быть разработаны для многих похожих задач перечисления всех объектов определенного типа.
Было высказано предположение, что, возможно, ОП означало, что на входе присутствуют все пары, а не только их набор, как говорится в вопросе. В этом случае алгоритм намного проще, потому что больше нет необходимости проверять, какие пары разрешены. Нет необходимости создавать множество всех пар; следующий псевдокод будет делать то, что спросил OP. Здесь - входной номер, «список» начинается с пустого списка, а «охватываемый» - это массив длиной n, инициализированный равным 0. Его можно сделать несколько более эффективным, но это не является моей непосредственной целью.n n
источник
Вы можете решить это итеративно. Предположим, у вас есть все решения для диапазона [ 0 , n ) . Тогда вы можете легко построить решения S n + 2 из S n . Размер растет очень быстро с n , поэтому лучше написать генератор, а не хранить все наборы в памяти, см. Пример Python ниже.SN [ 0 , n ) Sn + 2 SN N
Вы можете перечислить все пары, позвонив
источник
Обновление : мой предыдущий ответ касался двудольных графов, о которых ОП не спрашивал. Я оставляю это пока, как связанную информацию. но более важная информация относится к идеальным соответствиям в двудольных графах.
В связи с этим есть хороший опрос Проппа, в котором описывается прогресс (до 1999 года). Некоторые идеи из этой статьи и соответствующие ссылки могут оказаться полезными. TL; DR - это сложно :)
--- начало старого ответа
Обратите внимание, что вы просите перечислить все возможные идеальные совпадения на двудольном графе. Для этого существует множество различных алгоритмов, и, в частности, один из более свежих - из ISAAC 2001 .
Основная идея состоит в том, чтобы найти одно идеальное соответствие с использованием сетевых потоков, а затем неоднократно изменять его с помощью чередующихся циклов (дополнительную информацию см. В главе любого учебника по алгоритмам, посвященной сетевым потокам).
источник
Каждая пара, которую вы выбираете, удаляет два ряда, из которых вы больше не можете выбрать. Эта идея может быть использована для настройки рекурсивного алгоритма (в Scala):
Это, безусловно, можно выразить более эффективным способом. В частности, идея отсутствия необходимости рассматривать целые строки для комбинаций не используется при вызове
filter
.источник
Хотя уже есть много прекрасных ответов на этот вопрос, я думаю, что было бы неплохо указать на основной, общий трюк позади них.
Намного проще генерировать уникальные комбинации, если вы можете иметь общий порядок элементов, которые нужно объединить . Таким образом, уникальность гарантируется, если мы разрешаем только отсортированные комбинации. Нетрудно также сгенерировать отсортированные комбинации - просто выполните обычный поиск перечисления методом грубой силы, но на каждом шаге выбирайте только элементы, размер которых больше уже выбранных на каждом шаге.
Дополнительным осложнением в этой конкретной задаче является желание получить только комбинации длины n / 2 (максимальная длина). Это не сложно сделать, если мы выберем хорошую стратегию сортировки. Например, как указано в ответе Карла Маммета, если мы рассмотрим лексикографическую сортировку (сверху вниз, слева направо на диаграмме в вопросе), мы получим стратегию всегда брать следующий элемент так, чтобы его первая цифра была наименьшее количество неиспользованных номеров
Мы также можем расширить эту стратегию, если мы хотим генерировать последовательности другой длины. Просто помните, что всякий раз, когда мы выбираем следующий элемент, чье первое число не наименьшее из доступных, мы исключаем появление одной или нескольких строк элементов в отсортированной подпоследовательности, поэтому максимальная длина предварительной перестановки соответственно уменьшается.
источник
Я не уверен, если это то, что вы спрашиваете, но, как я понимаю, у вас есть все( н2) [ n ] = { 1 , ⋯ , n } [ п ] N КN N
источник