Generare combinazioni da una serie di coppie di elementi senza ripetizione

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

  •  16-10-2019
  •  | 
  •  

Domanda

Ho un insieme di coppie. Ogni coppia ha la forma (x, y) tale che x, y appartengono interi della gamma [0,n).

Quindi, se il n è 4, quindi ho le seguenti coppie: 

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

Ho già le coppie. Ora, devo costruire una combinazione usando coppie n/2 in modo tale che nessuno dei numeri interi si ripetono (in altre parole, ogni intero appare almeno una volta nella combinazione finale). Di seguito sono riportati gli esempi di una corretta e una combinazione non corretta per una migliore comprensione 

 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]

Qualcuno mi può suggerire un modo per generare tutte le combinazioni possibili, una volta che ho le coppie.

È stato utile?

Soluzione

Un modo diretto è una procedura ricorsiva che fa seguito ad ogni invocazione. L'input della procedura è una lista di coppie già scelti e un elenco di tutte le coppie.

  1. Calcola il più piccolo numero non già coperte dalla lista di input. Per la prima chiamata, questa sarà 0 naturalmente, perché nessuna coppia sono stati scelti.
  2. Se tutti i numeri sono coperti, si dispone di una combinazione corretta, stamparlo e restituire il passaggio precedente. In caso contrario, il più piccolo numero che viene scoperto è l'obiettivo punteremo per.
  3. una ricerca tra le coppie in cerca di un modo per coprire il numero di destinazione. Se non c'è nessuno, poi basta tornare al precedente livello di ricorsione.
  4. Se c'è un modo per coprire il numero di destinazione, scegliere il primo modo e ricorsivamente chiama nuovamente l'intera procedura, con la coppia appena raccolto metti in lista di coppie selezionate.
  5. Quando che restituisce, look per il Avanti modo per coprire il numero di destinazione con un paio, senza sovrapposizioni di una coppia scelta in precedenza. Se si trova uno, raccoglierlo e di nuovo ricorsivamente chiamare la procedura successiva.
  6. Continua punti 4 e 5 fino a quando non ci sono più modi per coprire il numero di destinazione. Passare attraverso l'intera lista di coppie. Quando ci sono le scelte più corrette, ritorno al livello precedente della ricorsione.

Il modo di visualizzare questo algoritmo è con un albero i cui percorsi sono sequenze di coppie non sovrapposti. Il primo livello dell'albero contiene tutte le coppie contenenti 0. Per l'esempio precedente, l'albero è 

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

In questo esempio tutti i percorsi attraverso l'albero effettivamente dare collezioni corretti, ma per esempio se abbiamo lasciato la coppia (1,2), allora il percorso più a destra avrebbe solo nodo e corrisponderebbe alla ricerca nel passaggio 3 difetto .

Ricerca algoritmi di questo tipo può essere sviluppato per molti problemi simili di enumerare tutti gli oggetti di un determinato tipo.

E 'stato suggerito che forse il PO ha fatto sì che tutti coppie sono in ingresso, non è solo un insieme di loro come la questione dice. In questo caso l'algoritmo è molto più facile perché non è più necessario controllare quali coppie sono consentiti. Non è nemmeno necessario generare l'insieme di tutte le coppie; il seguente pseudocodice farà quello che ha chiesto l'OP. Qui $ n $ è il numero di input, "lista" inizia come una lista vuota, e "coperto" è un array di lunghezza $ n $ inizializzato a 0. Si potrebbe essere reso un po 'più efficiente, ma che non è il mio obiettivo immediato. 

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

Altri suggerimenti

È possibile risolverlo in modo iterativo. Supponiamo di avere tutte le soluzioni $ S_n $ per la gamma di $ [0, n) $. Poi si può facilmente costruire le soluzioni $ s_ {n + 2} $ da $ S_n $. La dimensione cresce molto velocemente con $ n $, quindi potrebbe essere buono per scrivere un generatore piuttosto che per contenere tutti i set in memoria, vedere Python esempio di seguito. 

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

Si possono elencare tutte le coppie chiamando 

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

Aggiorna : la mia risposta in precedenza affrontato grafi bipartiti, che il PO non chiedeva circa. Parto in per ora, come informazioni correlate. ma le informazioni più pertinenti riferisce ad abbinamenti perfetti in grafici nonbipartite.

A questo proposito, c'è un sondaggio bel da Propp che delinea progresso (fino al 1999). Alcune delle idee nello stesso articolo, e dei relativi collegamenti, potrebbe rivelarsi utile. TL; DR è - è ingannevole:)

--- Inizio risposta vecchia

Si noti che quello che stai chiedendo di fare è enumerare tutti i possibili abbinamenti perfetti su un grafo bipartito. Ci sono molti diversi algoritmi per fare questo, e, in particolare, uno di quelli più recenti, è da ISAAC 2001 .

L'idea di base è quella di trovare una corrispondenza perfetta utilizzando flussi di rete, e poi ripetutamente modificare questo utilizzando cicli alternati (vedi eventuali algoritmi libro di testo capitolo sulla rete scorre per maggiori informazioni).

Ogni coppia si sceglie elimina due file da cui non si può prendere più. Questa idea può essere utilizzato per impostare un algoritmo ricorsivo (in 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
  }
}

Questo può certamente essere espresso in modo più efficiente. In particolare, l'idea di non dover considerare intere righe per combinazioni non viene utilizzato dalla chiamata a filter.

Mentre ci sono già molti ansewers belle alla domanda, penso che sarebbe bello per indicare la base, generale, trucco dietro di loro.

È molto più facile da generare combinazioni uniche, se si può avere un ordinamento totale degli elementi da combinare . In questo modo, l'unicità è garantita se permettiamo solo combinazioni ordinati. Non è difficile per generare le combinazioni a cernita -. Basta fare la solita forza bruta di ricerca enumerazione, ma ad ogni passo scegliere solo gli elementi più grandi poi quelle già raccolte ad ogni passo

La complicazione in più in questo particolare problema è il desiderio di ottenere solo le combinazioni di lunghezza n / 2 (la lunghezza massima). Questo non è difficile da fare se si decide su una buona strategia di smistamento. Per esempio, come le punte in risposta di Carl Mummet, se consideriamo una sorta lessicografico, (dall'alto verso il basso, da sinistra a destra nel diagramma in questione) che deriva la strategia di prendere sempre l'elemento successivo in modo che la sua prima cifra è la minor numero ancora inutilizzato.

Si può anche estendere questa strategia, se vogliamo generare sequenze di altre lunghezze. Basta ricordare che ogni volta che si sceglie un elemento successivo il cui primo numero non è il più piccolo disponibile escludiamo uno o più file di elementi di apparire sulla sottosequenza ordinato, in modo che la lunghezza massima del prermutation diminuisce di conseguenza.

Non sono sicuro se questo è quello che chiedete, ma mi pare di capire, avete tutto $ n \ scelgono 2 $ coppia non ordinata di $ [n] = \ {1, \ cdots, n \} $ e vuole contare l'elenco di tutte le coppie che coprono l'insieme $ [n] $ dove $ n $ è un numero pari. Possiamo pensare a questo come edge-rivestimenti di $ K_n $, il grafo completo su $ n $ vertici.

Inoltre, la questione sembra assumere che ogni numero in $ [n] $ appare solo una volta nell'elenco. In questo caso, stiamo solo guardando i rivestimenti che sono perfetta corrispondenza . Il numero di corrispondenza in un grafico è uguale alla permanente della sua adiacenza matrice . Quindi abbiamo bisogno di calcolare $ \ mathsf {} Perm (K_n) $.

E 'noto che permanente è $ \ mathsf {\ # P \ text {-}} completa $ , ma questo è in caso generale. Per $ K_n $ ci sono $ \ frac {n!} {2 ^ {\ frac {n} {2}}} $ tali liste.

Il modo più semplice per generare tutti questi è quello di fissare un abbinamento perfetto e quindi applicare una permutazione di $ [n] $ ma questo genererà molti duplicati.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top