Erstellen von Kombinationen aus einer Reihe von Paaren ohne Wiederholung von Elementen

28

Ich habe eine Reihe von Paaren. Jedes Paar hat die Form (x, y), sodass x, y zu ganzen Zahlen aus dem Bereich gehören [0,n).

Wenn also n 4 ist, dann habe ich die folgenden Paare:

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

Ich habe schon die Paare. Jetzt muss ich eine Kombination mit n/2Paaren erstellen, sodass sich keine der ganzen Zahlen wiederholt (mit anderen Worten, jede ganze Zahl kommt in der endgültigen Kombination mindestens einmal vor). Es folgen Beispiele für eine richtige und eine falsche Kombination zum besseren 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 mir jemand einen Weg vorschlagen, alle möglichen Kombinationen zu generieren, sobald ich die Paare habe.

Ankit
quelle
Verwenden Sie möglicherweise ein 2D-Array, um Ihre Paare darzustellen. Gültige Kombinationen entsprechen einer Auswahl von n Array-Zellen, sodass jede Zeile und Spalte genau 1 ausgewählte Zelle enthält.
Joe
4
Wollen Sie damit sagen, dass die Eingabe die Menge aller Paare ist? Wenn ja, dann sollten Sie einfach sagen, dass die Eingabe einfach . n
Rgrig
2
Ist immer gerade? Wenn nicht, sind die Aussagen "keine der ganzen Zahlen wird wiederholt" und "jede ganze Zahl erscheint mindestens einmal in der endgültigen Kombination" widersprüchlich. n
Dmytro Korduban
1
Das gleiche Problem wie bei @rgrig: Ist die Eingabe nur ein ungeordnetes Paar oder eine beliebige Menge möglicher Paare? Wenn es sich um alle Paare handelt, können Sie einfach sagen, dass die Eingabe , ohne dass Sie die Liste angeben müssen. n
Kaveh
1
Sie möchten alle perfekten Übereinstimmungen des Diagramms mit Punkten generieren, die durch Ihre anfängliche Gruppe von Paaren definiert sind. Außerdem scheint es, dass Sie diesen Graphen als den vollständigen Graphen für diese Punkte ansehen. Ihre Frage wäre klarer, wenn Sie das erwähnen würden. Es gibt solche Übereinstimmungen. ( n - 1 ) ! ! : = 1 × 3 × 5 × × ( n - 1 )n(n1)!!:=1×3×5××(n1)
Marc van Leeuwen

Antworten:

14

Ein direkter Weg ist eine rekursive Prozedur, die bei jedem Aufruf Folgendes ausführt. Die Eingabe für die Prozedur ist eine Liste von Paaren, die bereits ausgewählt wurden, und eine Liste aller Paare.

  1. Berechnen Sie die kleinste Zahl, die noch nicht in der Eingabeliste enthalten ist. Für den ersten Aufruf ist dies natürlich 0, da keine Paare ausgewählt wurden.
  2. Wenn alle Zahlen abgedeckt sind, haben Sie eine korrekte Kombination. Drucken Sie sie aus und wiederholen Sie den vorherigen Schritt. Ansonsten ist die kleinste Zahl, die aufgedeckt wird, das Ziel, das wir anstreben werden.
  3. Durchsuchen Sie die Paare nach einer Möglichkeit, die Zielnummer zu erfassen. Wenn es keine gibt, kehren Sie einfach zur vorherigen Rekursionsebene zurück.
  4. Wenn es eine Möglichkeit gibt, die Zielnummer abzudecken, wählen Sie den ersten Weg und rufen Sie die gesamte Prozedur rekursiv erneut auf, wobei das gerade ausgewählte Paar zur Liste der ausgewählten Paare hinzugefügt wird.
  5. Suchen Sie nach dem nächsten Weg, um die Zielnummer mit einem Paar zu überdecken, ohne ein zuvor ausgewähltes Paar zu überlappen. Wenn Sie eine finden, wählen Sie sie aus und rufen Sie die nächste Prozedur erneut rekursiv auf.
  6. Fahren Sie mit den Schritten 4 und 5 fort, bis die Zielnummer nicht mehr erfasst werden kann. Gehen Sie die gesamte Liste der Paare durch. Wenn die Auswahl nicht mehr korrekt ist, kehren Sie zur vorherigen Ebene der Rekursion zurück.

Die Visualisierung dieses Algorithmus erfolgt mit einem Baum, dessen Pfade Sequenzen nicht überlappender Paare sind. Die erste Ebene des Baums enthält alle Paare, die 0 enthalten. Im obigen Beispiel ist der Baum

           Wurzel
             |
     ----------------
     | | |
   (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 an. Wenn wir jedoch beispielsweise das Paar (1,2) weglassen, hat der Pfad ganz rechts nur einen Knoten und entspricht der Suche in Schritt 3, die fehlschlägt.

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


Möglicherweise bedeutete das OP, dass sich alle Paare in der Eingabe befanden und nicht nur eine Gruppe von ihnen, wie in der Frage angegeben. In diesem Fall ist der Algorithmus viel einfacher, da nicht mehr überprüft werden muss, welche Paare zulässig sind. Es ist nicht einmal erforderlich, die Menge aller Paare zu generieren. Der folgende Pseudocode erfüllt die Anforderungen des OP. Hier ist die Eingabenummer, "Liste" beginnt als leere Liste, und "verdeckt" ist ein Array mit der Länge auf 0 initialisiert ist. Es könnte etwas effizienter gestaltet werden, aber das ist nicht mein unmittelbares Ziel.nnn

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
quelle
Dies sollte funktionieren, ist jedoch wahrscheinlich nicht die effizienteste Methode.
Joe
2
Am Ende geht es irgendwie darum, die Pfade dieses Baumes aufzuzählen. Wenn die Anzahl der Paare in der Eingabeliste viel kleiner als die Anzahl der möglichen Paare ist, ist diese Art von Algorithmus vollkommen effizient, insbesondere wenn einige Hash-Tabellen verwendet werden, um sich daran zu erinnern, welche Zahlen bei jedem Schritt bereits behandelt wurden Dies kann in konstanter Zeit abgefragt werden.
Carl Mummert
Wenn die Liste Zeiger enthält, sind Knuths Dancing Links einen Blick wert. Wenn Sie zurückkehren, bilden Sie einen rekursiven Aufruf und müssen den vorherigen Status der Liste wiederherstellen.
uli
10

Sie können es iterativ lösen. Angenommen, Sie haben alle Lösungen für den Bereich . Dann können Sie einfach die Lösungen aus konstruieren . Die Größe wächst mit sehr schnell. Es kann daher sinnvoll sein, einen Generator zu schreiben, anstatt alle Sets im Speicher zu halten (siehe Python-Beispiel unten). [ 0 , n ) S n + 2 S n nSn[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] ] )

Sie können alle Paare auflisten, indem Sie anrufen

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

Update : Meine frühere Antwort befasste sich mit zweigeteilten Graphen, nach denen das OP NICHT fragte. Ich lasse es im Moment als verwandte Informationen. Die sachdienlicheren Informationen beziehen sich jedoch auf perfekte Übereinstimmungen in nicht zweigeteilten Diagrammen.

In dieser Hinsicht gibt es eine schöne Umfrage von Propp , in der die Fortschritte (bis 1999) skizziert werden. Einige der Ideen in diesem Artikel und die zugehörigen Links könnten sich als nützlich erweisen. die TL; DR ist - es ist knifflig :)

--- Beginn der alten Antwort

Beachten Sie, dass Sie alle möglichen perfekten Übereinstimmungen in einem zweigeteilten Diagramm auflisten müssen. Hierzu gibt es viele verschiedene Algorithmen, insbesondere einen neueren aus dem ISAAC 2001 .

Die Grundidee besteht darin, mithilfe von Netzwerkflüssen eine perfekte Übereinstimmung zu finden und diese dann wiederholt mithilfe alternierender Zyklen zu ändern (weitere Informationen finden Sie im Lehrbuch zu Algorithmen im Kapitel zu Netzwerkflüssen).

Suresh
quelle
Das zweigliedrige Diagramm besteht aus den beiden Mengen mit den angegebenen Bezeichnungen [0, n), und es gibt eine Kante (i, j) genau dann, wenn (i! = J)
Joe
Ich glaube nicht, dass Sie Knoten für die Paare setzen müssen, wir können sie als Kanten behandeln. Mit anderen Worten, wir haben ein vollständiges Diagramm für Eckpunkte und möchten alle Eckpunktabdeckungen generieren. Es scheint mir also, dass das Problem darin besteht, die Permanenz des berechnen . K nnKn
Kaveh
2
die bleibende berechnet die Antwort. aber die OP will sie aufzählen
Suresh
Alle von ihnen sind isomorph aufgrund der Graphstruktur, so dass es eine gute Idee sein könnte, über das Anwenden von Permutationen nachzudenken (aber das Problem ist, dass es Duplikate erzeugt).
Kaveh
4

Jedes Paar, das Sie auswählen, eliminiert 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 zum Ausdruck gebracht werden. Insbesondere wird die Idee, nicht ganze Zeilen für Kombinationen berücksichtigen zu müssen, vom Aufruf an nicht verwendet filter.

Raphael
quelle
Gibt dies nicht auch Kombinationen zurück, die nicht jede Zahl enthalten, aber nicht erweitert werden können, weil die ursprüngliche Sequenz keine Paare enthält, die sie erweitern können? In diesem Fall müssen diese Kombinationen herausgefiltert werden.
Carl Mummert
n2N
(0,1)n=4
Ja. Aber wie gesagt, meine Antwort behandelt das vom OP vorgeschlagene Szenario, dh keine willkürlichen Eingaben.
Raphael
Während ich die ursprüngliche Frage lese, handelt es sich um eine beliebige Menge von Paaren, das OP sagt niemals, dass alle Paare möglich sind. Aber ich stimme zu, dass das OP diesbezüglich klarer sein könnte.
Carl Mummert
4

Es gibt zwar bereits viele nette Antworten auf die Frage, aber ich denke, es wäre schön, auf den grundlegenden, allgemeinen Trick hinzuweisen, der dahintersteckt.

Es ist viel einfacher, eindeutige Kombinationen zu generieren, wenn Sie eine Gesamtreihenfolge der zu kombinierenden Elemente haben . Auf diese Weise ist die Eindeutigkeit garantiert, wenn wir nur sortierte Kombinationen zulassen. Es ist auch nicht schwer, die sortierten Kombinationen zu generieren - führen Sie einfach die übliche Brute-Force-Aufzählungssuche durch, sondern wählen Sie bei jedem Schritt nur Elemente aus, die größer sind als die, die bereits bei jedem Schritt ausgewählt wurden.

Die zusätzliche Komplikation bei diesem speziellen Problem ist der Wunsch, nur die Kombinationen der Länge n / 2 (der maximalen Länge) zu erhalten. Dies ist nicht schwer zu tun, wenn wir uns für eine gute Sortierstrategie entscheiden. Wenn wir zum Beispiel, wie in Carl Mummets Antwort ausgeführt, eine lexikografische Sortierung betrachten (von oben nach unten, von links nach rechts im Diagramm der Frage), leiten wir die Strategie ab, immer das nächste Element so zu nehmen, dass dessen erste Ziffer die ist kleinste noch unbenutzte Nummer.

Wir können diese Strategie auch erweitern, wenn wir Sequenzen anderer Länge erzeugen wollen. Denken Sie daran, dass bei der Auswahl eines nächsten Elements, dessen erste Nummer nicht die kleinste verfügbare ist, die Anzeige einer oder mehrerer Elementreihen in der sortierten Teilsequenz ausgeschlossen wird, sodass sich die maximale Länge der Prermutation entsprechend verringert.

hugomg
quelle
3

Ich bin nicht sicher, ob dies das ist, wonach Sie fragen, aber wie ich verstehe, haben Sie alle ungeordnete Paare von und möchten die Liste aller Paare zählen, die decken Sie die Menge wobei eine gerade Zahl ist. Wir können uns dies als Kantenbedeckung von , dem vollständigen Graphen auf Ecken.(n2)[n]={1,,n}[n]nKnn

Außerdem scheint die Frage anzunehmen, dass jede Zahl in nur einmal in der Liste vorkommt. In diesem Fall betrachten wir nur die Abdeckungen, die perfekt zusammenpassen . Die Anzahl der Übereinstimmungen in einem Diagramm entspricht der Permanenz seiner Adjazenzmatrix . Wir müssen also berechnen .[n]Perm(Kn)

Es ist bekannt, dass permanent , aber dies ist im Allgemeinen der Fall. Für gibt es solche Listen. #P-complete Knn!2n2

Der einfachste Weg, um all dies zu generieren, besteht darin, eine perfekte Übereinstimmung festzulegen und dann eine Permutation von anzuwenden. Dadurch werden jedoch viele Duplikate generiert.[n]

Kaveh
quelle