Conte Eulero Tours

Question

Leonhard Euler vuole visitare alcuni amici che vivono nelle case 2, 3, ..., N (vive nella casa 1). Tuttavia, a causa di come è strutturata la sua città, nessuno dei percorsi tra le case forma un anello (quindi, le case esistono su un grafico che è un albero).

Si annoia facilmente, ma se fa visita ai suoi amici in un ordine diverso, non si annoierà. Quindi, vuole che tu lo aiuti a scoprire quanti modi unici ci sono per lui per visitare ogni amico e tornare a casa entro la fine della giornata.

Non ha una mappa della sua città, ma ricorda l'ordine delle case che ha visitato l'ultima volta che è andato a fare una passeggiata.

Dichiarazione problema

Data la rappresentazione del tour di Eulero di un albero, determinare il numero di ETR univoci dello stesso albero, con la radice a 1.

Ingresso

L'ETR di un albero. La rappresentazione del tour di Eulero inizia essenzialmente dalla radice e attraversa la profondità dell'albero scrivendo prima l'etichetta di ogni nodo mentre procede. Un albero a 3 nodi con una radice e due figli sarebbe rappresentato come 1 -> 2 -> 1 -> 3 -> 1. Un albero a 3 nodi con una radice, un figlio e un nipote sarebbe rappresentato come 1 -> 2 -> 3 -> 2 -> 1.

In altre parole, rappresenta il circuito euleriano di un grafo diretto derivato dalla creazione di due bordi da ciascun bordo dell'albero, uno in ciascuna direzione.

Ecco un esempio visivo di un ETR:

Permetterò alcune modifiche all'input:

1. Puoi scegliere se vuoi che i nodi foglia vengano scritti una o due volte consecutivamente.
2. Puoi scegliere se vuoi tornare alla radice alla fine.

Ad esempio, ecco un albero:

    1
   / \
  2   3
 / \   \
4   5   6

Sono accettabili:

• 1 2 4 2 5 2 1 3 6 3 1
• 1 2 4 2 5 2 1 3 6 3
• 1 2 4 4 2 5 5 2 1 3 6 6 3 1
• 1 2 4 4 2 5 5 2 1 3 6 6 3 (questo è mostrato nell'articolo di Wikipedia)

Puoi prendere l'input in qualsiasi formato ragionevole per un elenco di numeri interi. Puoi anche richiedere di inserire prima N(il numero di nodi) e di indicizzare qualsiasi valore arbitrario (qui uso l'indicizzazione 1). Tuttavia, le etichette dei nodi che iniziano da xdevono essere x, x+1, x+2, ..., x+N-1.

Produzione

Un numero intero, che rappresenta il numero di ETR univoci di questo albero, a partire dallo stesso nodo radice.

Specifiche e regole della sfida

• notare che gli input NON sono sempre alberi binari; vedi il secondo caso di prova
• questo è un problema di code-golf , quindi il punteggio è in base alla lunghezza del codice con un punteggio inferiore è migliore
• nessuna risposta sarà accettata
• Si applicano scappatoie standard

Casi test

[1, 2, 3, 2, 4, 5, 4, 6, 4, 2, 1, 7, 8, 9, 8, 7, 1]                      ->  8
[1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1, 8, 9, 8, 10, 8, 1]               -> 48
[1, 2, 3, 4, 5, 6, 7, 6, 8, 6, 5, 9, 5, 4, 10, 4, 3, 11, 3, 2, 12, 2, 1] -> 32
[1]                                                                      ->  1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1]                      ->  1

^{Se vuoi testare con più dati, la mia implementazione di riferimento è qui . È piuttosto brutto ma è corretto quindi puoi usarlo; basta modificare l'elenco nella riga 3.}

Answer 1

Python 2 , 45 byte

f=lambda l:l==[]or(l.count(l.pop())or 1)*f(l)

Provalo online!

Sembra che un modo per ottenere la risposta sia prendere i conteggi di ogni nodo, cioè il numero di volte in cui ogni nodo è elencato, sottrarre 1 da ciascuno e moltiplicare i loro fattoriali. Questo è,

$$\prod_i (c_i-1)!$$

dove nodo \$i\$è elencato \$c_i\$volte. Nota che non importa in quale ordine i nodi compaiono nella rappresentazione del tour di Eulero, ma solo quante volte lo fanno. Elencare i nodi foglia una o due volte non fa differenza, poiché \$0!=1!=1\$.

Dal momento che Python non ha un fattoriale incorporato, facciamo così. Per ogni voce della lista, conteremo quante volte gli stessi valori appaiono prima di essa, cioè etichettiamo il suo k'esimo aspetto 0-indicizzato come k. Per esempio,

1 2 4 2 5 2 1 3 6 3 1
0 0 0 1 0 2 1 0 0 1 2  

Se poi rimuoviamo tutti gli zeri (o li convertiamo in 1) e li moltiplichiamo, otteniamo il risultato desiderato.

Per fare ciò in modo ricorsivo, rimuoviamo ripetutamente l'ultimo elemento e consideriamo il suo conteggio nel resto dell'elenco, convertendo qualsiasi conteggio da 0 a 1. Quindi, moltiplichiamo per il risultato ricorsivo nell'elenco con il suo ultimo elemento ora rimosso, con un caso base di 1 per l'elenco vuoto.

Possiamo salvare un paio di byte usando l'input splattato e Trueper 1 se questo è consentito.

43 byte

f=lambda a,*l:l==()or(l.count(a)or 1)*f(*l)

Provalo online!

Answer 2

APL (Dyalog Unicode) , 17 11 byte

Basato sulla risposta di xnor . L' ⍤operatore richiede la versione 18, che non è ancora su TIO.

(×/!÷⊢)≢⍤⊢⌸

Ecco una variante più lunga che funziona nelle versioni inferiori:

(×/!÷⊢)∘(+/∪∘.=⊢)

Provalo online!

+/∪∘.=⊢/ ≢⍤⊢⌸conta le occorrenze degli elementi univoci nell'input, ×/!÷⊢calcola$$\prod_i{c_i!\over c_i}$$

APL (Dyalog Unicode) , 27 byte

Penso che funzioni con tutti i formati di input suggeriti.

{2>≢⍵:1⋄(×/∇¨,∘!≢)⍵⊆⍨⍵≠⌊/⍵}

Provalo online!

Non penso che il caso di base 2>≢⍵:1sia davvero necessario, poiché a un certo punto non ci sono più sottoalberi su cui ricorrere, ma non riesco a farlo funzionare senza di esso.

Commentato:

{2>≢⍵:1⋄(×/∇¨,∘!≢)⍵⊆⍨⍵≠⌊/⍵}  ⍝ A recursive dfns
 2>≢⍵                        ⍝ If the input has less than 2 elements
     :1                      ⍝   return 1
                  ⍵⊆⍨        ⍝ Partition the input ...
                     ⍵≠      ⍝ ... taking the elements that are not equal
                       ⌊/⍵   ⍝ to the minimum (the root of the current tree)
                             ⍝ These are the new subtrees
               !≢            ⍝ Take the factorial of the number of subtrees
             ,               ⍝ And append it to the results of ...
           ∇¨                ⍝ the recursive calls on each subtree
         ×/                  ⍝ take the product of the vector
                             ⍝ this is the result

Answer 3

Gelatina , 5 byte

ĠẈ’!P

Provalo online!

Count Euler's Tours 5 Byte Jelly Solution, come menzionato da HyperNeutrino .

L'idea è la stessa di una precedente soluzione Python, ma vorrei comunque spiegare come l'ho ottenuta.

Nota che possiamo risolverlo ricorsivamente. Se il nostro nodo corrente è N, con C figli, la nostra risposta è C! volte il prodotto delle sotto-risposte di tutti i bambini. Il motivo è che possiamo scendere (nel nostro tour di Eulero) nei bambini in qualsiasi ordine lo desideriamo.

La seconda osservazione è che per ogni nodo tranne la radice, dove count (x) è il numero di occorrenze di x nel tour di eulero:

$$count(i) = deg(i)$$

Per la radice,

$$count(r) = deg(r) + 1$$

Ora, se guardiamo la nostra formula sopra, notiamo che la nostra risposta è

$$deg(r)! * [deg(n) - 1]!$$

per ogni altro nodo n. In realtà funziona in modo esilarante. Notiamo che, come accennato prima, la risposta è:

$$\prod_{i = 1}^v [count(v) - 1]!$$

Questa soluzione si presta molto bene alla gelatina.

ĠẈ’!P

Per prima cosa, otteniamo l'array count di cui abbiamo bisogno, ottenendo Ġgli indici di rouping dai loro elementi e prendendo la lunghezza vettorizzata. Quindi decrementiamo e fattoriale e infine prodotto:

ĠẈ      Count array
  ’     Decrement
   !    Factorial
    P   Product

PS: Grazie a HyperNeutrino per avermi aiutato con la soluzione di gelatina, visto che la mia gelatina è un po 'arrugginita ...

Answer 4

JavaScript (ES6), 42 byte

Questo è basato sulla congettura di @ xnor .

a=>a.map(x=>t*=(a[~x]=-~a[~x])-1||1,t=1)|t

Provalo online!

Answer 5

Carbone di legna , 11 byte

ＩΠＥθ∨№…θκι¹

Provalo online! Il collegamento è alla versione dettagliata del codice. Utilizza l'algoritmo di @ xnor. Spiegazione:

   θ        Input array
  Ｅ         Map over elements
       θ    Input array
      …     Truncated to length
        κ   Current index
     №      Count occurrences of
         ι  Current element
    ∨       Logical Or
          ¹ Literal `1`
 Π          Take the product
Ｉ           Cast to string
            Implicitly print

Usando la forma di rappresentazione in cui i nodi foglia vengono visitati una volta e il nodo radice è considerato avere un bordo extra in modo che venga visitato sia all'inizio che alla fine, quindi il numero di bordi per un dato nodo è uguale al numero di volte è stato visitato. Alla prima visita a un nodo con nbordi hai solo una scelta di n-1bordi poiché devi attraversare completamente tutti i suoi sottoalberi prima di tornare al genitore, e allo stesso modo nelle visite successive hai meno scelte fino a quando finalmente le ultime due visite ti danno nessuna scelta. Questo potrebbe essere ridotto ai prodotti dei fattoriali rilevanti per ogni nodo, sebbene come sottolinea @xnor sia effettivamente più golfistico per alcune lingue sostituire ogni visita con il conteggio delle scelte rimanenti e prendere il prodotto complessivo (l'algoritmo Charcoal prende effettivamente il prodotto in ordine inverso ma ovviamente questo non fa differenza rispetto al totale).

Answer 6

05AB1E , 5 byte

Ù¢<!P

Uno zoppo po ', ma questo è semplicemente un porto di @xnor 's Python 2 risposta e @Riolku ' s risposta gelatina , quindi assicuratevi di upvote loro!

Provalo online o verifica tutti i casi di test .

Spiegazione:

Ù      # Uniquify the (implicit) input-list
 ¢     # Count how many times each occurs in the (implicit) input-list
  <    # Decrease each count by 1
   !   # Take the factorial on each value
    P  # And take the product of that
       # (after which it is output implicitly as result)

Answer 7

Perl 5 -ap , 27 byte

$\=1;$\*=$h{$_}++||1for@F}{

Provalo online!

Answer 8

Japt , 8 byte

ü ®ÅÊÊÃ×

Provalo