Generando combinaciones a partir de un conjunto de pares sin repetición de elementos.

Tengo un conjunto de pares. Cada par tiene la forma (x, y) de modo que x, y pertenecen a enteros del rango [0,n).

Entonces, si n es 4, entonces tengo los siguientes pares:

(0,1) (0,2) (0,3)
(1,2) (1,3) 
(2,3) 

Ya tengo las parejas. Ahora, tengo que construir una combinación usando n/2pares de modo que ninguno de los enteros se repita (en otras palabras, cada entero aparece al menos una vez en la combinación final). Los siguientes son ejemplos de una combinación correcta e incorrecta para una mejor comprensión.

 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]

¿Puede alguien sugerirme una forma de generar todas las combinaciones posibles, una vez que tenga los pares?

Una forma directa es un procedimiento recursivo que hace lo siguiente en cada invocación. La entrada al procedimiento es una lista de pares que ya han sido elegidos y una lista de todos los pares.

1. Calcule el número más pequeño que aún no está cubierto por la lista de entrada. Para la primera invocación, esto será 0, por supuesto, porque no se han elegido pares.
2. Si todos los números están cubiertos, tiene una combinación correcta, imprímala y devuelva el paso anterior. De lo contrario, el número más pequeño que se descubre es el objetivo al que apuntaremos.
3. Busque entre los pares buscando una forma de cubrir el número objetivo. Si no hay ninguno, simplemente regrese al nivel anterior de recursión.
4. Si hay una manera de cubrir el número objetivo, elija la primera forma y llame de forma recursiva a todo el procedimiento nuevamente, con el par recién seleccionado y agregue a la lista de pares elegidos.
5. Cuando eso regrese, busque la siguiente forma de cubrir el número objetivo con un par, sin superponer un par elegido previamente. Si encuentra uno, selecciónelo y vuelva a llamar recursivamente al siguiente procedimiento.
6. Continúe los pasos 4 y 5 hasta que no haya más formas de cubrir el número objetivo. Ir a través de la lista completa de pares. Cuando no haya más opciones correctas, regrese al nivel anterior de la recursión.

La forma de visualizar este algoritmo es con un árbol cuyas rutas son secuencias de pares no superpuestos. El primer nivel del árbol contiene todos los pares que contienen 0. Para el ejemplo anterior, el árbol es

           Raíz
             El |
     ----------------
     El | El | El |
   (0,1) (0,2) (0,3)
     El | El | El |
   (2,3) (1,3) (1,2)

En este ejemplo, todas las rutas a través del árbol en realidad dan colecciones correctas, pero, por ejemplo, si omitimos el par (1,2), la ruta más a la derecha tendría solo un nodo y correspondería a la búsqueda en el paso 3 que falla.

Los algoritmos de búsqueda de este tipo pueden desarrollarse para muchos problemas similares de enumerar todos los objetos de un tipo particular.

Se sugirió que tal vez el OP significaba que todos los pares estaban en la entrada, no solo un conjunto de ellos como dice la pregunta. En ese caso, el algoritmo es mucho más fácil porque ya no es necesario verificar qué pares están permitidos. Ni siquiera es necesario generar el conjunto de todos los pares; El siguiente pseudocódigo hará lo que el OP solicitó. Aquí es el número de entrada, "lista" comienza como una lista vacía, y "cubierto" es una matriz de longitud n inicializada a 0. Podría hacerse algo más eficiente, pero ese no es mi objetivo inmediato.$n$$n$

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$

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

Puede enumerar todos los pares llamando

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

Actualización : mi respuesta anterior trataba con gráficos bipartitos, sobre los cuales el OP NO estaba preguntando. Lo dejo por ahora, como información relacionada. pero la información más pertinente se relaciona con coincidencias perfectas en gráficos no bipartitos.

A este respecto, hay una buena encuesta realizada por Propp que describe el progreso (hasta 1999). Algunas de las ideas en ese artículo, y los enlaces relacionados, pueden resultar útiles. el TL; DR es - es complicado :)

--- Inicio de la respuesta anterior

Tenga en cuenta que lo que está pidiendo hacer es enumerar todas las coincidencias perfectas posibles en un gráfico bipartito. Hay muchos algoritmos diferentes para hacer esto, y en particular uno de los más recientes es de ISAAC 2001 .

La idea básica es encontrar una coincidencia perfecta mediante el uso de flujos de red, y luego modificar esto repetidamente mediante ciclos alternos (consulte el capítulo de cualquier libro de texto de algoritmos sobre flujos de red para obtener más información).

Cada par que elijas elimina dos filas de las que ya no puedes elegir. Esta idea se puede utilizar para configurar un algoritmo recursivo (en 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
  }
}

Esto ciertamente se puede expresar de una manera más eficiente. En particular, la llamada a no utiliza la idea de no tener que considerar filas completas para combinaciones filter.

Si bien hay muchas respuestas encantadoras a la pregunta, creo que sería bueno señalar el truco básico y general detrás de ellas.

Es mucho más fácil generar combinaciones únicas si puede tener un orden total de los elementos que se combinarán. . De esta forma, la unicidad está garantizada si solo permitimos combinaciones ordenadas. Tampoco es difícil generar las combinaciones ordenadas: solo haga la búsqueda de enumeración de fuerza bruta habitual, pero en cada paso solo elija elementos más grandes que los que ya se seleccionaron en cada paso.

La complicación adicional en este problema particular es el deseo de obtener solo las combinaciones de longitud n / 2 (la longitud máxima). Esto no es difícil de hacer si decidimos una buena estrategia de clasificación. Por ejemplo, como se señala en la respuesta de Carl Mummet, si consideramos un tipo lexicográfico (de arriba a abajo, de izquierda a derecha en el diagrama de la pregunta) derivamos la estrategia de tomar siempre el siguiente elemento para que su primer dígito sea el El número más pequeño aún no utilizado.

También podemos extender esta estrategia si queremos generar secuencias de otras longitudes. Solo recuerde que cada vez que elegimos un siguiente elemento cuyo primer número no es el más pequeño disponible, descartamos que una o más filas de elementos aparezcan en la subsecuencia ordenada, por lo que la longitud máxima de la prermutación disminuye en consecuencia.

$n \choose 2$$[n] = \{1, \cdots, n\}$$[n]$$n$$K_n$$n$

$[n]$$\mathsf{Perm}(K_n)$

$\mathsf{\#P\text{-}complete}$ $K_n$$\frac{n!}{2^{\frac{n}{2}}}$

$[n]$