Экскурсии графа Эйлера
Леонард Эйлер хочет навестить нескольких друзей, которые живут в домах 2, 3, ..., N (он живет в доме 1). Однако из-за того, как устроен его город, ни один из путей между домами не образует петли (так что дома существуют на графе, который представляет собой дерево).
Ему быстро становится скучно, но если он навещает своих друзей в другом порядке, скучать ему не придется. Итак, он хочет, чтобы вы помогли ему узнать, сколько уникальных способов навестить каждого друга и вернуться домой к концу дня.
У него нет карты своего города, но он помнит порядок домов, которые он посетил в прошлый раз, когда гулял.
Постановка задачи
Учитывая представление дерева с помощью тура Эйлера , определите количество уникальных ETR одного и того же дерева с корнем в 1.
Ввод
ETR дерева. Представление Euler Tour по существу начинается с корня и проходит по дереву в глубину, записывая метку каждого узла по мере его продвижения. Трехузловое дерево с одним корнем и двумя дочерними элементами будет представлено как 1 -> 2 -> 1 -> 3 -> 1. Трехузловое дерево с одним корнем, одним дочерним элементом и одним внуком будет представлено как 1 -> 2 -> 3 -> 2 -> 1.
Другими словами, он представляет схему Эйлера ориентированного графа, полученного путем создания двух ребер из каждого ребра в дереве, по одному в каждом направлении.
Вот наглядный пример ETR:
Я допущу несколько изменений во вводе:
- Вы можете выбрать, хотите ли вы, чтобы листовые узлы записывались один или два раза подряд.
- Вы можете выбрать, хотите ли вы вернуться в корень в конце.
Например, вот такое дерево:
1
/ \
2 3
/ \ \
4 5 6
Допускаются следующие варианты:
1 2 4 2 5 2 1 3 6 3 11 2 4 2 5 2 1 3 6 31 2 4 4 2 5 5 2 1 3 6 6 3 11 2 4 4 2 5 5 2 1 3 6 6 3(это показано в статье Википедии)
Вы можете ввести список целых чисел в любом разумном формате. Вы также можете запросить Nсначала ввести (количество узлов) и проиндексировать любое произвольное значение (здесь я использую 1-индексацию). Однако метки ваших узлов, начиная с, xдолжны быть x, x+1, x+2, ..., x+N-1.
Вывод
Целое число, представляющее количество уникальных ETR этого дерева, начиная с одного и того же корневого узла.
Спецификации и правила испытания
- обратите внимание, что входные данные НЕ всегда являются двоичными деревьями; см. второй тестовый пример
- это проблема кода-гольфа , поэтому оценка производится по длине кода, чем ниже оценка, тем лучше
- ответ не будет принят
- Применяются стандартные лазейки
Тестовые кейсы
[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
Если вы хотите протестировать с большим количеством данных, моя эталонная реализация здесь . Это довольно плохо, но это правильно, так что вы можете его использовать; просто измените список в строке 3.
Ответы
Python 2 , 45 байт
f=lambda l:l==[]or(l.count(l.pop())or 1)*f(l)
Попробуйте онлайн!
Кажется, что один из способов получить ответ - это подсчитать количество каждого узла, то есть количество раз, когда каждый узел указан в списке, вычесть 1 из каждого и умножить их факториалы. То есть,
$$\prod_i (c_i-1)!$$
где узел \$i\$указан \$c_i\$раз. Обратите внимание, что не имеет значения, в каком порядке узлы появляются в представлении тура Эйлера, только сколько раз они появляются. Перечисление листовых узлов один или два раза не имеет значения, поскольку \$0!=1!=1\$.
Поскольку в Python нет встроенного факториала, мы поступаем так. Для каждой записи списка мы будем подсчитывать, сколько раз перед ней появляются одни и те же значения, то есть пометить ее kпоявление как 0-индексированное k. Например,
1 2 4 2 5 2 1 3 6 3 1
0 0 0 1 0 2 1 0 0 1 2
Если затем удалить все нули (или преобразовать их в единицы) и умножить, мы получим желаемый результат.
Чтобы сделать это рекурсивно, мы несколько раз удаляем последний элемент и рассматриваем его счетчик в оставшейся части списка, преобразовывая любое количество от 0 в 1. Затем мы умножаем его на рекурсивный результат в списке, удаляя последний элемент, с базовый случай 1 для пустого списка.
Мы можем сэкономить пару байтов, используя ввод с разделителями, и True1, если это разрешено.
43 байта
f=lambda a,*l:l==()or(l.count(a)or 1)*f(*l)
Попробуйте онлайн!
APL (Dyalog Unicode) , 17 11 байт
На основе ответа xnor . ⍤Оператор требует версии 18, который не является еще на TIO.
(×/!÷⊢)≢⍤⊢⌸
Вот более длинный вариант, который работает в более низких версиях:
(×/!÷⊢)∘(+/∪∘.=⊢)
Попробуйте онлайн!
+/∪∘.=⊢/ ≢⍤⊢⌸подсчитывает количество уникальных элементов во входных данных, ×/!÷⊢вычисляет$$\prod_i{c_i!\over c_i}$$
APL (Dyalog Unicode) , 27 байт
Я думаю, что это работает со всеми предлагаемыми форматами ввода.
{2>≢⍵:1⋄(×/∇¨,∘!≢)⍵⊆⍨⍵≠⌊/⍵}
Попробуйте онлайн!
Я не думаю, что базовый вариант 2>≢⍵:1действительно необходим, поскольку в какой-то момент не осталось поддеревьев для рекурсии, но я не могу заставить это работать без него.
Прокомментировал:
{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
Желе , 5 байт
ĠẈ’!P
Попробуйте онлайн!
5- байтовое желеобразное решение Count Euler's Tours , упомянутое HyperNeutrino .
Идея та же, что и в более раннем решении на Python, но я все же хотел бы объяснить, как я к этому пришел.
Обратите внимание, что мы можем решить эту проблему рекурсивно. Если наш текущий узел - N, с C детьми, наш ответ - C! умноженное на произведение дополнительных ответов всех детей. Причина в том, что мы можем опускаться (в нашем туре Эйлера) к детям в любом порядке, в каком захотим.
Второе наблюдение заключается в том, что для каждого узла, кроме корня, где count (x) - это количество вхождений x в обход Эйлера:
$$count(i) = deg(i)$$
Для рута
$$count(r) = deg(r) + 1$$
Теперь, если мы посмотрим на нашу формулу выше, мы заметим, что наш ответ:
$$deg(r)! * [deg(n) - 1]!$$
для каждого другого узла n. Это действительно очень хорошо работает. Отметим, что, как упоминалось ранее, ответ таков:
$$\prod_{i = 1}^v [count(v) - 1]!$$
Этот раствор очень хорошо превращается в желе.
ĠẈ’!P
Сначала мы получаем необходимый нам массив count, Ġгруппируя индексы по их элементам и взяв векторизованную длину. Затем мы уменьшаем и факторизуем, и, наконец, производим:
ĠẈ Count array
’ Decrement
! Factorial
P Product
PS: Спасибо HyperNeutrino за помощь с раствором желе, так как мое желе немного ржавое ...
JavaScript (ES6), 42 байта
Это основано на гипотезе @xnor .
a=>a.map(x=>t*=(a[~x]=-~a[~x])-1||1,t=1)|t
Попробуйте онлайн!
Уголь , 11 байт
ＩΠＥθ∨№…θκι¹
Попробуйте онлайн! Ссылка на подробную версию кода. Использует алгоритм @xnor. Пояснение:
θ 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
Используя форму представления, при которой листовые узлы посещаются один раз, а корневой узел считается имеющим дополнительное ребро, так что он посещается как в начале, так и в конце, тогда количество ребер для данного узла равно количеству ребер раз его посетили. При первом посещении узла с nребрами у вас есть только выбор n-1ребер, поскольку вам нужно полностью пройти все его поддеревья, прежде чем вернуться к родительскому, и аналогично при последующих посещениях у вас будет меньше вариантов, пока, наконец, два последних посещения не предоставят вам вообще нет выбора. Это можно свести к произведениям соответствующих факториалов для каждого узла, хотя, как указывает @xnor, для некоторых языков на самом деле удобнее заменять каждое посещение подсчетом оставшихся вариантов и брать общий продукт (алгоритм древесного угля фактически берет продукт в обратном порядке, но, конечно, это не имеет значения для общей суммы).
05AB1E , 5 байт
Ù¢<!P
Немного хромает, но это просто порт @xnor «s Python 2 ответа и @Riolku » Jelly ответ s , поэтому убедитесь , что upvote их!
Попробуйте онлайн или проверьте все тестовые примеры .
Пояснение:
Ù # 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)
Perl 5 -ap , 27 байт
$\=1;$\*=$h{$_}++||1for@F}{
Попробуйте онлайн!
Japt , 8 байт
ü ®ÅÊÊÃ×
Попытайся