Écrivez une fonction ou un programme qui génère le nombre de chaque type d'élément (sommet, arête, face, etc.) d'un hypercube à N dimensions.

Par exemple, le cube en 3 dimensions a 1 cellule (soit 1 cube en 3 dimensions), 6 faces (soit 6 cubes en 2 dimensions), 12 arêtes (soit 12 cubes en 2 dimensions) et 8 sommets (soit 8 0 dimensions) cubes).

Plus de détails sur les éléments Hypercube peuvent être trouvés ici

Vous pouvez également consulter la séquence OEIS suivante .

Contribution

Votre code prendra en entrée (via STDIN ou un paramètre de fonction ou des choses similaires) un entier supérieur ou égal à 0, qui est la dimension de l'hypercube.

Votre code doit théoriquement fonctionner pour toute entrée> = 0, sans tenir compte des problèmes de mémoire et de temps (c'est-à-dire que la vitesse et les débordements de pile potentiels ne sont pas un problème pour votre réponse si l'entrée est grande). Les entrées données comme cas de test ne seront pas supérieures à 12.

Production

Vous sortirez une liste de tous les éléments de l'hypercube, en commençant par l'élément "dimension la plus élevée". Par exemple, pour un cube (entrée = 3), vous afficherez la liste [1,6,12,8](1 cellule, 6 faces, 12 arêtes, 8 sommets).

Le format de la liste dans la sortie est relativement libre, tant qu'il ressemble à une liste.

Vous pouvez exporter le résultat vers STDOUT ou le renvoyer à partir d'une fonction.

Cas de test

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]

Notation

Il s'agit de code-golf , donc la réponse la plus courte en octets l'emporte.

Samau , 8 5 octets

Enregistré 3 octets grâce à Dennis .

▌2\$ⁿ

Vidage hexadécimal (Samau utilise le codage CP737):

dd 32 2f 24 fc

Explication:

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

Convoluer deux vecteurs équivaut à multiplier deux polynômes . De même, prendre la n-ième puissance de convolution équivaut à prendre la n-ième puissance d'un polynôme.

J, 13 octets

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

Inspiré par la réponse PARI / GP de @ alephalpha . Essayez en ligne avec J.js .

Contexte

Par le théorème binomial,

Ainsi, la sortie pour l'entrée n consiste précisément en les coefficients du polynôme ci-dessus.

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 octets

1i:"2:X+

Inspiré par la réponse PARI / GP de @ alephalpha .

Essayez-le en ligne! (utilise Y+pour MATL moderne)

Comment ça fonctionne

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 octets

Q:q"H@^G@Xn*

Essayez-le en ligne

Explication

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

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

Ma première réponse Mathematica! Ceci est une pure fonction qui utilise la même approche que PARI / GP de Alephalpha réponse . Nous construisons le polynôme (1+2x)^net obtenons la liste des coefficients, classés par ordre croissant de puissance (c'est-à-dire constant en premier).

Exemple d'utilisation:

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

APL, 15 11 octets

1,(2*⍳)×⍳!⊢

Il s'agit d'un train de fonctions monadique qui accepte un entier à droite et renvoie un tableau d'entiers.

Explication, appel de l'entrée 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

Essayez-le en ligne

4 octets enregistrés grâce à Dennis!

PARI / GP, 20 15 octets

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

Gelée, 8 octets

0rð2*×c@

Je devrais vraiment arrêter d'écrire Jelly sur mon téléphone.

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.

Essayez-le ici .

TI-BASIC, 10 octets

3^Ansbinompdf(Ans,2/3

CJam ( 17 14 octets)

ri_3@#_2+@#\b`

Démo en ligne

Cette approche utilise la fonction de génération ordinaire (x + 2)^n. L'OEIS le mentionne (2x + 1)^n, mais cette question indexe les coefficients dans l'ordre inverse. Je me donne un coup de pied pour ne pas penser à inverser la gf jusqu'à ce que je voie la mise à jour d'Alephalpha de la réponse PARI / GP qui a fait de même.

L'astuce intéressante de cette réponse est d'utiliser des puissances entières pour le fonctionnement en puissance polynomiale en fonctionnant dans une base supérieure à tout coefficient possible. En général, étant donné un polynôme p(x)dont les coefficients sont tous des entiers non négatifs inférieurs à b, p(b)est une breprésentation de base des coefficients (parce que les monômes individuels ne se "chevauchent"). Clairement(x + 2)^n aura des coefficients qui sont des entiers positifs et qui se résument à 3^n, donc chacun d'eux sera individuellement inférieur à 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

Approches alternatives: à 17 octets

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

Démo en ligne

ou

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

Démo en ligne

les deux fonctionnent en additionnant la ligne précédente avec une ligne décalée et doublée (dans un style similaire à la construction manuelle standard du triangle de Pascal).

Une approche "directe" utilisant des puissances cartésiennes (par opposition aux puissances entières) pour le fonctionnement de puissance polynomiale, se présente à 24 octets:

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

où la carte est, inhabituellement, suffisamment compliquée pour être plus courte à utiliser %que f:

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

ES6, 71 octets

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

Formule récursive simple. Chaque hypercube est créé en déplaçant l'unité d'hypercube 1 précédente à travers la Nième dimension. Cela signifie que les objets dimensionnels M sont dupliqués au début et à la fin de l'unité, mais que les objets dimensionnels (M-1) acquièrent une dimension supplémentaire, se transformant en objets dimensionnels M. En d'autres termes,c(n, m) = c(n - 1, m) * 2 + c(n - 1, m - 1) . (La soumission réelle inverse les paramètres afin que la formule s'affiche dans l'ordre souhaité.)

Ingénieusement, fillpermet mapde fournir les bons arguments à la fonction récursive, me faisant économiser 6 octets.

Pyth, 10 9 octets

.<L.cQdhQ

Utilise l'algorithme nCr que tout le monde semble utiliser.

05AB1E , 9 octets

Code:

WƒNoZNc*,

Explication:

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

Utilise l'encodage CP-1252.

Julia, 31 octets

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

Il s'agit d'une fonction lambda qui accepte un entier et renvoie un tableau d'entiers. Pour l'appeler, affectez-le à une variable.

Pour chaque m de 0 à l'entrée n , nous comptons le nombre d' hypercubes ( n - m ) -dimensionnels à la frontière de l' hypercube n- dimensionnel parent . En utilisant la formule sur Wikipedia, c'est simplement 2 ^m * choisissez ( n , m ). Le cas de m = 0 se réfère au n- cube lui-même, donc la sortie commence par 1 quelle que soit l'entrée. Les arêtes sont données par m = n , les sommets par m = n - 1, etc.

Ruby, Rev B 57 octets

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

La version précédente a seulement analysé la partie utilisée de la baie à chaque fois. Cette rév analyse l'ensemble du tableau à chaque itération. C'est plus lent, mais cela économise des octets. Un octet supplémentaire est enregistré en utilisant 1 boucle pour faire le travail de 2.

Ruby, Rev A 61 octets

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

Commence par un point et crée de manière itérative la dimension suivante

À chaque itération, chaque élément existant augmente en dimensionnalité et génère 2 nouveaux éléments de sa dimensionnalité d'origine. Par exemple, pour un carré dans le plan horizontal qui se prolonge verticalement pour devenir un cube:

La 1 face devient un cube et génère 1 paire de faces (1 au dessus, 1 en dessous)

Les 4 arêtes deviennent des faces et génèrent 4 paires d'arêtes (4 au dessus, 4 en dessous)

Les 4 sommets deviennent des arêtes et génèrent 4 paires de sommets (4 au dessus, 4 en dessous)

Non testé dans le programme de test

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]