Generowanie kombinacji z zestawu par bez powtarzania elementów

Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n).

Jeśli więc n wynosi 4, to mam następujące pary:

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

Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita nie była powtarzana (innymi słowy, każda liczba całkowita pojawia się co najmniej raz w ostatecznej kombinacji). Poniżej podano przykłady poprawnej i niepoprawnej kombinacji dla lepszego zrozumienia

 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]

Czy ktoś może zasugerować mi sposób na wygenerowanie wszystkich możliwych kombinacji, gdy tylko będę mieć pary.

Jednym bezpośrednim sposobem jest procedura rekurencyjna, która wykonuje następujące czynności przy każdym wywołaniu. Dane wejściowe do procedury to lista par, które zostały już wybrane, oraz lista wszystkich par.

1. Oblicz najmniejszą liczbę, która nie jest jeszcze objęta listą wprowadzania. Dla pierwszego wywołania będzie to oczywiście 0, ponieważ nie wybrano żadnych par.
2. Jeśli wszystkie liczby są uwzględnione, masz poprawną kombinację, wydrukuj ją i zwróć poprzedni krok. W przeciwnym razie najmniejsza liczba, która zostanie odkryta, to cel, do którego będziemy dążyć.
3. Przeszukuj pary, szukając sposobu na pokrycie liczby docelowej. Jeśli nie ma, to po prostu wróć do poprzedniego poziomu rekurencji.
4. Jeśli istnieje sposób na zakrycie numeru docelowego, wybierz pierwszy sposób i ponownie wywołaj całą procedurę rekurencyjnie, z wybraną parą dodaj do listy wybranych par.
5. Kiedy to powróci, poszukaj następnego sposobu na pokrycie liczby docelowej parą, bez nakładania się na wcześniej wybraną parę. Jeśli znajdziesz taki, wybierz go i ponownie uruchom rekurencyjnie następną procedurę.
6. Kontynuuj kroki 4 i 5, aż nie będzie już więcej sposobów na pokrycie liczby docelowej. Przejrzyj całą listę par. Gdy nie ma już poprawnych wyborów, wróć do poprzedniego poziomu rekurencji.

Sposobem na wizualizację tego algorytmu jest drzewo, którego ścieżki są sekwencjami nienakładających się par. Pierwszy poziom drzewa zawiera wszystkie pary zawierające 0. W powyższym przykładzie drzewo to

           Korzeń
             |
     ----------------
     | | |
   (0,1) (0,2) (0,3)
     | | |
   (2,3) (1,3) (1,2)

W tym przykładzie wszystkie ścieżki przez drzewo faktycznie dają poprawne kolekcje, ale na przykład, jeśli pominiemy parę (1,2), wówczas skrajnie prawa ścieżka będzie miała tylko jeden węzeł i nie powiedzie się wyszukiwanie w kroku 3.

Algorytmy wyszukiwania tego typu można opracować dla wielu podobnych problemów z wyliczaniem wszystkich obiektów określonego typu.

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

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

Możesz wyświetlić listę wszystkich par, dzwoniąc

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

Aktualizacja : moja wcześniejsza odpowiedź dotyczyła grafów dwustronnych, o które OP nie pytał. Zostawiam to na razie, jako powiązane informacje. ale bardziej trafne informacje dotyczą idealnych dopasowań w grafach dwudzielnych.

W związku z tym istnieje przyjemna ankieta przeprowadzona przez Propp, która przedstawia postęp (do 1999 r.). Niektóre pomysły zawarte w tym artykule i powiązane linki mogą okazać się przydatne. TL; DR jest - to trudne :)

--- Początek starej odpowiedzi

Zwróć uwagę, że to, o co prosisz, to wyliczyć wszystkie możliwe idealne dopasowania na dwudzielnym wykresie. Istnieje wiele różnych algorytmów do tego, a w szczególności jeden z najnowszych pochodzi z ISAAC 2001 .

Podstawową ideą jest znalezienie jednego idealnego dopasowania za pomocą przepływów sieciowych, a następnie wielokrotne modyfikowanie go za pomocą naprzemiennych cykli (więcej informacji można znaleźć w rozdziale podręcznika na temat algorytmów przepływów sieciowych).

Każda wybrana para eliminuje dwa rzędy, z których nie można już wybierać. Ten pomysł można wykorzystać do skonfigurowania algorytmu rekurencyjnego (w Scali):

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

Można to z pewnością wyrazić w bardziej wydajny sposób. W szczególności wezwanie do nie jest używane, aby nie brać pod uwagę całych wierszy dla kombinacji filter.

Chociaż istnieje już wiele uroczych odpowiedzi na pytanie, myślę, że fajnie byłoby wskazać na podstawową, ogólną sztuczkę.

Znacznie łatwiej jest generować unikalne kombinacje, jeśli można uzyskać całkowitą kolejność łączonych elementów . W ten sposób wyjątkowość jest gwarantowana, jeśli pozwolimy tylko na posortowane kombinacje. Nie jest też trudno wygenerować posortowane kombinacje - po prostu przeprowadź zwykłe wyszukiwanie wyliczeń siły brutalnej, ale na każdym kroku wybieraj tylko elementy większe niż te już wybrane na każdym kroku.

Dodatkową komplikacją w tym konkretnym problemie jest chęć uzyskania tylko kombinacji długości n / 2 (maksymalna długość). Nie jest to trudne, jeśli zdecydujemy się na dobrą strategię sortowania. Na przykład, jak wskazano w odpowiedzi Carla Mummeta, jeśli weźmiemy pod uwagę rodzaj leksykograficzny (z góry na dół, lewy-prawy na schemacie w pytaniu), otrzymujemy strategię polegającą na tym, aby zawsze przyjmować następny element, tak aby jego pierwszą cyfrą była najmniejsza wciąż nieużywana liczba.

Możemy również rozszerzyć tę strategię, jeśli chcemy generować sekwencje o innych długościach. Pamiętaj tylko, że za każdym razem, gdy wybieramy kolejny element, którego pierwsza liczba nie jest najmniejszą dostępną, wykluczamy pojawienie się jednego lub większej liczby wierszy elementów na posortowanym podsekwencji, więc maksymalna długość wstępnego cięcia odpowiednio się zmniejsza.

Nie jestem pewien, czy o to pytasz, ale jak rozumiem, masz wszystkie nieuporządkowane pary i chcesz policzyć listę wszystkich par, które obejmuje zestaw gdzie jest liczbą parzystą. Można myśleć o tym, jak krawędź pokryć z kompletna wykresu na wierzchołków.$n \choose 2$$[n] = \{1, \cdots, n\}$$[n]$$n$$K_n$$n$

Ponadto wydaje się, że pytanie zakłada, że ​​każda liczba w pojawia się tylko raz na liście. W takim przypadku patrzymy tylko na pokrycia, które są idealnie dopasowane . Liczba dopasowań na wykresie jest równa stałej jego macierzy przylegania . Musimy więc obliczyć .$[n]$$\mathsf{Perm}(K_n)$

Wiadomo, że permanent jest , ale tak jest w ogóle. Dla istnieją takich list. $\mathsf{\#P\text{-}complete}$ $K_n$$\frac{n!}{2^{\frac{n}{2}}}$

Najłatwiejszym sposobem wygenerowania tych wszystkich elementów jest poprawienie jednego idealnego dopasowania, a następnie zastosowanie permutacji ale spowoduje to wygenerowanie wielu duplikatów.$[n]$