Los viajes del conde Euler

Question

Leonhard Euler quiere visitar a unos amigos que viven en las casas 2, 3, ..., N (él vive en la casa 1). Sin embargo, debido a cómo está distribuida su ciudad, ninguno de los caminos entre las casas forma un bucle (por lo tanto, las casas existen en un gráfico que es un árbol).

Se aburre fácilmente, pero si visita a sus amigos en un orden diferente, no se aburrirá. Por lo tanto, quiere que lo ayudes a encontrar cuántas formas únicas hay de visitar a cada amigo y regresar a casa al final del día.

No tiene un mapa de su ciudad, pero recuerda el orden de las casas que visitó la última vez que salió a caminar.

Planteamiento del problema

Dada la Representación del recorrido de Euler de un árbol, determine el número de ETR únicos del mismo árbol, con la raíz en 1.

Entrada

La ETR de un árbol. La representación de recorrido de Euler comienza esencialmente en la raíz y atraviesa la profundidad del árbol, escribiendo primero la etiqueta de cada nodo a medida que avanza. Un árbol de 3 nodos con una raíz y dos hijos se representaría como 1 -> 2 -> 1 -> 3 -> 1. Un árbol de 3 nodos con una raíz, un hijo y un nieto se representaría como 1 -> 2 -> 3 -> 2 -> 1.

En otras palabras, representa el circuito euleriano de un gráfico dirigido derivado de crear dos aristas de cada arista del árbol, una en cada dirección.

A continuación, se muestra un ejemplo visual de una ETR:

Permitiré algunas alteraciones a la entrada:

1. Puede elegir si desea que los nodos hoja se escriban una o dos veces consecutivas.
2. Puede elegir si desea volver a la raíz al final.

Por ejemplo, aquí hay un árbol:

    1
   / \
  2   3
 / \   \
4   5   6

Los siguientes son aceptables:

• 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 (esto se muestra en el artículo de Wikipedia)

Puede tomar la entrada en cualquier formato razonable para una lista de números enteros. También puede solicitar ingresar N(el número de nodos) primero e indexar en cualquier valor arbitrario (yo uso 1-indexing aquí). Sin embargo, las etiquetas de sus nodos a partir de xdeben ser x, x+1, x+2, ..., x+N-1.

Salida

Un número entero, que representa el número de ETR únicos de este árbol, comenzando desde el mismo nodo raíz.

Especificaciones y reglas del desafío

• tenga en cuenta que las entradas NO siempre son árboles binarios; ver el segundo caso de prueba
• este es un problema de código de golf , por lo que la puntuación es por longitud de código, siendo mejor una puntuación más baja
• no se aceptará respuesta
• Se aplican lagunas legales estándar

Casos de prueba

[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

^{Si desea probar con más datos, mi implementación de referencia está aquí . Es bastante malo pero correcto, así que puedes usarlo; simplemente modifique la lista en la línea 3.}

Answer 1

Python 2 , 45 bytes

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

¡Pruébelo en línea!

Parece que una forma de obtener la respuesta es tomar los recuentos de cada nodo, es decir, el número de veces que aparece cada nodo, restar 1 de cada uno y multiplicar sus factoriales. Es decir,

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

donde nodo \$i\$está listado \$c_i\$veces. Tenga en cuenta que no importa en qué orden aparezcan los nodos en la Representación del recorrido de Euler, solo cuántas veces lo hacen. Listar los nodos hoja una o dos veces no hace ninguna diferencia, ya que \$0!=1!=1\$.

Como Python no tiene un factorial incorporado, lo hacemos así. Para cada entrada de la lista, contaremos cuántas veces aparecen los mismos valores antes de ella, es decir, etiquetar su kapariencia con índice 0 k. Por ejemplo,

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

Si luego quitamos todos los ceros (o los convertimos a unos) y los multiplicamos, obtenemos el resultado deseado.

Para hacer esto de forma recursiva, eliminamos repetidamente el último elemento y consideramos su recuento en el resto de la lista, convirtiendo cualquier recuento de 0 a 1. Luego, multiplicamos por el resultado recursivo en la lista con su último elemento ahora eliminado, con un caso base de 1 para la lista vacía.

Podemos guardar un par de bytes usando la entrada salpicada y Truepara 1 si está permitido.

43 bytes

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

¡Pruébelo en línea!

Answer 2

APL (Dyalog Unicode) , 17 11 bytes

Basado en la respuesta de xnor . El ⍤operador requiere la versión 18, que aún no está en TIO.

(×/!÷⊢)≢⍤⊢⌸

Aquí hay una variante más larga que funciona en versiones inferiores:

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

¡Pruébelo en línea!

+/∪∘.=⊢/ ≢⍤⊢⌸cuenta las apariciones de los elementos únicos en la entrada, ×/!÷⊢calcula$$\prod_i{c_i!\over c_i}$$

APL (Dyalog Unicode) , 27 bytes

Creo que esto funciona con todos los formatos de entrada sugeridos.

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

¡Pruébelo en línea!

No creo que el caso base 2>≢⍵:1sea ​​realmente necesario, ya que en algún momento no quedan subárboles en los que recurrir, pero no puedo hacer que esto funcione sin él.

Comentó:

{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 bytes

ĠẈ’!P

¡Pruébelo en línea!

Count Euler's Tours 5 Byte Jelly Solution, como lo menciona HyperNeutrino .

La idea es la misma que la de una solución de Python anterior, pero aún así me gustaría explicar cómo surgió.

Tenga en cuenta que podemos resolver esto de forma recursiva. Si nuestro nodo actual es N, con C hijos, ¡nuestra respuesta es C! multiplicado por el producto de las sub-respuestas de todos los niños. La razón es que podemos descender (en nuestro tour euler) hacia los niños en el orden que elijamos.

La segunda observación es que para cada nodo excepto la raíz, donde count (x) es el número de apariciones de x en el recorrido de euler:

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

Para la raíz

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

Ahora, si miramos nuestra fórmula anterior, notamos que nuestra respuesta es

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

para todos los demás nodos n. En realidad, esto funciona muy bien. Observamos que, como se mencionó anteriormente, la respuesta es:

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

Esta solución se presta muy bien a la gelatina.

ĠẈ’!P

Primero, obtenemos la matriz de conteo que necesitamos, obteniendo Ġíndices de enrutamiento por sus elementos y tomando la longitud vectorizada. Luego decrementamos y factorial, y finalmente producto:

ĠẈ      Count array
  ’     Decrement
   !    Factorial
    P   Product

PD: Gracias a HyperNeutrino por ayudarme con la solución de gelatina, ya que mi gelatina está un poco oxidada ...

Answer 4

JavaScript (ES6), 42 bytes

Esto se basa en la conjetura de @ xnor .

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

¡Pruébelo en línea!

Answer 5

Carbón , 11 bytes

ＩΠＥθ∨№…θκι¹

¡Pruébelo en línea! El enlace corresponde a la versión detallada del código. Utiliza el algoritmo de @ xnor. Explicación:

   θ        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 de representación en la que los nodos hoja se visitan una vez y se considera que el nodo raíz tiene un borde adicional para que sea visitado tanto al inicio como al final, entonces el número de bordes para un nodo dado es igual al número de veces que fue visitado. En la primera visita a un nodo con nbordes, solo tiene una opción de n-1bordes, ya que debe atravesar completamente todos sus subárboles antes de regresar al padre, y de manera similar, en visitas posteriores tiene menos opciones hasta que finalmente las dos últimas visitas le brindan no hay elección en absoluto. Esto podría reducirse a los productos de los factoriales relevantes para cada nodo, aunque como señala @xnor, en realidad, es más práctico para algunos idiomas reemplazar cada visita con el recuento de opciones restantes y tomar el producto general (el algoritmo Charcoal en realidad toma el producto en orden inverso, pero por supuesto esto no hace ninguna diferencia en el total).

Answer 6

05AB1E , 5 bytes

Ù¢<!P

Un poco tonto, pero esto es simplemente un puerto de la respuesta de Python 2 de @xnor y la respuesta de Jelly de @Riolku , ¡así que asegúrese de votarlos!

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

Ù      # 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 bytes

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

¡Pruébelo en línea!

Answer 8

Japonés , 8 bytes

ü ®ÅÊÊÃ×

Intentalo