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

28

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?

Ankit
fuente
Quizás usando una matriz 2D para representar sus pares. Las combinaciones válidas corresponden a una selección de n celdas de matriz de modo que cada fila y columna contiene exactamente 1 celda seleccionada.
Joe
44
¿Estás diciendo que la entrada es el conjunto de todos los pares? Si es así, debería decir que la entrada es simplemente n .
rgrig
2
¿Es siempre par? Si no, las declaraciones "ninguno de los enteros se repiten" y "cada entero aparece al menos una vez en la combinación final" son contradictorias. n
Dmytro Korduban
1
mismo problema que @rgrig: ¿la entrada es todos pares desordenados o es un conjunto arbitrario de pares posibles? Si se trata de todos los pares, puede decir que la entrada es , no es necesario dar la lista. n
Kaveh
1
Está interesado en generar todas las coincidencias perfectas de la gráfica en puntos definidos por su conjunto inicial de pares. Además, parece que tomas esa gráfica como la gráfica completa en esos puntos. Su pregunta sería más clara si lo mencionara. Hay ( n - 1 ) ! ! : = 1 × 3 × 5 × × ( n - 1 ) tales coincidencias. n(n1)!!:=1×3×5××(n1)
Marc van Leeuwen

Respuestas:

14

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.nn

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;
}
Carl Mummert
fuente
Esto debería funcionar, pero probablemente no sea la forma más eficiente de hacerlo.
Joe
2
Al final, el punto es de alguna manera enumerar los caminos de ese árbol. Si el número de pares en la lista de entrada es mucho menor que el número de pares posibles, este tipo de algoritmo será perfectamente eficiente, particularmente si se usan algunas tablas hash para ayudar a recordar qué números ya se han cubierto en cada paso, de modo que Esto se puede consultar en tiempo constante.
Carl Mummert
Si la lista usa punteros, entonces vale la pena echar un vistazo a los Enlaces de baile de Knuth . Cuando regresas forma una llamada recursiva y tienes que restaurar el estado anterior de la lista.
uli
10

Sn[0,n)Sn+2Snn

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)
mitchus
fuente
6

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

Suresh
fuente
El gráfico bipartito consiste en los dos conjuntos con etiquetas dadas [0, n), y hay un borde (i, j) si y solo si (i! = J)
Joe
nKn
2
El permanente calcula la respuesta. pero el OP quiere enumerarlos
Suresh
todos son isomórficos debido a la estructura gráfica, por lo que pensar en aplicar permutaciones podría ser una buena idea (pero el problema es que creará duplicados).
Kaveh
4

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.

Rafael
fuente
¿No devolverá esto también combinaciones que no incluyen todos los números, pero que no se pueden extender porque no hay pares en la secuencia original que puedan extenderlos? Si es así, esas combinaciones deben ser filtradas.
Carl Mummert
n2N
(0,1)n=4
Sí. Pero como dije, mi respuesta aborda el escenario que propone el OP, es decir, no entradas arbitrarias.
Raphael
Mientras leo la pregunta original, se trata de un conjunto arbitrario de pares, el OP nunca dice que todos los pares son posibles. Pero estoy de acuerdo en que el OP podría ser más claro al respecto.
Carl Mummert
4

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.

hugomg
fuente