Count Euler's Turları

Question

Leonhard Euler , 2, 3, ..., N numaralı evlerde yaşayan birkaç arkadaşını ziyaret etmek istiyor (1. evde yaşıyor). Ancak, kentinin nasıl düzenlendiğinden dolayı, evlerin arasındaki yolların hiçbiri bir döngü oluşturmaz (bu nedenle evler bir ağaç olan bir grafikte bulunur).

Kolayca sıkılır ama arkadaşlarını farklı bir sırayla ziyaret ederse sıkılmaz. Bu yüzden, her arkadaşını ziyaret etmesi ve günün sonunda eve dönmesi için kaç benzersiz yol olduğunu bulmasına yardım etmenizi istiyor.

Şehrinin bir haritası yok, ancak en son yürüyüşe çıktığında ziyaret ettiği evlerin sırasını hatırlıyor.

Sorun bildirimi

Bir ağacın Euler Turu Temsili verildiğinde, aynı ağacın benzersiz ETR sayısını, kök 1'de olacak şekilde belirleyin.

Giriş

Bir ağacın ETR'si. Euler Tur Temsilciliği esasen kökten başlar ve ağaç derinliğini aşar - önce her düğümün etiketini yazarken ilerler. Bir kök ve iki çocuk içeren 3 düğümlü bir ağaç olarak temsil edilir 1 -> 2 -> 1 -> 3 -> 1. Bir kökü, bir çocuğu ve bir torunu olan 3 düğümlü bir ağaç, olarak temsil edilir 1 -> 2 -> 3 -> 2 -> 1.

Başka bir deyişle, ağaçtaki her bir kenardan her bir yönde birer tane olmak üzere iki kenar oluşturmaktan türetilen yönlendirilmiş bir grafiğin Euler devresini temsil eder.

İşte bir ETR'nin görsel bir örneği:

Girişte birkaç değişikliğe izin vereceğim:

1. Yaprak düğümlerin art arda bir veya iki kez yazılmasını isteyip istemediğinizi seçebilirsiniz.
2. Sonunda köke geri dönmek isteyip istemediğinizi seçebilirsiniz.

Örneğin, işte bir ağaç:

    1
   / \
  2   3
 / \   \
4   5   6

Aşağıdakiler kabul edilebilir:

• 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 (bu Wikipedia makalesinde gösterilmektedir)

Tam sayıların bir listesi için girişi herhangi bir makul biçimde alabilirsiniz. Ayrıca önce girdi N(düğüm sayısı) ve herhangi bir rastgele değerde indeksleme talebinde bulunabilirsiniz (burada 1-indeksleme kullanıyorum). Ancak, başlangıç ​​düğüm etiketleriniz xolmalıdır x, x+1, x+2, ..., x+N-1.

Çıktı

Aynı kök düğümden başlayarak, bu ağacın benzersiz ETR sayısını temsil eden bir tam sayı.

Zorluk Özellikleri ve Kuralları

• girişlerin her zaman ikili ağaç OLMADIĞINI unutmayın; ikinci test senaryosuna bakın
• bu bir kod golf problemidir, bu nedenle puanlama kod uzunluğuna göredir ve daha düşük bir puan daha iyidir
• hiçbir cevap kabul edilmeyecek
• Standart Boşluklar geçerlidir

Test Durumları

[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

^{Daha fazla veriyle test etmek istiyorsanız, referans uygulamam burada . Oldukça kötü ama doğru, bu yüzden onu kullanabilirsiniz; sadece 3. satırdaki listeyi değiştirin.}

Answer 1

Python 2 , 45 bayt

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

Çevrimiçi deneyin!

Görünüşe göre cevabı almanın bir yolu, her bir düğümün sayısını almak, yani her bir düğümün kaç kez listelendiğini, her birinden 1 çıkarmak ve faktöriyellerini çarpmaktır. Yani,

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

burada düğüm \$i\$listeleniyor \$c_i\$zamanlar. Düğümlerin Euler Tur Temsilcisinde hangi sırada göründüklerinin önemli olmadığını, yalnızca kaç kez göründüklerinin önemli olduğunu unutmayın. Yaprak düğümleri bir veya iki kez listelemek bir fark yaratmaz, çünkü \$0!=1!=1\$.

Python yerleşik bir faktöriyel içermediğinden, bunu yaparız. Listenin her girişi için, aynı değerlerin ondan önce kaç kez göründüğünü sayacağız, yani onun k'inci görünümü 0 indekslenmiş olarak etiketlenir k. Örneğin,

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

Sonra tüm sıfırları kaldırırsak (veya 1'lere dönüştürürsek) ve çarparsak, istenen sonucu elde ederiz.

Bunu yinelemeli olarak yapmak için, son öğeyi defalarca kaldırır ve listenin geri kalanında onun sayısını dikkate alırız, herhangi bir sayıyı 0'a 1'e dönüştürürüz. boş liste için 1 temel durum.

Splatted girişi kullanarak birkaç bayt ve buna Trueizin verilirse 1 bayt kaydedebiliriz .

43 bayt

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

Çevrimiçi deneyin!

Answer 2

APL (Dyalog Unicode) , 17 11 bayt

Dayanarak XNOR cevabı . ⍤Operatör TIO üzerinde henüz sürümü 18 gerektirir.

(×/!÷⊢)≢⍤⊢⌸

İşte daha düşük versiyonlarda çalışan daha uzun bir varyant:

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

Çevrimiçi deneyin!

+/∪∘.=⊢/ ≢⍤⊢⌸girdideki benzersiz öğelerin oluşumlarını sayar, ×/!÷⊢hesaplar$$\prod_i{c_i!\over c_i}$$

APL (Dyalog Unicode) , 27 bayt

Bunun önerilen tüm giriş biçimleriyle çalıştığını düşünüyorum.

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

Çevrimiçi deneyin!

Temel durumun 2>≢⍵:1gerçekten gerekli olduğunu sanmıyorum , çünkü bir noktada tekrarlanacak alt ağaçlar kalmadı, ama bunu onsuz çalıştıramam.

Yorum yaptı:

{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

Jöle , 5 bayt

ĠẈ’!P

Çevrimiçi deneyin!

HyperNeutrino'nun bahsettiği gibi Euler's Tours 5 Byte Jelly Solution'ı sayın .

Fikir daha önceki bir python çözümüyle aynı, ancak yine de bunun nasıl ortaya çıktığını açıklamak istiyorum.

Bunu yinelemeli olarak çözebileceğimize dikkat edin. Mevcut düğümümüz N ise, C çocuklu ise, cevabımız C! çarpı tüm çocuklardan gelen alt cevapların çarpımıdır. Bunun nedeni, seçtiğimiz herhangi bir sırayla çocukların içine (euler turumuzda) inebilmemizdir.

İkinci gözlem, kök dışındaki her düğüm için, burada count (x), euler turunda x'in oluşum sayısıdır:

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

Kök için,

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

Şimdi, yukarıdaki formülümüze bakarsak, cevabımızın

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

diğer her düğüm için n. Bu aslında çok komik bir şekilde çalışıyor. Daha önce de belirtildiği gibi cevabın:

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

Bu çözüm jöleye çok iyi uyum sağlar.

ĠẈ’!P

İlk olarak, Ġindisleri elemanlarına göre yuvarlayarak ve vektörleştirilmiş uzunlukları alarak ihtiyacımız olan sayım dizisini elde ederiz. Sonra eksiltip faktöriyel ve nihayet ürün:

ĠẈ      Count array
  ’     Decrement
   !    Factorial
    P   Product

Not: Jöle çözümünde bana yardım ettiği için HyperNeutrino'ya teşekkürler, jölemin biraz paslı olduğunu görünce ...

Answer 4

JavaScript (ES6), 42 bayt

Bu, @ xnor'un varsayımına dayanmaktadır .

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

Çevrimiçi deneyin!

Answer 5

Kömür , 11 bayt

ＩΠＥθ∨№…θκι¹

Çevrimiçi deneyin! Bağlantı, kodun ayrıntılı sürümüne yöneliktir. @ Xnor'un algoritmasını kullanır. Açıklama:

   θ        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

Yaprak düğümlerin bir kez ziyaret edildiği ve kök düğümün hem başlangıçta hem de sonda ziyaret edilebilmesi için fazladan bir kenara sahip olduğu düşünülen temsil biçimi kullanıldığında, belirli bir düğüm için kenar sayısı, sayıya eşittir. kez ziyaret edildi. Kenarlı bir düğüme ilk ziyaretinizde , üst ağına dönmeden önce tüm alt ağaçlarını tamamen geçmeniz gerektiğinden, nyalnızca bir n-1kenar seçeneğiniz vardır ve benzer şekilde sonraki ziyaretlerde, son iki ziyaretin her ikisi de size verene kadar daha az seçeneğiniz vardır. hiçbir seçenek yok. Bu, her düğüm için ilgili faktörlerin ürünlerine indirgenebilir, ancak @xnor'un her ziyareti kalan seçeneklerin sayısıyla değiştirmesi ve genel ürünü alması bazı diller için aslında daha golfçudur (Kömür algoritması aslında ürünü alır) ters sırada ama tabii ki bu toplamda hiçbir fark yaratmaz)

Answer 6

05AB1E , 5 bayt

Ù¢<!P

Biraz sakat, ama bu sadece @xnor'un Python 2 cevabının ve @Riolku'nun Jelly cevabının bir limanı , bu yüzden onlara oy verdiğinizden emin olun!

Çevrimiçi deneyin veya tüm test durumlarını doğrulayın .

Açıklama:

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

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

Çevrimiçi deneyin!

Answer 8

Japt , 8 bayt

ü ®ÅÊÊÃ×

Dene