Gerando combinações de um conjunto de pares sem repetição de elementos

Eu tenho um conjunto de pares. Cada par tem a forma (x, y) tal que x, y pertencem a números inteiros do intervalo [0,n).

Portanto, se n é 4, tenho os seguintes pares:

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

Eu já tenho os pares. Agora, eu tenho que construir uma combinação usando n/2pares de forma que nenhum dos números inteiros seja repetido (em outras palavras, cada número inteiro aparece pelo menos uma vez na combinação final). A seguir estão os exemplos de uma combinação correta e incorreta para melhor entendimento

 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]

Alguém pode me sugerir uma maneira de gerar todas as combinações possíveis, uma vez que tenho os pares.

Uma maneira direta é um procedimento recursivo que faz o seguinte em cada chamada. A entrada para o procedimento é uma lista de pares que já foram escolhidos e uma lista de todos os pares.

1. Calcule o menor número ainda não coberto pela lista de entrada. Para a primeira invocação, será 0, é claro, porque nenhum par foi escolhido.
2. Se todos os números estiverem cobertos, você tem uma combinação correta, imprima-a e retorne a etapa anterior. Caso contrário, o menor número descoberto é a meta que almejamos.
3. Pesquise os pares procurando uma maneira de cobrir o número de destino. Se não houver, retorne ao nível anterior de recursão.
4. Se houver uma maneira de cobrir o número de destino, escolha a primeira e recursivamente chame todo o procedimento novamente, com o par escolhido apenas adicionado à lista de pares escolhidos.
5. Quando isso retornar, procure a próxima maneira de cobrir o número de destino com um par, sem sobrepor um par escolhido anteriormente. Se você encontrar um, escolha-o e chame novamente recursivamente o próximo procedimento.
6. Continue as etapas 4 e 5 até que não haja mais maneiras de cobrir o número de destino. Percorra a lista inteira de pares. Quando não houver mais opções corretas, retorne ao nível anterior da recursão.

A maneira de visualizar esse algoritmo é com uma árvore cujos caminhos são sequências de pares não sobrepostos. O primeiro nível da árvore contém todos os pares que contêm 0. No exemplo acima, a árvore é

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

Neste exemplo, todos os caminhos na árvore realmente fornecem coleções corretas, mas, por exemplo, se deixássemos de fora o par (1,2), o caminho mais à direita teria apenas um nó e corresponderia à falha na etapa 3 da pesquisa.

Algoritmos de pesquisa desse tipo podem ser desenvolvidos para muitos problemas semelhantes de enumerar todos os objetos de um tipo específico.

Foi sugerido que talvez o OP significasse que todos os pares estão na entrada, não apenas um conjunto deles, como diz a pergunta. Nesse caso, o algoritmo é muito mais fácil, porque não é mais necessário verificar quais pares são permitidos. Nem é necessário gerar o conjunto de todos os pares; o pseudocódigo a seguir fará o que o OP pediu. Aqui é o número de entrada, "lista" começa como uma lista vazia e "coberto" é uma matriz de comprimento n inicializada como 0. Poderia ser um pouco mais eficiente, mas esse não é meu objetivo imediato.$n$$n$

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

Você pode resolvê-lo iterativamente. Suponha que você tenha todas as soluções para o intervalo [ 0 , n ) . Então você pode construir facilmente as soluções S n + 2 a partir de S n . O tamanho aumenta extremamente rapidamente com n , portanto, pode ser bom escrever um gerador em vez de manter todos os conjuntos na memória, veja o exemplo do Python abaixo.$S_n$$[0,n)$$S_{n+2}$$S_n$$n$

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

Você pode listar todos os pares chamando

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

Atualização : minha resposta anterior tratava de gráficos bipartidos, sobre os quais o OP NÃO estava perguntando. Estou deixando por enquanto, como informações relacionadas. mas as informações mais pertinentes estão relacionadas a combinações perfeitas em gráficos não bipartidos.

Nesse sentido, há uma boa pesquisa da Propp que descreve o progresso (até 1999). Algumas das idéias contidas neste artigo e os links relacionados podem ser úteis. o TL; DR é - é complicado :)

--- Início da resposta antiga

Observe que o que você está pedindo para fazer é enumerar todas as combinações perfeitas possíveis em um gráfico bipartido. Existem muitos algoritmos diferentes para fazer isso, e um dos mais recentes é o ISAAC 2001 .

A idéia básica é encontrar uma correspondência perfeita usando fluxos de rede e modificá-la repetidamente usando ciclos alternados (consulte qualquer capítulo do livro de algoritmos sobre fluxos de rede para obter mais informações).

Cada par que você escolhe elimina duas linhas das quais você não pode mais escolher. Esta ideia pode ser usada para configurar um algoritmo recursivo (no 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
  }
}

Isso certamente pode ser expresso de uma maneira mais eficiente. Em particular, a idéia de não ter que considerar linhas inteiras para combinações não é usada pela chamada para filter.

Embora já existam muitas respostas encantadoras para a pergunta, acho que seria bom ressaltar o truque básico e geral por trás delas.

É muito mais fácil gerar combinações exclusivas se você puder ter uma ordem total dos elementos a serem combinados . Dessa forma, a exclusividade é garantida se permitirmos apenas combinações ordenadas. Também não é difícil gerar as combinações classificadas - basta fazer a pesquisa de enumeração de força bruta usual, mas em cada etapa escolha apenas elementos maiores que os já selecionados em cada etapa.

A complicação extra nesse problema específico é o desejo de obter apenas as combinações de comprimento n / 2 (o comprimento máximo). Isso não é difícil de fazer se decidirmos uma boa estratégia de classificação. Por exemplo, como apontado na resposta de Carl Mummet, se considerarmos um tipo lexicográfico (de cima para baixo, esquerda e direita no diagrama da pergunta), derivamos a estratégia de sempre pegar o próximo elemento para que seu primeiro dígito seja o menor número ainda não utilizado.

Também podemos estender essa estratégia se queremos gerar sequências de outros comprimentos. Lembre-se de que sempre que escolhemos um próximo elemento cujo primeiro número não é o menor disponível, excluímos que uma ou mais linhas de elementos apareçam na subsequência classificada, portanto o comprimento máximo da pré-comutação diminui de acordo.

$n \choose 2$$[n] = \{1, \cdots, n\}$$[n]$$n$$K_n$$n$

$[n]$$\mathsf{Perm}(K_n)$

$\mathsf{\#P\text{-}complete}$ $K_n$$\frac{n!}{2^{\frac{n}{2}}}$

$[n]$ mas isso irá gerar muitas duplicatas.