Visites du comte Euler

Question

Leonhard Euler veut rendre visite à quelques amis qui vivent dans les maisons 2, 3, ..., N (il habite dans la maison 1). Cependant, en raison de la disposition de sa ville, aucun des chemins entre les maisons ne forme une boucle (ainsi, les maisons existent sur un graphique qui est un arbre).

Il s'ennuie facilement mais s'il rend visite à ses amis dans un ordre différent, il ne s'ennuiera pas. Alors, il veut que vous l'aidiez à trouver le nombre de façons uniques dont il dispose pour rendre visite à chaque ami et rentrer chez lui avant la fin de la journée.

Il n'a pas de carte de sa ville, mais il se souvient de l'ordre des maisons qu'il a visitées la dernière fois qu'il s'est promené.

Énoncé du problème

Étant donné la représentation Euler Tour d'un arbre, déterminez le nombre d'ETR uniques du même arbre, avec la racine à 1.

Contribution

L'ETR d'un arbre. La représentation Euler Tour commence essentiellement à la racine et traverse l'arborescence en profondeur en écrivant d'abord l'étiquette de chaque nœud au fur et à mesure. Un arbre à 3 nœuds avec une racine et deux enfants serait représenté par 1 -> 2 -> 1 -> 3 -> 1. Un arbre à 3 nœuds avec une racine, un enfant et un petit-enfant serait représenté par 1 -> 2 -> 3 -> 2 -> 1.

En d'autres termes, il représente le circuit eulérien d'un graphe orienté dérivé de la création de deux arêtes à partir de chaque arête de l'arbre, une dans chaque direction.

Voici un exemple visuel d'un ETR:

Je vais permettre quelques modifications à l'entrée:

1. Vous pouvez choisir si vous souhaitez que les nœuds feuilles soient écrits une ou deux fois consécutivement.
2. Vous pouvez choisir si vous souhaitez revenir à la racine à la fin.

Par exemple, voici un arbre:

    1
   / \
  2   3
 / \   \
4   5   6

Les éléments suivants sont acceptables:

• 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 (ceci est montré sur l'article Wikipédia)

Vous pouvez prendre l'entrée dans n'importe quel format raisonnable pour une liste d'entiers. Vous pouvez également demander à saisir d'abord N(le nombre de nœuds) et à indexer à n'importe quelle valeur arbitraire (j'utilise ici l'indexation 1). Cependant, les étiquettes de vos nœuds à partir de xdoivent être x, x+1, x+2, ..., x+N-1.

Production

Un entier, représentant le nombre d'ETR uniques de cet arbre, à partir du même nœud racine.

Spécifications et règles du défi

• notez que les entrées ne sont PAS toujours des arbres binaires; voir le deuxième cas de test
• il s'agit d'un problème de code-golf , donc le score se fait par longueur de code, un score inférieur étant meilleur
• aucune réponse ne sera acceptée
• Les échappatoires standard s'appliquent

Cas de 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

^{Si vous souhaitez tester avec plus de données, mon implémentation de référence est ici . C'est assez mauvais mais c'est correct donc vous pouvez l'utiliser; modifiez simplement la liste de la ligne 3.}

Answer 1

Python 2 , 45 octets

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

Essayez-le en ligne!

Il semble qu'une façon d'obtenir la réponse est de prendre le décompte de chaque nœud, c'est-à-dire le nombre de fois que chaque nœud est répertorié, soustraire 1 de chacun et multiplier leurs factorielles. C'est,

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

où noeud \$i\$est répertorié \$c_i\$fois. Notez que l'ordre dans lequel les nœuds apparaissent dans la représentation Euler Tour n'a pas d'importance, mais seulement combien de fois ils le font. La liste des nœuds feuilles une ou deux fois ne fait aucune différence, car \$0!=1!=1\$.

Puisque Python n'a pas de factorielle intégrée, nous faisons comme ça. Pour chaque entrée de la liste, nous compterons le nombre de fois que les mêmes valeurs apparaissent devant elle, c'est-à-dire que sa k'ème apparence est indexée à 0 k. Par exemple,

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

Si nous supprimons ensuite tous les zéros (ou les convertissons en 1) et multiplions, nous obtenons le résultat souhaité.

Pour ce faire de manière récursive, nous supprimons à plusieurs reprises le dernier élément et considérons son décompte dans le reste de la liste, en convertissant tout décompte de 0 en 1. Ensuite, nous multiplions par le résultat récursif sur la liste avec son dernier élément maintenant supprimé, avec un cas de base de 1 pour la liste vide.

Nous pouvons enregistrer quelques octets en utilisant une entrée splattée et Truepour 1 si cela est autorisé.

43 octets

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

Essayez-le en ligne!

Answer 2

APL (Dyalog Unicode) , 17 11 octets

Basé sur la réponse de xnor . L' ⍤opérateur a besoin de la version 18, qui n'est pas encore sur TIO.

(×/!÷⊢)≢⍤⊢⌸

Voici une variante plus longue qui fonctionne dans les versions inférieures:

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

Essayez-le en ligne!

+/∪∘.=⊢/ ≢⍤⊢⌸compte les occurrences des éléments uniques dans l'entrée, ×/!÷⊢calcule$$\prod_i{c_i!\over c_i}$$

APL (Dyalog Unicode) , 27 octets

Je pense que cela fonctionne avec tous les formats d'entrée suggérés.

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

Essayez-le en ligne!

Je ne pense pas que le cas de base soit 2>≢⍵:1vraiment nécessaire, car à un moment donné, il ne reste plus de sous-arbres sur lesquels se répéter, mais je ne peux pas faire fonctionner cela sans lui.

Commenté:

{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

Gelée , 5 octets

ĠẈ’!P

Essayez-le en ligne!

Count Euler's Tours 5 Byte Jelly Solution, comme mentionné par HyperNeutrino .

L'idée est la même que celle d'une solution python précédente, mais j'aimerais quand même expliquer comment je suis arrivée.

Notez que nous pouvons résoudre ce problème de manière récursive. Si notre nœud actuel est N, avec des enfants C, notre réponse est C! fois le produit des sous-réponses de tous les enfants. La raison en est que nous pouvons descendre (lors de notre tournée euler) chez les enfants dans l'ordre que nous choisissons.

La deuxième observation est que pour chaque nœud sauf la racine, où count (x) est le nombre d'occurrences de x dans le tour euler:

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

Pour la racine,

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

Maintenant, si nous regardons notre formule ci-dessus, nous notons que notre réponse est

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

pour chaque autre nœud n. Cela fonctionne vraiment très bien. Nous notons que, comme mentionné précédemment, la réponse est:

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

Cette solution se prête très bien à la gelée.

ĠẈ’!P

Premièrement, nous obtenons le tableau de comptage dont nous avons besoin, en Ġregroupant les indices par leurs éléments et en prenant la longueur vectorisée. Puis on décrémente et factorielle, et enfin on produit:

ĠẈ      Count array
  ’     Decrement
   !    Factorial
    P   Product

PS: Merci à HyperNeutrino de m'avoir aidé avec la solution de gelée, vu que ma gelée est un peu rouillée ...

Answer 4

JavaScript (ES6), 42 octets

Ceci est basé sur la conjecture de @ xnor .

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

Essayez-le en ligne!

Answer 5

Charbon , 11 octets

ＩΠＥθ∨№…θκι¹

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Utilise l'algorithme de @ xnor. Explication:

   θ        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

En utilisant la forme de représentation par laquelle les nœuds feuilles sont visités une fois et le nœud racine est considéré comme ayant un bord supplémentaire afin qu'il soit visité à la fois au début et à la fin, alors le nombre d'arêtes pour un nœud donné est égal au nombre de fois où il a été visité. Lors de la première visite d'un nœud avec des narêtes, vous n'avez que le choix des n-1arêtes car vous devez traverser complètement tous ses sous-arbres avant de revenir au parent, et de même lors des visites suivantes, vous avez moins de choix jusqu'à ce que finalement les deux dernières visites vous donnent toutes les deux. pas de choix du tout. Cela pourrait être réduit aux produits des factorielles pertinentes pour chaque nœud, bien que, comme @xnor le souligne, il est en fait plus golfique pour certaines langues de remplacer chaque visite par le nombre de choix restants et de prendre le produit global (l'algorithme Charcoal prend en fait le produit dans l'ordre inverse, mais bien sûr cela ne change rien au total).

Answer 6

05AB1E , 5 octets

Ù¢<!P

Un peu boiteux, mais c'est simplement un portage de la réponse Python 2 de @xnor et de la réponse Jelly de @Riolku , alors assurez-vous de les voter!

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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

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

Essayez-le en ligne!

Answer 8

Japt , 8 octets

ü ®ÅÊÊÃ×

Essayez-le