Count Euler's Tours

Question

Leonhard Euler wants to visit a few friends who live in houses 2, 3, ..., N (he lives in house 1). However, because of how his city is laid out, none of the paths between any houses form a loop (so, the houses exist on a graph which is a tree).

He gets bored easily but if he visits his friends in a different order, he won't be bored. So, he wants you to help him find how many unique ways there are for him to visit every friend and return home by the end of the day.

He doesn't have a map of his city, but he does remember the order of houses he visited last time he went on a walk.

Problem Statement

Given the Euler Tour Representation of a tree, determine the number of unique ETRs of the same tree, with the root at 1.

Input

The ETR of a tree. The Euler Tour Representation essentially starts at the root and traverses the tree depth-first writing out the label of each node as it goes along. A 3-node tree with one root and two children would be represented as 1 -> 2 -> 1 -> 3 -> 1. A 3-node tree with one root, one child, and one grandchild would be represented as 1 -> 2 -> 3 -> 2 -> 1.

In other words, it represents the Eulerian circuit of a directed graph derived from creating two edges from each edge in the tree, one in each direction.

Here is a visual example of an ETR:

I will allow a few alterations to the input:

1. You can choose if you want leaf nodes to be written once or twice consecutively.
2. You can choose if you want to return to the root at the end.

For example, here is a tree:

    1
   / \
  2   3
 / \   \
4   5   6

The following are acceptable:

• 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 (this is shown on the Wikipedia article)

You can take the input in any reasonable format for a list of integers. You may also request to input N (the number of nodes) first, and to index at any arbitrary value (I use 1-indexing here). However, your node labels starting from x must be x, x+1, x+2, ..., x+N-1.

Output

An integer, representing the number of unique ETRs of this tree, starting from the same root node.

Challenge Specifications and Rules

• note that inputs are NOT always binary trees; see the second test case
• this is a code-golf problem, so scoring is by code length with a lower score being better
• no answer will be accepted
• Standard Loopholes apply

Test Cases

[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

^{If you want to test with more data, my reference implementation is here. It's pretty bad but it's correct so you can use it; just modify the list in line 3.}

Answer 1

Python 2, 45 bytes

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

Try it online!

It seems that one way to get the answer is take the counts of each node, that is the number of times each node is listed, subtract 1 from each, and multiply their factorials. That is,

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

where node \$i\$ is listed \$c_i\$ times. Note that it doesn't matter what order the nodes appear in the Euler Tour Representation, only how many times they do. Listing leaf nodes once or twice doesn't make a difference, since \$0!=1!=1\$.

Since Python doesn't have a built-in factorial, we make do like this. For each entry of the list, we will count how many times that same values appears before it, that is label its k'th appearance 0-indexed as k. For example,

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

If we then remove all zeroes (or convert them to 1's) and multiply, we get the desired result.

To do this recursively, we repeatedly remove the last element and consider its its count in the remainder of the list, converting any count of 0 to 1. Then, we multiply by the recursive result on the list with its last element now removed, with a base case of 1 for the empty list.

We can save a couple of bytes using splatted input and True for 1 if this is allowed.

43 bytes

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

Try it online!

Answer 2

APL (Dyalog Unicode), 17 11 bytes

Based on xnor's answer. The ⍤ operator requires version 18, which is not yet on TIO.

(×/!÷⊢)≢⍤⊢⌸

Here is a longer variant that works in lower versions:

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

Try it online!

+/∪∘.=⊢/≢⍤⊢⌸ counts the occurrences of the unique items in the input, ×/!÷⊢ calculates $$\prod_i{c_i!\over c_i}$$

APL (Dyalog Unicode), 27 bytes

I think this works with all suggested input formats.

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

Try it online!

I don't think the base case 2>≢⍵:1 is really necessary, since at some point there are no subtrees left to recurse on, but I can't get this to work without it.

Commented:

{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

Jelly, 5 bytes

ĠẈ’!P

Try it online!

Count Euler's Tours 5 Byte Jelly Solution, as mentioned by HyperNeutrino.

The idea is the same as an earlier python solution, but I'd still like to explain how I came about it.

Note that we can solve this recursively. If our current node is N, with C children, our answer is C! times the product of the sub-answers from all the children. The reason is we can descend (in our euler tour) into the children in any order we so choose.

The second observation is that for every node except the root, where count(x) is the number of occurences of x in the euler tour:

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

For the root,

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

Now, if we look at our formula above, we note that our answer is

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

for every other node n. This actually works out hilariously well. We note that, as mentioned before, the answer is:

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

This solution lends itself very well to jelly.

ĠẈ’!P

First, we get the count array that we need, by Ġrouping indices by their elements and taking vectorized length. Then we decrement and factorial, and finally product:

ĠẈ      Count array
  ’     Decrement
   !    Factorial
    P   Product

P.S.: Thanks to HyperNeutrino for helping me with the jelly solution, seeing as my jelly is a bit rusty...

Answer 4

JavaScript (ES6), 42 bytes

This is based on @xnor's conjecture.

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

Try it online!

Answer 5

Charcoal, 11 bytes

ＩΠＥθ∨№…θκι¹

Try it online! Link is to verbose version of code. Uses @xnor's algorithm. Explanation:

   θ        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

Using the form of representation whereby leaf nodes are visited once and the root node is considered to have an extra edge so that it gets visited both at the start and the end, then the number of edges for a given node is equal to the number of times it was visited. On the first visit to a node with n edges you only have a choice of n-1 edges since you have to completely traverse all of its subtrees before returning to the parent, and similarly on subsequent visits you have fewer choices until finally the last two visits both give you no choice at all. This could be reduced to the products of the relevant factorials for each node, although as @xnor points out it's actually golfier for some languages to replace each visit with the count of remaining choices and take the overall product (the Charcoal algorithm actually takes the product in reverse order but of course this makes no difference to the total).

Answer 6

Japt, 8 bytes

ü ®ÅÊÊÃ×

Try it

ü ®ÅÊÊÃ×     :Implicit input of array
ü            :Group and sort by value
  ®          :Map
   Å         :  Slice off the first element
    Ê        :  Length
     Ê       :  Factorial
      Ã      :End map
       ×     :Reduce by multiplication

Answer 7

05AB1E, 5 bytes

Ù¢<!P

A bit lame, but this is simply a port of @xnor's Python 2 answer and @Riolku's Jelly answer, so make sure to upvote them!

Try it online or verify all test cases.

Explanation:

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

Perl 5 -ap, 27 bytes

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

Try it online!