Elementos hipercubos

19

Escriba una función o programa que genere el número de cada tipo de elemento (vértice, arista, cara, etc.) de un hipercubo N-dimensional.

Como ejemplo, el cubo tridimensional tiene 1 celda (es decir, 1 cubo tridimensional), 6 caras (es decir, 6 cubos bidimensionales), 12 aristas (es decir, 12 cubos bidimensionales) y 8 vértices (es decir, 8 dimensiones). cubitos).

Puede encontrar más detalles sobre los elementos de Hypercube aquí

También puede echar un vistazo a la siguiente secuencia OEIS .

Entrada

Su código tomará como entrada (a través de STDIN o un parámetro de función o cosas similares) un número entero mayor o igual a 0, que es la dimensión del hipercubo.

Su código tiene que funcionar teóricamente para cualquier entrada> = 0, sin tener en cuenta los problemas de memoria y tiempo (es decir, la velocidad y los desbordamientos potenciales de la pila no son un problema para su respuesta si la entrada es grande). Las entradas dadas como casos de prueba no serán superiores a 12.

Salida

Superará una lista de todos los elementos del hipercubo, comenzando con el elemento de "dimensión más alta". Por ejemplo, para un cubo (input = 3), generará la lista [1,6,12,8](1 celda, 6 caras, 12 aristas, 8 vértices).

El formato de la lista en la salida es relativamente libre, siempre que parezca una lista.

Puede enviar el resultado a STDOUT o devolverlo desde una función.

Casos de prueba

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]

Puntuación

Este es el , por lo que gana la respuesta más corta en bytes.

Fatalizar
fuente

Respuestas:

10

Samau , 8 5 bytes

Guardado 3 bytes gracias a Dennis .

▌2\$ⁿ

Volcado hexadecimal (Samau utiliza la codificación CP737):

dd 32 2f 24 fc

Explicación:

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

Convolucionar dos vectores es equivalente a multiplicar dos polinomios . Del mismo modo, tomar la enésima potencia de convolución es equivalente a tomar la enésima potencia de un polinomio.

alephalpha
fuente
11

J, 13 bytes

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

Inspirado por la respuesta PARI / GP de @ alephalpha . Pruébelo en línea con J.js .

Antecedentes

Por el teorema binomial,

fórmula

Por lo tanto, la salida para la entrada n consiste precisamente en los coeficientes del polinomio anterior.

Código

[: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.
Dennis
fuente
10

MATL, 8 bytes

1i:"2:X+

Inspirado por la respuesta PARI / GP de @ alephalpha .

Pruébalo en línea! (usosY+ para MATL de hoy en día)

Cómo funciona

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].
Dennis
fuente
55
Mi primera respuesta MATL.
Dennis
¡Y excelente! Es un honor que haya usado este idioma :-)
Luis Mendo
1
Hermosa. ¡Todos están empezando a subirse al tren de MATL ahora!
rayryeng - Restablece a Mónica el
@rayryeng Te extrañamos :-)
Luis Mendo
8

MATL , 12 bytes

Q:q"H@^G@Xn*

Pruébalo en línea

Explicación

         % 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
Luis Mendo
fuente
8

Mathematica, 29 bytes

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

¡Mi primera respuesta de Mathematica! Esta es una pura función que utiliza el mismo enfoque que PARI / GP de Alephalpha respuesta . Construimos el polinomio (1+2x)^ny obtenemos la lista de coeficientes, enumerados en orden de potencia ascendente (es decir, constante primero).

Ejemplo de uso:

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

APL, 15 11 bytes

1,(2*⍳)×⍳!⊢

Este es un tren de funciones monádicas que acepta un número entero a la derecha y devuelve una matriz entera.

Explicación, llamando a la entrada 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

Pruébalo en línea

¡Guardado 4 bytes gracias a Dennis!

Alex A.
fuente
6

PARI / GP, 20 15 bytes

n->Vec((x+2)^n)
alephalpha
fuente
5

Jalea, 8 bytes

0rð2*×c@

Realmente debería dejar de escribir Jelly en mi teléfono.

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.

Probarlo aquí .

lirtosiast
fuente
4

TI-BASIC, 10 bytes

3^Ansbinompdf(Ans,2/3
lirtosiast
fuente
Creo que esta es una de las soluciones más interesantes. No sé si hubiera pensado alguna vez binompdf.
PhiNotPi
4

CJam ( 17 14 bytes)

ri_3@#_2+@#\b`

Demostración en línea

Este enfoque utiliza la función generadora ordinaria (x + 2)^n. La OEIS menciona(2x + 1)^n , pero esta pregunta indexa los coeficientes en el orden opuesto. Me estoy pateando por no pensar en revertir el gf hasta que vi la actualización de Alephalpha a la respuesta PARI / GP que hizo lo mismo.

El truco interesante en esta respuesta es utilizar potencias enteras para la operación de potencia polinómica operando en una base más alta que cualquier coeficiente posible. En general, dado un polinomio p(x)cuyos coeficientes son todos enteros no negativos menores que b, p(b)es una brepresentación base de los coeficientes (porque los monomios individuales no se "superponen"). Claramente (x + 2)^ntendrá coeficientes que son enteros positivos y que suman 3^n, por lo que cada uno de ellos será individualmente menor que 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

Enfoques alternativos: a 17 bytes

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

Demostración en línea

o

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

Demostración en línea

ambos trabajan sumando la fila anterior con una fila desplazada y doblada (en un estilo similar a la construcción manual estándar del triángulo de Pascal).

Un enfoque "directo" que usa potencias cartesianas (en oposición a las potencias enteras) para la operación de potencia polinómica, viene en 24 bytes:

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

donde el mapa es, inusualmente, lo suficientemente complicado como para que sea más corto de usar %que f:

2,rim*1fb_0af*2@f#.+z1fb`
Peter Taylor
fuente
3

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))

Fórmula recursiva simple. Cada hipercubo se crea moviendo la unidad anterior del hipercubo 1 a través de la enésima dimensión. Esto significa que los objetos M-dimensionales se duplican al comienzo y al final de la unidad, pero también los objetos dimensionales (M-1) ganan una dimensión extra, convirtiéndose en objetos M-dimensionales. En otras palabras,c(n, m) = c(n - 1, m) * 2 + c(n - 1, m - 1) . (El envío real invierte los parámetros para que la fórmula salga en el orden deseado).

Ingeniosamente, fillpermite mapproporcionar los argumentos correctos a la función recursiva, ahorrándome 6 bytes.

Neil
fuente
3

Pyth, 10 9 bytes

.<L.cQdhQ

Utiliza el algoritmo nCr que todo el mundo parece estar usando.

orlp
fuente
L-map guarda un byte:.<L.cQdhQ
isaacg
2

05AB1E , 9 bytes

Código:

WƒNoZNc*,

Explicación:

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

Utiliza la codificación CP-1252.

Adnan
fuente
2

Julia, 31 bytes

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

Esta es una función lambda que acepta un entero y devuelve una matriz de enteros. Para llamarlo, asígnelo a una variable.

Para cada m desde 0 hasta la entrada n , contamos el número de hipercubos dimensionales ( n - m ) en el límite del hipercubo n- dimensional primario . Usando la fórmula en Wikipedia, es simplemente 2 m * elegir ( n , m ). El caso de m = 0 se refiere al n -cubo en sí mismo, por lo que la salida comienza con 1 independientemente de la entrada. Los bordes están dados por m = n , los vértices por m = n - 1, etc.

Alex A.
fuente
1

Ruby, Rev B 57 bytes

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

La rev anterior solo escaneaba a través de la parte utilizada de la matriz cada vez. Esta revolución explora toda la matriz en cada iteración. Esto es más lento, pero ahorra bytes. Un byte adicional se guarda usando 1 bucle para hacer el trabajo de 2.

Ruby, Rev A 61 bytes

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

Comienza con un punto y crea iterativamente la siguiente dimensión

En cada iteración, cada elemento existente aumenta en dimensionalidad y genera 2 elementos nuevos de su dimensionalidad original. Por ejemplo, para un cuadrado en el plano horizontal que se extiende verticalmente para convertirse en un cubo:

La 1 cara se convierte en un cubo y genera 1 par de caras (1 arriba, 1 abajo)

Los 4 bordes se convierten en caras y generan 4 pares de bordes (4 arriba, 4 abajo)

Los 4 vértices se convierten en bordes y generan 4 pares de vértices (4 arriba, 4 abajo)

Sin golf en el programa de prueba

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]
Level River St
fuente