Generieren von Kombinationen aus einer Menge von Paaren ohne Wiederholung der Elemente

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

  •  16-10-2019
  •  | 
  •  

Frage

Ich habe eine Menge von Paaren.Jedes paar ist von der form (x,y) derart, dass x,y gehören zu ganzen zahlen aus dem Bereich [0,n).

Also, wenn n 4 ist, dann habe ich die folgenden Paare:

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

Ich habe bereits die Paare.Nun, ich habe zu bauen eine Kombination mit n/2 Paare, so dass keine der ganzen zahlen wiederholt werden (in anderen Worten, jede ganze Zahl erscheint mindestens einmal in der abschließenden Kombination).Die folgenden Beispiele für eine richtige und eine falsche Kombination für ein besseres Verständnis

 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]

Kann jemand empfehlen, mir einen Weg zu erzeugen, die alle möglichen Kombinationen, einmal habe ich die Paare.

War es hilfreich?

Lösung

Ein direkter Weg ist ein rekursives Verfahren, das bei jedem Aufruf Folgendes ausführt. Die Eingabe für das Verfahren ist eine Liste der bereits ausgewählten Paare und eine Liste aller Paare.

  1. Berechnen Sie die kleinste Zahl, die nicht bereits von der Eingabeliste abgedeckt ist. Für den ersten Aufruf wird dies natürlich 0 sein, da keine Paare ausgewählt wurden.
  2. Wenn alle Zahlen abgedeckt sind, haben Sie eine korrekte Kombination, drucken Sie sie aus und senden Sie den vorherigen Schritt zurück. Andernfalls ist die kleinste Anzahl, die entdeckt wird, das Ziel, das wir anstreben werden.
  3. Suchen Sie durch die Paare, um nach einer Möglichkeit zu suchen, die Zielnummer abzudecken. Wenn es keine gibt, kehren Sie einfach auf die vorherige Rekursion zurück.
  4. Wenn es eine Möglichkeit gibt, die Zielnummer abzudecken, wählen Sie den ersten Weg aus und rufen Sie die gesamte Prozedur erneut auf, wobei das Paar gerade die Liste der ausgewählten Paare ausgewählt hat.
  5. Wenn das zurückkehrt, suchen Sie nach dem nächste Weg, um die Zielnummer mit einem Paar abzudecken, ohne ein zuvor ausgewähltes Paar zu überlappen. Wenn Sie einen finden, wählen Sie es aus und rufen Sie erneut die nächste Prozedur an.
  6. Setzen Sie die Schritte 4 und 5 fort, bis es keine Möglichkeiten gibt, die Zielnummer abzudecken. Gehen Sie die gesamte Liste von Paaren durch. Wenn es keine korrekten Entscheidungen mehr gibt, kehren Sie auf die vorherige Ebene der Rekursion zurück.

Der Weg zur Visualisierung dieses Algorithmus besteht bei einem Baum, dessen Pfade Sequenzen nicht überlappender Paare sind. Die erste Ebene des Baumes enthält alle Paare, die 0 enthalten. Für das obige Beispiel ist der Baum

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

In diesem Beispiel geben alle Pfade durch den Baum tatsächlich korrekte Sammlungen, aber wenn wir das Paar (1,2) auslassen, hätte der rechte Pfad nur einen Knoten und entspricht der Suche in Schritt 3 fehlgeschlagen.

Suchalgorithmen dieses Typs können für viele ähnliche Probleme bei der Aufzählung aller Objekte eines bestimmten Typs entwickelt werden.

Es wurde vermutet, dass das OP das bedeutet alle Paare sind in der Eingabe, nicht nur ein Satz von ihnen, wie die Frage heißt. In diesem Fall ist der Algorithmus viel einfacher, da es nicht mehr erforderlich ist, zu überprüfen, welche Paare zulässig sind. Es ist nicht einmal notwendig, den Satz aller Paare zu erzeugen. Der folgende Pseudocode erledigt das, was das OP gefragt hat. Hier ist $ n $ die Eingabenummer, "Liste" beginnt als leere Liste und "abgedeckt" ist eine Reihe von Länge $ n $ initialisiert auf 0. Es könnte etwas effizienter gemacht werden, aber das ist nicht mein unmittelbares Ziel. 

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

Andere Tipps

Sie können es iterativ lösen. Angenommen, Sie haben alle Lösungen $ S_N $ für den Bereich $ [0, n) $. Dann können Sie die Lösungen $ s_ {n+2} $ aus $ s_n $ problemlos konstruieren. Die Größe wächst mit $ n $ extrem schnell, daher kann es gut sein, einen Generator zu schreiben, anstatt alle Sätze im Speicher zu halten. Siehe Python -Beispiel unten.

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

Sie können alle Paare durch Anruf auflisten

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

Aktualisieren: Meine frühere Antwort befasste sich mit zweiparteilen Graphen, nach denen das OP nicht gefragt hat. Ich lasse es vorerst als verwandte Informationen. Die relevanteren Informationen beziehen sich jedoch auf perfekte Übereinstimmungen in nicht -partiten Graphen.

In dieser Hinsicht, Es gibt eine schöne Umfrage von Propp Das beschreibt den Fortschritt (bis 1999). Einige der Ideen in diesem Artikel und die damit verbundenen Links könnten sich als nützlich erweisen. Das tl; dr ist - es ist schwierig :)

--- Beginn der alten Antwort

Beachten Sie, dass Sie alle möglichen perfekten Übereinstimmungen in einem zweigliedrigen Diagramm aufzählen können. Es gibt viele verschiedene Algorithmen dafür, und insbesondere eines der neueren stammt aus Isaac 2001.

Die Grundidee besteht darin, eine perfekte Übereinstimmung mithilfe von Netzwerkflüssen zu finden und diese dann wiederholt mithilfe von Wechselzyklen zu ändern (weitere Informationen finden Sie in einem Lehrbuchkapitel für Algorithmen für weitere Informationen).

Jedes Paar, das Sie auswählen, beseitigt zwei Reihen, aus denen Sie nicht mehr auswählen können. Diese Idee kann verwendet werden, um einen rekursiven Algorithmus (in Scala) einzurichten:

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

Dies kann sicherlich effizienter ausgedrückt werden. Insbesondere wird die Idee, ganze Zeilen für Kombinationen in Betracht zu ziehen filter.

Während die Frage bereits viele schöne Ansewers gibt, wäre es schön, auf den grundlegenden allgemeinen Trick hinter ihnen hinzuweisen.

Es ist viel einfacher, einzigartige Kombinationen zu generieren, wenn Sie eine Gesamtbestellung der Elemente kombinieren können. Auf diese Weise ist die Einzigartigkeit garantiert, wenn wir nur sortierte Kombinationen zulassen. Es ist auch nicht schwierig, die sortierten Kombinationen zu generieren - einfach die übliche Brute -Force -Aufzählungssuche durchführen, aber bei jedem Schritt wählen Sie nur Elemente größer als diejenigen, die bereits bei jedem Schritt ausgewählt wurden.

Die zusätzliche Komplikation in diesem speziellen Problem ist der Wunsch, nur die Kombinationen von Länge N/2 (maximaler Länge) zu erhalten. Dies ist nicht schwer zu tun, wenn wir uns für eine gute Sortierstrategie entscheiden. Wie in Carl Mummets Antwort beispielsweise hervorgeht, beachten wir, wenn wir eine lexikografische Art (Top-Down, linksgerechter im Diagramm in der Frage) in Betracht ziehen kleinste noch ungenutzte Nummer.

Wir können diese Strategie auch erweitern, wenn wir Sequenzen anderer Längen generieren möchten. Denken Sie daran, dass wenn wir ein nächstes Element auswählen, dessen erste Zahl nicht die kleinste verfügbare ist, eine oder mehrere Elementreihen ausschließen, wenn wir in der sortierten Subsequenz erscheinen, sodass die maximale Länge der Promination entsprechend entsprechend abnimmt.

Ich bin nicht sicher, ob dies ist, was Sie Fragen sich aber, wie ich verstehe, haben Sie alle $n \choose 2$ ungeordnete Paare von $[n] = \{1, \cdot \ prod_, n\}$ und zählen möchten, die Liste aller Paare, die Abdeckung der set - $[n]$, wobei $n$ eine gerade Zahl ist.Wir können dies so vorstellen, als edge-Abdeckungen von $K_n$, der vollständige graph auf $n$ Ecken.

Darüber hinaus ist die Frage scheint zu unterstellen, dass jede Zahl in $[n]$ erscheint nur einmal in der Liste.In diesem Fall, wir sind nur die Abdeckungen, die sind perfekt passende.Die Anzahl der matching in einem Graphen ist gleich der permanent seiner Nachbarschaft-matrix.Also müssen wir berechnen $\mathsf{Perm}(K_n)$.

Es ist bekannt, dass permanent $\mathsf{\#P ext{-}complete}$ , aber dies ist im Allgemeinen Fall.Für $K_n$ gibt es $\frac{n!}{2^{\frac{n}{2}}}$ solche Listen.

Der einfachste Weg, zu generieren alle diese ist fix perfekt passende und wenden Sie dann eine permutation von $[n]$, aber dies erzeugt viele Duplikate.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top