Napisz funkcję lub program, który wypisuje liczbę każdego typu elementu (wierzchołek, krawędź, powierzchnia itp.) Hipersześcianu N-wymiarowego.

Na przykład trójwymiarowy sześcian ma 1 komórkę (tj. 1 trójwymiarowy sześcian), 6 ścian (tj. 6 2-wymiarowych kostek), 12 krawędzi (tj. 12 2-wymiarowych kostek) i 8 wierzchołków (tj. 8 0-wymiarowych kostki).

Więcej informacji na temat elementów Hypercube można znaleźć tutaj

Możesz także rzucić okiem na następującą sekwencję OEIS .

Wejście

Twój kod przyjmuje jako dane wejściowe (przez STDIN lub parametr funkcji lub podobne rzeczy) liczbę całkowitą większą lub równą 0, która jest wymiarem hipersześcianu.

Twój kod musi teoretycznie działać dla każdego wejścia> = 0, nie uwzględniając problemów z pamięcią i czasem (to znaczy, szybkość i potencjalne przepełnienia stosu nie stanowią problemu dla twojej odpowiedzi, jeśli dane wejściowe są duże). Dane wejściowe podane jako przypadki testowe nie będą wyższe niż 12.

Wynik

Wyślesz listę wszystkich elementów hipersześcianu, zaczynając od elementu „najwyższego wymiaru”. Na przykład, dla sześcianu (input = 3), wypiszesz listę [1,6,12,8](1 komórka, 6 ścian, 12 krawędzi, 8 wierzchołków).

Format listy na wyjściu jest względnie darmowy, pod warunkiem, że wygląda jak lista.

Możesz wyprowadzić wynik do STDOUT lub zwrócić go z funkcji.

Przypadki testowe

Input = 0
Output = [1]

Input = 1
Output = [1,2]

Input = 3
Output = [1,6,12,8]

Input = 10
Output = [1, 20, 180, 960, 3360, 8064, 13440, 15360, 11520, 5120, 1024]

Input = 12
Output = [1, 24, 264, 1760, 7920, 25344, 59136, 101376, 126720, 112640, 67584, 24576, 4096]

Punktacja

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

Samau , 8 5 bajtów

Zaoszczędzono 3 bajty dzięki Dennisowi .

▌2\$ⁿ

Zrzut szesnastkowy (Samau używa kodowania CP737):

dd 32 2f 24 fc

Wyjaśnienie:

▌        read a number
 2\      push the array [1 2]
   $     swap
    ⁿ    take the convolution power

Konwekcja dwóch wektorów jest równoważna pomnożeniu dwóch wielomianów . Podobnie, przyjęcie n-tej mocy splotu jest równoważne z pobraniem n-tej mocy wielomianu.

J, 13 bajtów

[:p.2&^;$&_.5

Zainspirowany odpowiedzią PARI / GP @ alephalpha . Spróbuj go online z J.js .

tło

Według twierdzenia dwumianowego

Zatem dane wyjściowe dla wejścia n składają się dokładnie ze współczynników powyższego wielomianu.

Kod

[:p.2&^;$&_.5  Monadic verb. Argument: n

        $&_.5  Yield an array of n instances of -0.5.
    2&^        Compute 2^n.
       ;       Link the results to the left and right.
               This specifies a polynomial of n roots (all -0.5)
               with leading term 2^n.  
[:p.           Convert from roots to coefficients.

MATL, 8 bajtów

1i:"2:X+

Zainspirowany odpowiedzią PARI / GP @ alephalpha .

Wypróbuj online! (używa Y+do współczesnego MATL)

Jak to działa

1        % Push 1.
 i:      % Push [1 ... input].
   "     % Begin for-each loop:
    2:   %   Push [1 2].
      X+ %   Take the convolution product of the bottom-most stack item and [1 2].

MATL , 12 bajtów

Q:q"H@^G@Xn*

Wypróbuj online

Wyjaśnienie

         % implicit: input number "n"
Q:q      % generate array[0,1,...,n]
"        % for each element "m" from that array
  H@^    % compute 2^m
  G      % push n
  @      % push m
  Xn     % compute n choose m
  *      % multiply
         % implicit: close loop and display stack contents

Mathematica, 29 bajtów

CoefficientList[(1+2x)^#,x]&

Moja pierwsza odpowiedź Mathematica! Jest to po prostu funkcja, która wykorzystuje takie samo podejście jak Alephalpha za PARI / GP odpowiedź . Konstruujemy wielomian (1+2x)^ni otrzymujemy listę współczynników, uszeregowanych w kolejności rosnącej mocy (tj. Najpierw stałej).

Przykładowe użycie:

> F := CoefficientList[(1+2x)^#,x]&`
> F[10]
{1,20,180,960,3360,8064,13440,15360,11520,5120,1024}

APL, 15 11 bajtów

1,(2*⍳)×⍳!⊢

Jest to monadyczny ciąg funkcji, który akceptuje liczbę całkowitą po prawej stronie i zwraca tablicę liczb całkowitych.

Objaśnienie, wywoływanie danych wejściowych n:

        ⍳!⊢  ⍝ Get n choose m for each m from 1 to n
       ×     ⍝ Multiply elementwise by
  (2*⍳)      ⍝ 2^m for m from 1 to n
1,           ⍝ Tack 1 onto the front to cover the m=0 case

Wypróbuj online

Zaoszczędź 4 bajty dzięki Dennisowi!

PARI / GP, 20 15 bajtów

n->Vec((x+2)^n)

Galaretka, 8 bajtów

0rð2*×c@

Naprawdę powinienem przestać pisać Galaretkę na moim telefonie.

0r            Helper link. Input is n, inclusive range from 0 to n. Call the result r.
  ð           Start a new, dyadic link. Input is r, n.
   2*         Vectorized 2 to the power of r
     ×c@      Vectorized multiply by n nCr r. @ switches argument order.

Wypróbuj tutaj .

TI-BASIC, 10 bajtów

3^Ansbinompdf(Ans,2/3

CJam ( 17 14 bajtów)

ri_3@#_2+@#\b`

Demo online

To podejście wykorzystuje zwykłą funkcję generowania (x + 2)^n. OEIS wspomina (2x + 1)^n, ale to pytanie indeksuje współczynniki w odwrotnej kolejności. Kopie mnie za to, że nie myślę o odwróceniu GF, dopóki nie zobaczyłem aktualizacji Alephalpha do odpowiedzi PARI / GP, która zrobiła to samo.

Interesującą sztuczką w tej odpowiedzi jest użycie mocy liczb całkowitych do działania mocy wielomianowej poprzez działanie w bazie wyższej niż jakikolwiek możliwy współczynnik. Ogólnie biorąc, biorąc pod uwagę wielomian, p(x)którego współczynniki są liczbami całkowitymi nieujemnymi mniejszymi niż b, p(b)jest to podstawowa breprezentacja współczynników (ponieważ poszczególne monomale nie „nakładają się”). Oczywiście (x + 2)^nbędą miały współczynniki, które są dodatnimi liczbami całkowitymi i które sumują 3^n, więc każdy z nich będzie indywidualnie mniejszy niż 3^n.

ri     e# Read an integer n from stdin
_3@#   e# Push 3^n to the stack
_2+    e# Duplicate and add 2, giving a base-3^n representation of x+2
@#     e# Raise to the power of n
\b`    e# Convert into a vector of base-3^n digits and format for output

Alternatywne podejścia: 17 bajtów

1a{0X$2f*+.+}ri*`

Demo online

lub

1a{0X$+_]:.+}ri*`

Demo online

oba działają poprzez zsumowanie poprzedniego rzędu z przesuniętym i podwójnym rzędem (w podobnym stylu do standardowej ręcznej konstrukcji trójkąta Pascala).

Podejście „bezpośrednie” wykorzystujące potęgi kartezjańskie (w przeciwieństwie do potęg całkowitych) do operacji mocy wielomianowej ma 24 bajty:

2,rim*{1b_0a*2@#+}%z1fb`

gdzie mapa jest niezwykle skomplikowana, tak że jej użycie jest krótsze %niż f:

2,rim*1fb_0af*2@f#.+z1fb`

ES6, 71 bajtów

n=>[...Array(n+1)].fill(n).map(b=(n,i)=>!i?1:i>n?0:b(--n,i-1)*2+b(n,i))

Prosta formuła rekurencyjna. Każdy hipersześcian jest tworzony przez przeniesienie poprzedniej jednostki hipersześcianu 1 przez N-ty wymiar. Oznacza to, że obiekty M-wymiarowe są powielane na początku i na końcu jednostki, ale także obiekty (M-1) zyskują dodatkowy wymiar, zamieniając się w obiekty M-wymiarowe. Innymi słowy c(n, m) = c(n - 1, m) * 2 + c(n - 1, m - 1). (Rzeczywiste przesłanie odwraca parametry, aby formuła generowała dane w żądanej kolejności).

Pomysłowo fillpozwala mapna podanie poprawnych argumentów funkcji rekurencyjnej, oszczędzając mi 6 bajtów.

Pyth, 10 9 bajtów

.<L.cQdhQ

Korzysta z algorytmu nCr, którego wszyscy używają.

05AB1E , 9 bajtów

Kod:

WƒNoZNc*,

Wyjaśnienie:

W          # Push input and store in Z
 ƒ         # For N in range(0, input + 1)
  No       # Compute 2**N
    ZNc    # Compute Z nCr N
       *   # Multiply
        ,  # Pop and print

Wykorzystuje kodowanie CP-1252.

Julia, 31 bajtów

n->[2^m*binomial(n,m)for m=0:n]

Jest to funkcja lambda, która przyjmuje liczbę całkowitą i zwraca tablicę liczb całkowitych. Aby go wywołać, przypisz go do zmiennej.

Dla każdego m od 0 do wejścia n liczymy liczbę ( n - m ) wymiarów hipersześcianów na granicy nadrzędnego n- wymiarowego hipersześcianu. Korzystając ze wzoru na Wikipedii, wystarczy 2 ^m * wybrać ( n , m ). Przypadek m = 0 odnosi się do samego n- modułu, więc wyjście zaczyna się od 1 niezależnie od danych wejściowych. Krawędzie są podane przez m = n , wierzchołki przez m = n - 1 itd.

Ruby, Rev B 57 bajtów

->n{a=[1]+[0]*n
(n*n).downto(n){|i|a[1+j=i%n]+=2*a[j]}
a}

Poprzednia wersja tylko za każdym razem skanowała używaną część tablicy. Ta rev skanuje całą tablicę podczas każdej iteracji. Jest to wolniejsze, ale oszczędza bajty. Kolejny bajt jest zapisywany przy użyciu 1 pętli do wykonania zadania 2.

Ruby, Rev A 61 bajtów

->n{a=[1]+[0]*n
n.times{|i|i.downto(0){|j|a[j+1]+=2*a[j]}}
a}

Zaczyna się od punktu i iteracyjnie tworzy następny wymiar

W każdej iteracji każdy istniejący element zwiększa wymiarowość i generuje 2 nowe elementy o pierwotnej wymiarowości. Na przykład dla kwadratu w płaszczyźnie poziomej, który jest przedłużony pionowo, aby stał się sześcianem:

1 twarz staje się sześcianem i generuje 1 parę ścian (1 powyżej, 1 poniżej)

4 krawędzie stają się powierzchniami i generują 4 pary krawędzi (4 powyżej, 4 poniżej)

4 wierzchołki stają się krawędziami i generują 4 pary wierzchołków (4 powyżej, 4 poniżej)

Niegolfowany w programie testowym

f=->n{a=[1]+[0]*n                  #make an array with the inital point and space for other dimensions
  n.times{|i|                      #iteratively expand dimension by dimension 
    i.downto(0){|j|a[j+1]+=2*a[j]} #iterating downwards (to avoid interferences) add the 2 new elements generated by each existing element.
  }
a}                                 #return the array

p f[gets.to_i]