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

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

  •  16-10-2019
  •  | 
  •  

Question

I possède un ensemble de paires. Chaque paire est de la forme (x, y) de telle sorte que x, y appartiennent à des nombres entiers de la gamme [0,n).

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

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

Je l'ai déjà les paires. Maintenant, je dois construire une combinaison en utilisant des paires de n/2 telle qu'aucun des nombres entiers sont répétées (en d'autres termes, chaque entier apparaît au moins une fois dans la combinaison finale). Voici les exemples d'une bonne et une mauvaise combinaison 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 je les paires.

Était-ce utile?

La solution

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é choisis et une liste de toutes les paires.

  1. Calculer le plus petit nombre ne sont pas déjà couverts par la liste d'entrée. Pour la première invocation, ce sera 0 bien sûr, car aucune paire ont été choisis.
  2. Si tous les numéros sont couverts, vous avez une bonne combinaison, l'imprimer et renvoyer la l'étape précédente. Dans le cas contraire, le plus petit nombre qui est découvert est l'objectif que nous viserons.
  3. Faites une recherche parmi les paires qui cherchent un moyen de couvrir le nombre cible. S'il n'y en a pas, puis juste revenir au niveau précédent de la récursivité.
  4. S'il y a un moyen de couvrir le nombre cible, choisissez la première voie et appeler récursive à nouveau toute la procédure, avec la paire juste pris ajouter à la liste des paires choisies.
  5. Lorsque ce rendement, recherchez les suivant moyen de couvrir le nombre cible avec une paire, sans se chevaucher une paire préalablement choisie. Si vous trouvez un, choisissez et appeler à nouveau récursive la procédure suivante.
  6. Continuer les étapes 4 et 5 jusqu'à ce qu'il n'y a pas d'autres façons de couvrir le nombre cible. Parcourez la liste complète des paires. Quand il n'y a plus de bons choix, retour au niveau précédent de la récursion.

Le moyen de visualiser cet algorithme est un arbre dont les chemins sont des séquences de paires ne se chevauchant pas. Le premier niveau de l'arbre contient toutes les paires contenant 0. Pour l'exemple ci-dessus, l'arbre est 

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

Dans cet exemple, tous les chemins à travers l'arbre donne en fait des collections correctes, mais par exemple, si nous avons quitté la paire (1,2), le chemin n'aurait qu'un extrême droite d'un nœud et correspondraient à la recherche à l'étape 3 à défaut .

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

Il a été suggéré que l'OP signifiait que tous paires sont en entrée, pas seulement un ensemble d'entre eux, comme le dit la question. Dans ce cas, l'algorithme est beaucoup plus facile, car il est plus nécessaire de vérifier les paires sont autorisés. Il 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 $ n $ 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 un peu plus efficace, mais ce n'est pas mon objectif immédiat. 

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;
}

Autres conseils

Vous pouvez résoudre de manière itérative. Supposons que vous ayez toutes les solutions $ S_n $ pour la gamme $ [0, n) $. Ensuite, vous pouvez facilement construire les solutions $ S_ {n + 2} $ de $ S_n $. La taille croît très rapidement avec $ n $, donc il peut être bon d'écrire un générateur plutôt que de tenir tous les jeux en mémoire, voir exemple Python ci-dessous. 

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 des graphiques bipartites, que l'OP ne demandait pas au sujet. Je pars en pour l'instant, que des informations connexes. mais l'information plus pertinente concerne appariements parfaits dans les graphiques nonbipartite.

À cet égard, il y a une belle enquête réalisée par Propp contours progrès (jusqu'en 1999). Certaines des idées dans cet article, et les liens connexes, pourraient se révéler utiles. la TL; DR est - il est délicat:)

--- Début de la vieille réponse

Notez que ce que vous demandez de faire est possible d'énumérer tous les appariements parfaits sur un graphe biparti. Il existe de nombreux algorithmes différents pour ce faire, et en particulier un des plus récents est de ISAAC 2001 .

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

Chaque paire vous prenez deux lignes à partir élimine que vous ne pouvez pas choisir plus. Cette idée peut être utilisée pour configurer un algorithme récursif (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 être exprimé d'une manière plus efficace. En particulier, l'idée de ne pas avoir à considérer des rangées entières pour les combinaisons ne sont pas utilisées par l'appel à filter.

Bien qu'il existe déjà beaucoup de belles ansewers à la question, je pense que ce serait bien de mettre en évidence la base, en général, tour derrière eux.

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 permettons que des combinaisons triées. Il est difficile de ne pas générer les combinaisons triées -. Est-ce que l'habituel recherche d'énumération force brute, mais à chaque étape seulement choisir des éléments plus importants alors ceux qui sont déjà cueillis à 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 sur pointe dans la réponse de Carl Mummet, si l'on considère une sorte lexicographique, (de haut en bas, de gauche à droite dans le schéma de la question) nous dérivons la stratégie de prendre toujours l'élément suivant de sorte que son premier chiffre est la le plus petit nombre encore utilisé.

Nous pouvons également étendre cette stratégie si nous voulons générer des séquences d'autres longueurs. Rappelez-vous que chaque fois que nous prenons un élément suivant dont le premier numéro n'est pas la plus petite règle disponible nous sur une ou plusieurs lignes d'éléments d'apparaître sur la sous-séquence triée, de sorte que la longueur maximale du prermutation diminue en conséquence.

Je ne suis pas sûr que ce soit ce que vous demandez, mais si je comprends bien, vous avez tout $ n \ choose 2 $ paires désordonnées de $ [n] = \ {1, \ cdots, n \} $ et que vous voulez compte la liste de toutes les paires qui couvrent le $ set [n] $ où $ n $ est un nombre pair. Nous pouvons penser à cela comme bord de revêtements $ K_N $, le graphique complet sur $ n $ sommets.

En outre, la question semble supposer que chaque numéro $ [n] $ apparaît une seule fois dans la liste. Dans ce cas, nous ne regardons que les revêtements qui sont correspondance parfaite permanent de sa contiguïté matrice . Nous avons donc besoin de calculer $ \ mathsf {} Perm (K_N) $.

Il est connu que permanent est $ \ mathsf {\ # P \ texte {-}} complète $ , mais cela est dans le cas général. Pour $ K_N il $ sont $ \ frac {n!} {2 ^ {\ frac {n} {2}}} $ de telles listes.

La meilleure façon de générer tous ces est de fixer une correspondance parfaite, puis appliquer une permutation de $ [n] $, mais cela va générer beaucoup de doublons.

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top