W teoria grafówkod Prüfer to unikatowy ciąg liczb całkowitych, które oznacza konkretną drzewo.

Możesz znaleźć kod Prüfera drzewa z następującym algorytmem zaczerpniętym z Wikipedii:

Rozważmy oznaczone drzewo T z wierzchołkami {1, 2, ..., n}. W kroku i usuń liść z najmniejszą etykietą i ustaw i- ty element sekwencji Prüfer, aby był etykietą sąsiada tego liścia.

(Pamiętaj, że ponieważ jest to liść, będzie miał tylko jednego sąsiada).

Powinieneś zatrzymać iterację, gdy na wykresie pozostaną tylko dwa wierzchołki.

Zadanie

Biorąc pod uwagę drzewo oznaczone jako dane wyjściowe, jego kod Prüfer. Możesz wziąć wkład w dowolny rozsądny sposób. Takich jak macierz przylegania lub wbudowana reprezentacja graficzna twoich języków. ( Nie możesz przyjmować danych wejściowych jako kodu Prüfer ).

To jest golf-golf więc powinieneś dążyć do zminimalizowania bajtów w twoim źródle.

Przypadki testowe

Oto niektóre dane wejściowe w ASCII, a ich wyniki poniżej. Nie musisz obsługiwać takiego wejścia ASCII.

    3
    |
1---2---4---6
    |
    5

{2,2,2,4}

1---4---3
    |
5---2---6---7
|
8

{4,4,2,6,2,5}

5---1---4   6
    |       |
    2---7---3

{1,1,2,7,3}

Mathematica, 34 bajty

<<Combinatorica`
LabeledTreeToCode

Ktoś musiał to zrobić ....

Po załadowaniu Combinatoricapakietu funkcja LabeledTreeToCodeoczekuje, że dane wejściowe drzewa będą nieukierowanym wykresem z wyraźnie wymienionymi krawędziami i wierzchołkami; na przykład dane wejściowe w drugim przypadku testowym mogą być Graph[{{{1, 4}}, {{4, 3}}, {{4, 2}}, {{2, 5}}, {{2, 6}}, {{6, 7}}, {{5, 8}}}, {1, 2, 3, 4, 5, 6, 7, 8}].

Python 3, 136 131 127 bajtów

def f(t):
 while len(t)>2:
  m=min(x for x in t if len(t[x])<2);yield t[m][0];del t[m]
  for x in t:m in t[x]and t[x].remove(m)

Pobiera dane wejściowe jako macierz przylegania. Pierwszy przykład:

>>> [*f({1:[2],2:[1,3,4,5],3:[2],4:[2,6],5:[2],6:[4]})]
[2, 2, 2, 4]

Galaretka , 31 bajtów

FĠLÞḢḢ
0ịµÇHĊṙ@µÇCịṪ,
WÇÐĿḢ€ṖṖḊ

Łącze monadyczne, które pobiera listę par węzłów (definiujących krawędzie) w dowolnej kolejności (i każdej w dowolnej orientacji) i zwraca kod Prüfera jako listę.

Wypróbuj online!

W jaki sposób?

FĠLÞḢḢ - Link 1, find leaf location: list of edges (node pairs)
F      - flatten
 Ġ     - group indices by value (sorted smallest to largest by value)
  LÞ   - sort by length (stable sort, so equal lengths remain in prior order)
    ḢḢ - head head (get the first of the first group. If there are leaves this yields
       -   the index of the smallest leaf in the flattened version of the list of edges)

0ịµÇHĊṙ@µÇCịṪ, - Link 2, separate smallest leaf: list with last item a list of edges
0ị             - item at index zero - the list of edges
  µ            - monadic chain separation (call that g)
   Ç           - call last link (1) as a monad (index of smallest leaf if flattened)
    H          - halve
     Ċ         - ceiling (round up)
      ṙ@       - rotate g left by that amount (places the edge to remove at the right)
        µ      - monadic chain separation (call that h)
         Ç     - call last link (1) as a monad (again)
          C    - complement (1-x)
            Ṫ  - tail h (removes and yields the edge)
           ị   - index into, 1-based and modular (gets the other node of the edge)
             , - pair with the modified h
               -    (i.e. [otherNode, restOfTree], ready for the next iteration)

WÇÐĿḢ€ṖṖḊ - Main link: list of edges (node pairs)
W         - wrap in a list (this is so the first iteration works)
  ÐĿ      - loop and collect intermediate results until no more change:
 Ç        -   call last link (2) as a monad
    Ḣ€    - head €ach (get the otherNodes, although the original tree is also collected)
      ṖṖ  - discard the two last results (they are excess to requirements)
        Ḋ - discard the first result (the tree, leaving just the Prüfer Code)

05AB1E , 29 bajtów

[Dg#ÐD˜{γé¬`U\X.å©Ï`XK`ˆ®_Ï]¯

Wypróbuj online!

Wyjaśnienie

[Dg#                           # loop until only 1 link (2 vertices) remain
    ÐD                         # quadruple the current list of links
      ˜{                       # flatten and sort values
        γé                     # group by value and order by length of runs
          ¬`U                  # store the smallest leaf in X
             \X                # discard the sorted list and push X
               .å©             # check each link in the list if X is in that link
                  Ï`           # keep only that link
                    XK`ˆ       # add the value that isn't X to the global list
                        ®_Ï    # remove the handled link from the list of links
                           ]   # end loop
                            ¯  # output global list

Clojure, 111 bajtów

#(loop[r[]G %](if-let[i(first(sort(remove(set(vals G))(keys G))))](recur(conj r(G i))(dissoc G i))(butlast r)))

Wymaga, aby dane wejściowe były mapą skrótu, mającą etykiety „przypominające liście” jako klucze i etykiety „podobne do katalogu głównego” jako wartości. Na przykład:

{1 2, 3 2, 5 2, 4 2, 6 4}
{1 4, 3 4, 4 2, 8 5, 5 2, 7 6, 6 2}

Przy każdej iteracji znajduje najmniejszy klucz, do którego nie odwołuje się żaden inny węzeł, dodaje go do wyniku ri usuwa węzeł z definicji wykresu G. if-letprzechodzi do innego przypadku, gdy Gjest pusty, ponieważ firstzwraca nil. Również ostatni element musi zostać usunięty.

Python 2 , 91 bajtów

d=input()
while len(d)>2:m=min(d,key=lambda k:len(d[k]));n,=d[m];del d[m];d[n]-={m};print n

Wypróbuj online!

Na podstawie rozwiązania L3viathan . Bierze słownik zestawów reprezentujących listy przyległości.