Génération de combinaisons à partir d'un ensemble de paires sans répétition d'éléments

J'ai un ensemble de paires. Chaque paire est de la forme (x, y) telle que x, y appartiennent à des entiers de la plage [0,n).

Donc, si le n est 4, alors j'ai les paires suivantes:

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

J'ai déjà les paires. Maintenant, je dois construire une combinaison en utilisant des n/2paires de sorte qu'aucun des entiers ne soit répété (en d'autres termes, chaque entier apparaît au moins une fois dans la combinaison finale). Voici les exemples d'une combinaison correcte et incorrecte pour une meilleure compréhension

 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]

Quelqu'un peut-il me suggérer un moyen de générer toutes les combinaisons possibles, une fois que j'ai les paires.

Une façon directe est une procédure récursive qui effectue les opérations suivantes à chaque appel. L'entrée de la procédure est une liste de paires qui ont déjà été choisies et une liste de toutes les paires.

1. Calculez le plus petit nombre non déjà couvert par la liste d'entrée. Pour la première invocation, ce sera bien sûr 0, car aucune paire n'a été choisie.
2. Si tous les numéros sont couverts, vous avez une combinaison correcte, imprimez-la et retournez à l'étape précédente. Sinon, le plus petit nombre qui est découvert est la cible que nous viserons.
3. Cherchez parmi les paires à la recherche d'un moyen de couvrir le nombre cible. S'il n'y en a pas, revenez simplement au niveau de récursivité précédent.
4. S'il existe un moyen de couvrir le nombre cible, choisissez la première méthode et appelez à nouveau de manière récursive la procédure entière, la paire venant d'être ajoutée s'ajoutant à la liste des paires choisies.
5. Lorsque cela revient, cherchez la prochaine façon de couvrir le nombre cible avec une paire, sans chevaucher une paire précédemment choisie. Si vous en trouvez un, choisissez-le et appelez à nouveau de manière récursive la procédure suivante.
6. Continuez les étapes 4 et 5 jusqu'à ce qu'il n'y ait plus de moyens de couvrir le nombre cible. Parcourez la liste complète des paires. Lorsqu'il n'y a plus de choix corrects, revenez au niveau précédent de la récursivité.

La façon de visualiser cet algorithme est avec un arbre dont les chemins sont des séquences de paires qui ne se chevauchent pas. Le premier niveau de l'arbre contient toutes les paires qui contiennent 0. Pour l'exemple ci-dessus, l'arbre est

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

Dans cet exemple, tous les chemins dans l'arborescence donnent des collections correctes, mais par exemple, si nous omettons la paire (1,2), le chemin le plus à droite n'aurait qu'un seul nœud et correspondrait à l'échec de la recherche à l'étape 3.

Des algorithmes de recherche de ce type peuvent être développés pour de nombreux problèmes similaires d'énumération de tous les objets d'un type particulier.

Il a été suggéré que peut-être le PO signifiait que toutes les paires sont dans l'entrée, pas seulement un ensemble d'entre elles comme le dit la question. Dans ce cas, l'algorithme est beaucoup plus facile car il n'est plus nécessaire de vérifier quelles paires sont autorisées. Il n'est même pas nécessaire de générer l'ensemble de toutes les paires; le pseudocode suivant fera ce que l'OP a demandé. Ici, est le numéro d'entrée, "liste" commence comme une liste vide et "couvert" est un tableau de longueur n initialisé à 0. Il pourrait être rendu un peu plus efficace mais ce n'est pas mon objectif immédiat.$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] ] )

Vous pouvez lister toutes les paires en appelant

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

Mise à jour : ma réponse précédente portait sur les graphes bipartites, que le PO ne demandait pas. Je le laisse pour l'instant, en tant qu'informations connexes. mais les informations les plus pertinentes concernent les correspondances parfaites dans les graphiques non bipartites.

À cet égard, il y a une belle enquête de Propp qui décrit les progrès (jusqu'en 1999). Certaines des idées contenues dans cet article et les liens connexes pourraient s'avérer utiles. le TL; DR est - c'est délicat :)

--- Début de l'ancienne réponse

Notez que ce que vous demandez de faire est d'énumérer toutes les correspondances parfaites possibles sur un graphique bipartite. Il existe de nombreux algorithmes différents pour ce faire, et en particulier l'un des plus récents est celui d' ISAAC 2001 .

L'idée de base est de trouver une correspondance parfaite en utilisant des flux de réseau, puis de la modifier à plusieurs reprises en utilisant des cycles alternés (voir le chapitre du manuel d'algorithmes sur les flux de réseau pour plus d'informations).

Chaque paire que vous choisissez élimine deux rangées desquelles vous ne pouvez plus choisir. Cette idée peut être utilisée pour configurer un algorithme récursif (dans 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
  }
}

Cela peut certainement s'exprimer de manière plus efficace. En particulier, l'idée de ne pas avoir à considérer des lignes entières pour les combinaisons n'est pas utilisée par l'appel à filter.

Bien qu'il existe déjà de nombreuses réponses intéressantes à la question, je pense qu'il serait bon de souligner l'astuce de base, générale, derrière elles.

Il est beaucoup plus facile de générer des combinaisons uniques si vous pouvez avoir un ordre total des éléments à combiner . De cette façon, l'unicité est garantie si nous n'autorisons que les combinaisons triées. Il n'est pas difficile non plus de générer les combinaisons triées - faites simplement la recherche d'énumération par force brute habituelle, mais à chaque étape, choisissez uniquement des éléments plus grands que ceux déjà sélectionnés à chaque étape.

La complication supplémentaire dans ce problème particulier est le désir d'obtenir uniquement les combinaisons de longueur n / 2 (la longueur maximale). Ce n'est pas difficile à faire si nous décidons d'une bonne stratégie de tri. Par exemple, comme indiqué dans la réponse de Carl Mummet, si nous considérons une sorte lexicographique, (de haut en bas, de gauche à droite dans le diagramme de la question), nous dérivons la stratégie de toujours prendre l'élément suivant afin que son premier chiffre soit le le plus petit nombre encore inutilisé.

Nous pouvons également étendre cette stratégie si nous voulons générer des séquences d'autres longueurs. N'oubliez pas que chaque fois que nous choisissons un élément suivant dont le premier nombre n'est pas le plus petit disponible, nous excluons qu'une ou plusieurs lignes d'éléments apparaissent sur la sous-séquence triée, de sorte que la longueur maximale de la prermutation diminue en conséquence.

paires non ordonnées de$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]$