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

28

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.

Ankit
la source
Peut-être en utilisant un tableau 2D pour représenter vos paires. Les combinaisons valides correspondent à une sélection de n cellules du tableau de sorte que chaque ligne et colonne contient exactement 1 cellule sélectionnée.
Joe
4
Voulez-vous dire que l'entrée est l'ensemble de toutes les paires? Si c'est le cas, vous devez simplement dire que l'entrée est simplement . n
rgrig
2
est-il toujours pair? Sinon, les énoncés «aucun des nombres entiers ne sont répétés» et «chaque nombre entier apparaît au moins une fois dans la combinaison finale» sont contradictoires. n
Dmytro Korduban
1
même problème que @rgrig: l'entrée est-elle toutes les paires non ordonnées ou est-ce un ensemble arbitraire de paires possibles? S'il s'agit de toutes les paires, vous pouvez simplement dire que l'entrée est , pas besoin de donner la liste. n
Kaveh
1
Vous souhaitez générer toutes les correspondances parfaites du graphique sur points définis par votre ensemble initial de paires. De plus, il semble que vous considérez ce graphique comme le graphique complet sur ces points. Votre question serait plus claire si vous en parliez. Il y en a ( n - 1 ) ! ! : = 1 × 3 × 5 × × ( n - 1 ) ces correspondances. n(n1)!!:=1×3×5××(n1)
Marc van Leeuwen

Réponses:

14

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.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
la source
Cela devrait fonctionner, mais ce n'est probablement pas le moyen le plus efficace de le faire.
Joe
2
En fin de compte, il s'agit en quelque sorte d'énumérer les chemins de cet arbre. Si le nombre de paires dans la liste d'entrée est beaucoup plus petit que le nombre de paires possibles, ce type d'algorithme sera parfaitement efficace, en particulier si certaines tables de hachage sont utilisées pour aider à se rappeler quels nombres ont déjà été couverts à chaque étape, de sorte que cela peut être interrogé en temps constant.
Carl Mummert
Si la liste utilise des pointeurs, alors les liens de danse de Knuth valent le détour. Lorsque vous revenez depuis un appel récursif et que vous devez restaurer l'état précédent de la liste.
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] ] )

Vous pouvez lister toutes les paires en appelant

for x in pairs(6):
   print(x)
mitchus
la source
6

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

Suresh
la source
Le graphe bipartite se compose des deux ensembles avec des étiquettes données [0, n), et il y a une arête (i, j) si et seulement si (i! = J)
Joe
nKn
2
le permanent calcule la réponse. mais le PO veut les énumérer
Suresh
ils sont tous isomorphes en raison de la structure du graphe, donc penser à appliquer des permutations peut être une bonne idée (mais le problème est qu'il créera des doublons).
Kaveh
4

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.

Raphael
la source
Cela ne retournera-t-il pas également des combinaisons qui n'incluent pas tous les nombres, mais qui ne peuvent pas être étendues car il n'y a pas de paires dans la séquence d'origine qui peuvent les étendre? Si tel est le cas, ces combinaisons doivent être filtrées.
Carl Mummert
n2N
(0,1)n=4
Oui. Mais comme je l'ai dit, ma réponse concerne le scénario proposé par l'OP, c'est-à-dire pas des entrées arbitraires.
Raphael
En lisant la question d'origine, il s'agit d'un ensemble arbitraire de paires, l'OP ne dit jamais que toutes les paires sont possibles. Mais je suis d'accord que le PO pourrait être plus clair à ce sujet.
Carl Mummert
4

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.

hugomg
la source
3

paires non ordonnées de(n2)[n]={1,,n}[n]nKnn

[n]Perm(Kn)

#P-complete Knn!2n2

[n]

Kaveh
la source