Создание комбинаций из набора пар без повторения элементов

https://cs.stackexchange.com/questions/11

algorithms

16-10-2019
|

Вопрос

У меня есть набор пар. Каждая пара имеет форму (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]

Может ли кто -нибудь предложить мне способ генерировать все возможные комбинации, как только у меня будут пары.

Решение

Одним из прямых способов является рекурсивная процедура, которая выполняет следующее при каждом вызовах. Вход в процедуру - это список пар, которые уже были выбраны, и список всех пар.

Вычислите наименьшее число, которое еще не охватывает список вводов. Для первого вызова, это будет 0, конечно, потому что не было выбрано никаких пар.
Если все цифры покрыты, у вас есть правильная комбинация, распечатайте ее и верните предыдущий шаг. В противном случае, наименьшее, что обнаружено, - это цель, к которой мы стремимся.
Поиск через пары в поисках способа покрыть целевой номер. Если нет, то просто вернитесь на предыдущий уровень рекурсии.
Если есть способ покрыть целевой номер, выберите первый путь и снова вызовите всю процедуру, и только что выбранная пара добавьте в список выбранных пар.
Когда это возвращается, ищите следующий Способ покрыть целевой номер парой, не перекрывая ранее выбранную пару. Если вы найдете один, выберите его и снова рекурсивно вызовите следующую процедуру.
Продолжайте шаги 4 и 5, пока не будет больше способов покрыть целевой номер. Пройдите весь список пар. Когда нет более правильных вариантов, вернитесь на предыдущий уровень рекурсии.

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

           Root
             |
     ----------------
     |       |       |
   (0,1)   (0,2)   (0,3)
     |       |       |
   (2,3)   (1,3)   (1,2)

В этом примере все пути через дерево на самом деле дают правильные коллекции, но, например, если мы оставим пару (1,2), тогда самый правый путь будет иметь только один узел и будет соответствовать поиску на шаге 3, выполняющем сбой.

Алгоритмы поиска этого типа могут быть разработаны для многих подобных задач перечисления всех объектов конкретного типа.

Было высказано предположение, что, возможно, ОП означал, что все Пары находятся на входе, а не просто набор из них, как говорится в вопросе. В этом случае алгоритм намного проще, потому что больше не нужно проверять, какие пары разрешены. Даже не нужно генерировать набор всех пар; Следующий псевдокод сделает то, что спросил ОП. Здесь $ n $ - это входной номер, «список» начинается как пустой список, а «покрытый» - это массив длины $ n n $, инициализированные к 0. Это может быть сделано несколько более эффективным, но это не моя ближайшая цель.

sub cover {
  i = 0;
  while ( (i < n) && (covered[i] == 1 )) {
   i++;
  }
  if ( i == n ) { print list; return;}
  covered[i] = 1;
  for ( j = 0; j < n; j++ ) {
    if ( covered[j] == 0 ) {
      covered[j] = 1;
      push list, [i,j];
      cover();
      pop list;
      covered[j] = 0;
    }
  }
  covered[i] = 0;
}

Другие советы

Вы можете решить это итеративно. Предположим, у вас есть все решения $ s_n $ для диапазона $ [0, n) $. Затем вы можете легко построить решения $ s_ {n+2} $ из $ s_n $. Размер растет очень быстро с $ n $, поэтому может быть хорошо писать генератор, а не держать все наборы в памяти, см. Пример Python ниже.

def pairs(n):
    if (n%2==1 or n<2):
        print("no solution")
        return
    if (n==2):
        yield(  [[0,1]]  )
    else:
        Sn_2 = pairs(n-2) 
        for s in Sn_2:
            yield( s + [[n-2,n-1]] )
            for i in range(n/2-1):
                sn = list(s)
                sn.remove(s[i])
                yield( sn + [ [s[i][0], n-2] , [s[i][1], n-1] ] )
                yield( sn + [ [s[i][1], n-2] , [s[i][0], n-1] ] )

Вы можете перечислить все пары, позвонив

for x in pairs(6):
   print(x)

Обновлять: Мой предыдущий ответ рассматривал двухпартийные графики, о которых OP не спрашивал. Я оставляю это на данный момент, как связанная информация. Но более подходящая информация относится к идеальным совпадениям в небитартских графиках.

В этом отношении, есть хороший опрос Propp Это описывает прогресс (до 1999 года). Некоторые из идей в этой статье и связанных ссылок могут оказаться полезными. TL; DR - это сложно :)

--- начало старого ответа

Обратите внимание, что то, что вы просите сделать, это перечислять все возможные идеальные совпадения на двухпартийном графике. Есть много разных алгоритмов для этого, и, в частности, один из самых последних - это из Исаак 2001.

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

Каждая пара, которую вы выбираете, устраняет два ряда, из которых вы больше не можете выбирать. Эта идея может быть использована для настройки рекурсивного алгоритма (в Scala):

def combine(pairs : Seq[(Int,Int)]) : Seq[Seq[(Int, Int)]] = pairs match {
  case Seq() => Seq()
  case Seq(p) => Seq(Seq(p))
  case _ => {
    val combinations = pairs map { case (a,b) => {
      val others = combine(pairs filter { case (c,d) =>
        a != c && a != d && b != c && b != d
      })

      others map { s => ((a,b) +: s) }
    }}

    combinations.flatten map { _.sorted } distinct
  }
}

Это, безусловно, можно выразить более эффективным образом. В частности, идея не учитывать целые ряды для комбинаций не используется при вызове filter.

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

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

Дополнительным осложнением в этой конкретной проблеме является желание получить только комбинации длины N/2 (максимальная длина). Это не сложно сделать, если мы решим хорошую стратегию сортировки. Например, как указывалось в ответе Карла Маммета, если мы рассмотрим лексикографический вид (сверху вниз, слева направо в диаграмме в вопросе), мы получаем стратегию всегда принимать следующий элемент, чтобы его первая цифра была наименьший все еще неиспользованный номер.

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

Я не уверен, что это то, что вы спрашиваете, но, насколько я понимаю, у вас есть все $ n Выберите 2 $ Неупопорядоченные пары $ [n] = {1, cdots, n } $ и хотите подсчитать список Из всех пар, которые охватывают набор $ [n] $, где $ n $ - равномерное число. Мы можем думать об этом как Край-порывы $ k_n $, полный график на вершине $ n $.

Более того, вопрос, похоже, предполагает, что каждый номер в $ [n] $ появляется только один раз в списке. В этом случае мы смотрим только на покрытия, которые Идеальное соответствие. Анкет Количество сопоставления на графике равно постоянный его Матрица смежности. Анкет Таким образом, нам нужно вычислить $ mathsf {perm} (k_n) $.

Известно, что постоянный $ mathsf {#p text {-} opred} $ , но это в общем случае. Для $ k_n $ есть $ frac {n!} {2^{ frac {n} {2}}} $ такие списки.

Самый простой способ создать все это - исправить одно идеальное сопоставление, а затем применить перестановку $ [n] $, но это приведет к множеству дубликатов.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с cs.stackexchange