Schreiben Sie eine Funktion oder ein Programm, das die Nummer jedes Elementtyps (Scheitelpunkt, Kante, Fläche usw.) eines N-dimensionalen Hyperwürfels ausgibt.

Beispielsweise hat der dreidimensionale Würfel 1 Zelle (dh 1 dreidimensionaler Würfel), 6 Flächen (dh 6 zweidimensionale Würfel), 12 Kanten (dh 12 zweidimensionale Würfel) und 8 Eckpunkte (dh 8 0-dimensional) Würfel).

Weitere Details zu Hypercube-Elementen finden Sie hier

Sie können sich auch die folgende OEIS-Sequenz ansehen .

Eingang

Ihr Code nimmt als Eingabe (über STDIN oder einen Funktionsparameter oder ähnliche Dinge) eine ganze Zahl größer oder gleich 0 an, die die Dimension des Hyperwürfels darstellt.

Ihr Code muss theoretisch für jede Eingabe> = 0 funktionieren, wobei Speicher- und Zeitprobleme unberücksichtigt bleiben (dh Geschwindigkeit und potenzielle Stapelüberläufe sind für Ihre Antwort kein Problem, wenn die Eingabe groß ist). Als Testfälle angegebene Eingaben werden nicht höher als 12 sein.

Ausgabe

Sie geben eine Liste aller Elemente des Hypercubes aus, beginnend mit dem Element "höchste Dimension". Für einen Würfel (Eingabe = 3) geben Sie beispielsweise die Liste aus [1,6,12,8](1 Zelle, 6 Flächen, 12 Kanten, 8 Eckpunkte).

Das Format der Liste in der Ausgabe ist relativ frei, solange es wie eine Liste aussieht.

Sie können das Ergebnis an STDOUT ausgeben oder von einer Funktion zurückgeben.

Testfälle

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]

Wertung

Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.

Samau , 8 5 Bytes

3 Bytes gespart dank Dennis .

▌2\$ⁿ

Hex-Dump (Samau verwendet CP737-Codierung):

dd 32 2f 24 fc

Erläuterung:

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

Das Falten zweier Vektoren entspricht dem Multiplizieren zweier Polynome . In ähnlicher Weise ist das Nehmen der n-ten Faltungskraft gleichbedeutend mit dem Nehmen der n-ten Potenz eines Polynoms.

J, 13 Bytes

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

Inspiriert von der PARI / GP-Antwort von @ alephalpha . Probieren Sie es online mit J.js .

Hintergrund

Nach dem Binomialsatz

Somit ist der Ausgang für den Eingang n genau aus den Koeffizienten des obigen Polynoms.

Code

[: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 Bytes

1i:"2:X+

Inspiriert von der PARI / GP-Antwort von @ alephalpha .

Probieren Sie es online! (verwendet Y+für moderne MATL)

Wie es funktioniert

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 Bytes

Q:q"H@^G@Xn*

Probieren Sie es online aus

Erläuterung

         % 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 Bytes

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

Meine erste Mathematica-Antwort! Dies ist eine reine Funktion, die den gleichen Ansatz wie Alephalphas PARI / GP verwendet Antwort verwendet . Wir konstruieren das Polynom (1+2x)^nund erhalten die Liste der Koeffizienten, sortiert nach aufsteigender Potenz (dh konstant zuerst).

Anwendungsbeispiel:

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

APL, 15 11 Bytes

1,(2*⍳)×⍳!⊢

Dies ist ein monadischer Funktionszug, der eine Ganzzahl auf der rechten Seite akzeptiert und ein Ganzzahl-Array zurückgibt.

Erklärung, Aufruf der Eingabe 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

Probieren Sie es online aus

4 Bytes gespart dank Dennis!

PARI / GP, 20 15 Bytes

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

Gelee, 8 Bytes

0rð2*×c@

Ich sollte wirklich aufhören, Jelly auf mein Handy zu schreiben.

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.

Probieren Sie es hier aus .

TI-BASIC, 10 Bytes

3^Ansbinompdf(Ans,2/3

CJam ( 17 14 Bytes)

ri_3@#_2+@#\b`

Online-Demo

Dieser Ansatz verwendet die gewöhnliche Erzeugungsfunktion (x + 2)^n. Der OEIS erwähnt(2x + 1)^n , aber diese Frage indiziert die Koeffizienten in umgekehrter Reihenfolge. Ich mache mir den Kopf zerbrochen, weil ich nicht daran gedacht habe, die Gf umzukehren, bis ich Alephalphas Aktualisierung der PARI / GP-Antwort gesehen habe, die dasselbe tat.

Der interessante Trick bei dieser Antwort besteht darin, ganzzahlige Potenzen für die polynomiale Potenzoperation zu verwenden, indem mit einer Basis gearbeitet wird, die höher ist als jeder mögliche Koeffizient. Im Allgemeinen ist bei einem Polynom, p(x)dessen Koeffizienten alle nicht negative ganze Zahlen sind b, p(b)eine Basisdarstellung bder Koeffizienten (da sich die einzelnen Monome nicht "überlappen"). Es ist klar (x + 2)^n, dass Koeffizienten positive ganze Zahlen sind, die sich summieren 3^n, sodass jeder von ihnen einzeln kleiner als ist 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

Alternative Ansätze: bei 17 Bytes

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

Online-Demo

oder

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

Online-Demo

Beide arbeiten, indem sie die vorherige Zeile mit einer versetzten und doppelten Zeile summieren (in einem ähnlichen Stil wie bei der manuellen Standardkonstruktion von Pascals Dreieck).

Ein "direkter" Ansatz unter Verwendung kartesischer Potenzen (im Gegensatz zu ganzzahligen Potenzen) für die polynomiale Potenzoperation ergibt 24 Bytes:

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

Wo die Karte ungewöhnlich kompliziert genug ist, um kürzer zu sein %als f:

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

ES6, 71 Bytes

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

Einfache rekursive Formel. Jeder Hyperkubus wird erstellt, indem die vorherige Einheit Hyperkubus 1 durch die N-te Dimension bewegt wird. Dies bedeutet, dass die M-dimensionalen Objekte am Anfang und Ende der Einheit dupliziert werden, aber auch die (M-1) -dimensionalen Objekte erhalten eine zusätzliche Dimension und werden zu M-dimensionalen Objekten. Mit anderen Worten,c(n, m) = c(n - 1, m) * 2 + c(n - 1, m - 1) . (Die tatsächliche Übermittlung kehrt die Parameter um, sodass die Formel in der gewünschten Reihenfolge ausgegeben wird.)

Genialerweise fillerlaubt mapes, die richtigen Argumente für die rekursive Funktion bereitzustellen, was mir 6 Bytes spart.

Pyth, 10 9 Bytes

.<L.cQdhQ

Verwendet den nCr-Algorithmus, den anscheinend jeder verwendet.

05AB1E , 9 Bytes

Code:

WƒNoZNc*,

Erläuterung:

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

Verwendet CP-1252-Codierung.

Julia, 31 Bytes

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

Dies ist eine Lambda-Funktion, die eine Ganzzahl akzeptiert und ein Ganzzahl-Array zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Für jedes m von 0 bis zur Eingabe n zählen wir die Anzahl der ( n - m ) -dimensionalen Hyperwürfel an der Grenze des übergeordneten n -dimensionalen Hyperwürfels. Mit der Formel auf Wikipedia sind es einfach 2 ^m * wähle ( n , m ). Der Fall von m = 0 bezieht sich auf den n- Würfel selbst, sodass die Ausgabe unabhängig von der Eingabe mit 1 beginnt. Kanten sind gegeben durch m = n , Eckpunkte durch m = n - 1 usw.

Ruby, Rev. B 57 Bytes

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

Die vorherige Version hat jedes Mal nur den verwendeten Teil des Arrays durchsucht. Diese Version durchsucht das gesamte Array bei jeder Iteration. Das ist langsamer, spart aber Bytes. Ein weiteres Byte wird gespeichert, indem 1 Schleife verwendet wird, um die Arbeit von 2 zu erledigen.

Ruby, Rev A 61 Bytes

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

Beginnt mit einem Punkt und erstellt iterativ die nächste Dimension

In jeder Iteration nimmt die Dimension jedes vorhandenen Elements zu und erzeugt 2 neue Elemente seiner ursprünglichen Dimension. Zum Beispiel für ein Quadrat in der horizontalen Ebene, das vertikal erweitert wird, um ein Würfel zu werden:

Die 1 Fläche wird zu einem Würfel und erzeugt 1 Paar Flächen (1 oben, 1 unten)

Die 4 Kanten werden zu Flächen und erzeugen 4 Kantenpaare (4 oben, 4 unten)

Die 4 Eckpunkte werden zu Kanten und erzeugen 4 Paare von Eckpunkten (4 oben, 4 unten)

Ungolfed im Testprogramm

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]