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

28

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.

Ankit
fonte
Talvez usando uma matriz 2D para representar seus pares. As combinações válidas correspondem a uma seleção de n células da matriz, de modo que cada linha e coluna contenha exatamente 1 célula selecionada.
31512 Joe
4
Você está dizendo que a entrada é o conjunto de todos os pares? Nesse caso, basta dizer que a entrada é simplesmente . n
Rrigig 6/03/12
2
é sempre par? Caso contrário, as instruções "nenhum dos números inteiros são repetidos" e "cada número inteiro aparece pelo menos uma vez na combinação final" são contraditórias. n
Dmytro Korduban
11
mesmo problema que @rgrig: a entrada é todos os pares não ordenados ou é um conjunto arbitrário de pares possíveis? Se forem todos os pares, basta dizer que a entrada é , não é necessário fornecer a lista. n
Kaveh
11
Você está interessado em gerar todas as combinações perfeitas do gráfico em pontos definidos pelo seu conjunto inicial de pares. Além disso, parece que você considera esse gráfico o gráfico completo desses pontos. Sua pergunta seria mais clara se você mencionasse isso. Existem ( n - 1 ) ! ! : = 1 × 3 × 5 × × ( n - 1 ) tais emparelhamentos. n(n-1 1)!!: =1 1×3×5××(n-1 1)
Marc van Leeuwen

Respostas:

14

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.nn

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
fonte
Isso deve funcionar, mas provavelmente não é a maneira mais eficiente de fazer isso.
31412 Joe
2
No final, o ponto é de alguma forma enumerar os caminhos dessa árvore. Se o número de pares na lista de entrada for muito menor que o número possível de pares, esse tipo de algoritmo será perfeitamente eficiente, principalmente se algumas tabelas de hash forem usadas para ajudar a lembrar quais números já foram abordados em cada etapa, para que isso pode ser consultado em tempo constante.
Carl Mummert
Se a lista usar ponteiros, os links de dança de Knuth valem uma olhada. Quando você retornar, faça uma chamada recursiva e precisará restaurar o estado anterior da lista.
Uli
10

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.Sn[0 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] ] )

Você pode listar todos os pares chamando

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

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

Suresh
fonte
O gráfico bipartido consiste nos dois conjuntos com etiquetas dadas [0, N), e há uma aresta (i, j) se e só se (i = j)!
Joe
nKn
2
o permanente calcula a resposta. mas o OP quer enumerá-los
Suresh
todos eles são isomórficos devido à estrutura do gráfico; portanto, pensar em aplicar permutações pode ser uma boa ideia (mas o problema é que ele criará duplicatas).
Kaveh
4

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.

Rafael
fonte
Isso também não retornará combinações que não incluem todos os números, mas que não podem ser estendidas porque não há pares na sequência original que possam estendê-los? Nesse caso, essas combinações precisam ser filtradas.
Carl Mummert
n2N
(0 0,1 1)n=4
Sim. Mas, como eu disse, minha resposta lida com o cenário proposto pelo OP, ou seja, sem contribuições arbitrárias.
Raphael
Enquanto eu leio a pergunta original, trata-se de um conjunto arbitrário de pares, o OP nunca diz que todos os pares são possíveis. Mas concordo que o OP poderia ser mais claro sobre isso.
Carl Mummert
4

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.

hugomg
fonte
3

(n2)[n]={1 1,,n}[n]nKnn

[n]Perm(Kn)

#P-compeuete Knn!2n2

[n] mas isso irá gerar muitas duplicatas.

Kaveh
fonte