Zadanie

Otrzymasz dodatnią liczbę całkowitą i musisz wygenerować „ wykres komplementarny ” z tyloma węzłami. Jeśli nie wiesz, czym jest wykres uzupełniający się w Wikipedii, artykuł na pewno Ci nie pomoże, więc poniżej znajdują się dwa wyjaśnienia, techniczne i nietechniczne.

Nietechniczne

Wykres to zestaw węzłów połączonych liniami. Każda para punktów może być połączona jedną linią lub żadną. „Uzupełnienie” wykresu jest wynikiem pobrania wykresu i połączenia wszystkich węzłów, które nie są połączone, i odłączenia wszystkich węzłów, które są.

Samouzupełniający się wykres to wykres, którego dopełnienie można przestawić na kształt oryginału. Poniżej znajduje się przykład komplementarnego wykresu i pokaz tego, jak to zrobić.

Oto wykres z 5 węzłami:

Podkreślimy wszystkie miejsca, do których połączenia mogłyby się udać, za pomocą czerwonych kropkowanych linii:

Teraz znajdziemy uzupełnienie wykresu, zamieniając czerwone i czarne krawędzie:

Nie wygląda to tak jak na oryginalnym wykresie, ale jeśli przesuniemy węzły w ten sposób (każdy krok zamienia dwa węzły):

Otrzymujemy oryginalny wykres! Wykres i jego uzupełnienie są tym samym wykresem

Techniczny

Samouzupełniający się wykres jest wykresem izomorficznym do swojego uzupełnienia.

Dane techniczne

Otrzymasz dodatnią liczbę całkowitą za pomocą dowolnej metody, która najbardziej Ci odpowiada. I będzie wyjściowe wykres w jakikolwiek sposób Państwo uznają za stosowne, to obejmuje, ale nie ogranicza się do sąsiedztwa Matrix Form , adjacency formie wykazu, zdjęcia i oczywiście! Wyprowadzany wykres musi być własnym dopełnieniem i mieć tyle węzłów, ile wejściowych liczb całkowitych. Jeśli taki wykres nie istnieje, musisz podać wartość fałszowania.

To jest golf golfowy i powinieneś dążyć do zminimalizowania liczby bajtów.

Przypadki testowe

Poniżej znajdują się zdjęcia możliwych wyników dla kilku n

4

5

9

Haskell , 77 bajtów

f n=[(a,b)|b<-[1..n],a<-[1..b-1],mod n 4<2,mod(a+(last$b:[a|odd n,n==b]))4<2]

Wypróbuj online!

Wykorzystuje to łatwe do obliczenia jawne kryterium, aby zdecydować, czy krawędź (a,b)należy do wykresu. Tworzy instancję tego algorytmu , z cykliczną permutacją między wartościami modulo 4

4*m -> 4*m+1 -> 4*m+2 -> 4*m+3 -> 4*m

Uwzględniamy krawędzie, których dwa wierzchołki końcowe dodają do 0 lub 1 modulo 4. Zauważ, że cykliczne wierzchołki zgodnie z tą permutacją dodają 2 modulo 4 do sumy wierzchołków na każdym z nich, a zatem zamieniają krawędzie i nie-krawędzie. Daje to permutację wierzchołków, która uzupełnia krawędzie.

Jeśli wykres ma dodatkowy węzeł większy niż wielokrotność 4, zostaje umieszczony w samym cyklu. Uwzględniamy krawędzie, gdy inny wierzchołek jest równy. Dopuszczenie wierzchołków powoduje odwrócenie parzystości, dzięki czemu wykres sam się uzupełnia.

Jeśli liczba wierzchołków nie jest równa 0 lub 1 moduł 4, nie jest możliwy samouzupełniający się wykres, ponieważ na całym wykresie jest nieparzysta liczba krawędzi

Ogólnie rzecz biorąc, oto warunki:

• Jeśli wejście n nie jest 0 lub 1 modulo 4, wypisz pustą listę
• W przeciwnym razie, jeśli n jest parzyste, uwzględnij wszystkie krawędzie (a,b)z a<bi a+brówne 0 lub 1 modulo 4.
• W przeciwnym razie, jeśli n jest nieparzyste, zrób to samo, ale zamiast tego dołącz krawędzie formularza, (a,n)gdy a jest parzyste.

Kod łączy drugie i trzecie przypadków zastępując warunek mod(a+b)4<2ze mod(a+a)4<2gdy oba odd ni b==n.

Brachylog 2 , 24 bajty

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧

Wypróbuj online!

Ta funkcja zwraca parę składającą się z dwóch list przyległości: jednej dla wykresu, jednej dla wykresu dopełniacza. (W interpretatorze Brachylog na TIO możesz poprosić go o ocenę funkcji, a nie pełnego programu, podając Zjako argument wiersza poleceń.) Na przykład dane wyjściowe dla danych wejściowych 5to:

[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

Oto, jak to wygląda jako obraz (pokazujący dwa wykresy):

Jak to zwykle bywa w językach opartych na Prologu, funkcja obsługuje więcej niż jeden wzorzec wywołań. W szczególności, jeśli spróbujesz użyć go jako generatora, wyświetli on wszystkie możliwe samouzupełniające się wykresy z podaną liczbą wierzchołków (chociaż nie dołożyłem żadnych starań, aby ten przypadek był użyteczny, a zwłaszcza wyświetli każdy z nich wykresy wiele razy).

Wyjaśnienie

Jest to w zasadzie tylko opis problemu, pozostawiając implementację Prologa w celu znalezienia najlepszej metody jego rozwiązania. (Wątpię jednak, czy w tym konkretnym przypadku użyje algorytmu lepszego niż brutalna siła, więc jest to prawdopodobnie dość nieefektywne, a testy wydają się to potwierdzać, pokazując, że wydajność staje się znacznie gorsza, im większy jest wykres).

{⟦₁⊇Ċ}ᶠpḍ.(\\ᵐcdl?∨?<2)∧
 ⟦₁                       The range [1, 2, …, ?], where ? is the input
   ⊇                      A subset of that range…
    Ċ                     …which has exactly two elements
{    }ᶠ                   A list of everything that fits the above description
{⟦₁⊇Ċ}ᶠ                   All edges that could exist in a ?-element graph
       p                  Find a permutation of these…
        ḍ                 …so that splitting it into two equal parts…
          (       ∨   )   …either:
               dl?          produces ? distinct elements
           \                after transposing it
            \ᵐ              and transposing its elements
              c             and flattening one level;
                          or:
                   ?<2      ? was less than 2
         .             ∧  Once you've found it, . specifies what to output

Nawiasem mówiąc, skończyło się na tym, że spędziłem całe 6 bajtów (¼ programu, znaków (∨?<2)) zajmujących się specjalnymi przypadkami 0 i 1. Frustrujące, ale taka jest natura specjalnych przypadków.

Ta \\ᵐcdl?sekcja jest trochę trudna do zrozumienia, więc oto sprawdzony przykład. Jego celem jest sprawdzenie, czy coś jest wykresem i jego dopełnieniem, przy czym odpowiednie krawędzie na wykresie i dopełnieniu są w tej samej kolejności na listach. Para wykres / uzupełnienie staje się ostatecznym wyjściem programu. Oto przykładowy przypadek:

[[[1,2],[1,3],[1,5],[3,5],[4,5]],[[2,5],[2,3],[2,4],[3,4],[1,4]]]

Transpozycja tego daje nam listę par odpowiednich krawędzi między wykresem a dopełnieniem:

[[[1,2],[2,5]],[[1,3],[2,3]],[[1,5],[2,4]],[[3,5],[3,4]],[[4,5],[1,4]]

Następnie transponujemy elementy listy i spłaszczamy jeden poziom; która daje nam listę par odpowiednich elementów między wykresem a dopełnieniem:

[[1,2],[2,5],[1,2],[3,3],[1,2],[5,4],[3,3],[5,4],[4,1],[5,4]]

Najwyraźniej chcemy tutaj, aby nie było więcej niż 1 para zaczynająca się od każdego elementu (co dowodzi, że elementy wykresu i dopełniacza są w korespondencji 1 do 1). Możemy to niemal zweryfikować, stwierdzając, że lista zawiera dokładnie ?różne elementy (tj. Liczbę różnych elementów równą liczbie wierzchołków). W takim przypadku test kończy się powodzeniem; odrębne elementy to:

[[1,2],[2,5],[3,3],[5,4],[4,1]]

Pozostawia to jednak miejsce na potencjalny problem; jeśli wierzchołek jest całkowicie odłączony na oryginalnym wykresie, jego korespondencja nie zostanie wymieniona, pozostawiając miejsce na zduplikowaną korespondencję z niektórych innych wierzchołków. Jeśli jest to przypadek, wykres uzupełnienie musi mieć przewagę między tym wierzchołku (bez straty ogólności załóżmy, że jest 1), i co drugi wierzchołek, a więc lista będzie zawierać korespondencji [1,2], [1,3], ..., [1, ?]. Gdy ?jest duży, doprowadzi to do większej liczby korespondencji ogółem niż w innym przypadku, więc nie ma problemu. Jedyny problem występuje, gdy ?jest 3 lub niższy, w którym to przypadku dodajemy tylko jedną dodatkową korespondencję (usuwając jedną z1nie pojawia się na wejściu); nie stanowi to jednak problemu w praktyce, ponieważ istnieją 3 możliwe krawędzie na wykresie 3-elementowym, co jest liczbą nieparzystą (podobnie, 1 możliwa krawędź na wykresie 2-elementowym jest również liczbą nieparzystą), a zatem test zakończy się niepowodzeniem na tym \etapie (nie można przetransponować obdartej listy, tzn. tych, których elementy mają różne długości).

BBC BASIC, 161 bajtów

Tokenizowany rozmiar pliku 140 bajtów

Pobierz tłumacza na http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

I.m:IF2ANDm ORm<4P.0:END
r=400n=-2A.m:t=2*PI/n:F.i=1TOn*n:a=i DIVn:b=i MODn:c=b:IFa+b A.2a*=t:b*=t:L.r+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1A.m A.c DRAWr*3,0
N.

Nieskluczony kod

  INPUTm                           :REM get input
  IF2ANDm ORm<4PRINT0:END          :REM if m=4x+2 or 4x+3 or less than 4, print 0 and exit
  r=400                            :REM radius of diagram
  n=-2ANDm                         :REM n = m truncated to an even number
  t=2*PI/n                         :REM t = 1/n turns
  FORi=1TOn*n                      :REM for each combination of vertices
    a=i DIVn                       :REM extract a and b
    b=i MODn                       :REM make a copy of c
    c=b                            :REM if a+b MOD 4 = 2 or 3, convert a and b to angles and draw edge.
    IFa+b AND2 a*=t:b*=t:LINEr+r*SINa,r+r*COSa,r+r*SINb,r+r*COSb:IF 1ANDm ANDc DRAWr*3,0
  NEXT                             :REM if m is odd and c is odd, draw a line to the additional vertex for m=4x+1 input.

Wyjaśnienie

Wykorzystuje ten sam algorytm co Xnor, ale generuje schemat.

Gdzie njest w formie 4x+2lub 4x+3nie ma rozwiązania, ponieważ liczba krawędzi jest nieparzysta.

Gdzie nma postać 4x, układamy wszystkie wierzchołki w okręgu i rysujemy te krawędzie, w których (a+b) mod 4jest 2 lub 3 (nie 0 lub 1, jak w przypadku Xnora, ze względów golfowych. Jest to zatem uzupełnienie rozwiązania podanego przez Xnor.)

Aby zobaczyć to w bardziej obrazowym sensie, bierzemy co drugi wierzchołek i rysujemy krawędzie do wierzchołków 1 i 2 miejsc w kierunku przeciwnym do ruchu wskazówek zegara. To określa nrównoległe kierunki, połowę całości. Następnie dodajemy wszystkie pozostałe krawędzie równolegle do nich.

Uzupełnienie można znaleźć, dodając 1 do obu a i b w każdej specyfikacji krawędzi lub obrazowo, obracając schemat o 1/nzakręt.

Gdzie nma postać 4x + 1 dodajemy kolejny wierzchołek, który jest powiązany z co drugim wierzchołkiem wykresu 4x. Gdyby została umieszczona w środku, symetria diagramu zostałaby zachowana, ale dla jasności wybrałem ją poza głównym okręgiem punktów.

Wynik

Oto kilka pierwszych przypadków dla 4x + 1. przypadki 4x można zobaczyć, usuwając wierzchołek w prawym dolnym rogu i związane z nim krawędzie.

JavaScript (ES6), 191 bajtów

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

Ta funkcja zwraca listę przylegania. Wykorzystuje dwa algorytmy i rozróżnia puste wykresy komplementarne od niepochodzących z wyników, zwracając 0zamiast, []gdy nie ma. Pierwszy algorytm oparty jest na wykresach Rado skonstruowanych przy użyciu predykatu BIT i tworzy prawidłowe wykresy komplementarne rzędu 0, 1, 4 i 5. Drugi algorytm, znaleziony przez naszych przyjaciół z matematyki , konstruuje prawidłowy wykres komplementarny wierzchołka V + 4, stosując dodatek 4-ścieżkowy do prawidłowego wykresu komplementarnego wierzchołka V.

Zaczyna się od sprawdzenia poprawności danych wejściowych w celu potwierdzenia istnienia prawidłowego wykresu uzupełniającego (za pomocą n*~-n/4%1), a jeśli to się nie powiedzie, zwraca 0. Następnie sprawdza, czy n>5i powtarza n-4sprawę, aby skonstruować prawidłowe rozwiązanie niższego rzędu, a następnie stosuje dodatek 4 do zwróconej listy sąsiadów w drodze do łańcucha rekurencji. Wreszcie, jeśli n>5nie jest to prawdą, to iteracje od 0do n-1do xi y, i sprawdza, czy (y>>x)&1jest to prawda. Jeśli tak, to te węzły są sparowane.

Oto bardziej czytelny format funkcji, z operatorami potrójnymi rozszerzonymi do instrukcji if-else i eval()wstawionych:

// precalculate amount of required vertices in v
f = (n, a = [], v = n*~-n / 4) => {
  // if amount is non-integer
  if (v % 1) {
    // no valid complementary graph
    return 0;
  } else {
    if (n > 5) {
      // generate valid (n-4)-order complementary graph
      f(n -= 4, a);
      // apply 4-path addition
      for (i = 0; i < n;)
        a.push([i, n+1],[i++, n+2]);
      a.push([n, ++n], [n, ++n], [n, ++n]);
    } else {
      // construct Rado graph using BIT predicate
      for(l = x = 0; x < n; x++)
        for(y = x; y < n; y++)
          // if amount of pairs is less than required and xth bit of y is high
          if (l < v && (y>>x & 1))
            // vertices x and y should be paired
            a.push([x,y]);
    }
    return a;
  }
};

Próbny

f=(n,a=[],v=n*~-n/4)=>v%1?0:eval(n>5?f(n-=4,a)&&'for(i=0;i<n;)a.push([i,n+1],[i++,n+2]);a.push([n,++n],[n,++n],[n,++n])-v':'for(l=x=0;x<n;x++)for(y=x;y<n;y++)l<v&y>>x&1?l=a.push([x,y]):a')||a

<input type="number" onchange="o.textContent=JSON.stringify(f(this.value))"><pre id="o"></pre>