17

El número de Eulerian A(n, m) es el número de permutaciones [1, 2, ..., n]en las que exactamente los melementos son mayores que el elemento anterior. Estos también se llaman subidas . Por ejemplo, si n = 3, hay 3! = 6 permutaciones de[1, 2, 3]

1 2 3
 < <  2 elements are greater than the previous

1 3 2
 < >  1 ...

2 1 3
 > <  1 ...

2 3 1
 < >  1 ...

3 1 2
 > <  1 ...

3 2 1
 > >  0 ...

Entonces las salidas para A(3, m)para men [0, 1, 2, 3]serán

A(3, 0) = 1
A(3, 1) = 4
A(3, 2) = 1
A(3, 3) = 0

Además, esta es la secuencia OEIS A173018 .

Reglas

Este es el código de golf, por lo que gana el código más corto.
La entrada nserá un número entero no negativo y mserá un número entero en el rango [0, 1, ..., n].

Casos de prueba

n   m   A(n, m)
0   0   1
1   0   1
1   1   0
2   0   1
2   1   1
2   2   0
3   0   1
3   1   4
3   2   1
3   3   0
4   0   1
4   1   11
4   2   11
4   3   1
4   4   0
5   1   26
7   4   1191
9   5   88234
10  5   1310354
10  7   47840
10  10  0
12  2   478271
15  6   311387598411
17  1   131054
20  16  1026509354985
42  42  0

code-golf math sequence combinatorics permutations millas
fuente

¿Algún límite n, m?

Loovjo

No hay límite, pero no es necesario que su envío pueda ejecutar completamente un caso de prueba en un cierto período de tiempo, solo tenga la lógica correcta. Preferiblemente, me gustaría que las presentaciones manejen valores de hasta 20, pero lo dejé sin un requisito de rendimiento para permitir soluciones de fuerza bruta que solo pueden funcionar n = 10.

millas

¿Puede la entrada tener m> = n, n> 0?

Feersum

¿No debería, "m será un número entero en el rango [0, 1, ..., n]" ser "... [0, 1, ..., n-1]"?

Jonathan Allan

@feersum Su solución puede admitir cualquiera msi lo desea, pero solo requiero que sea válida para 0 <= m <= n con 0 <= n .

millas

9

Jalea , 8 bytes

Œ!Z>2\Sċ

Pruébalo en línea! (lleva un tiempo) o verifique los casos de prueba más pequeños .

Cómo funciona

Œ!Z>2\Sċ  Main link. Arguments: n, m

Œ!        Generate the matrix of all permutations of [1, ..., n].
  Z       Zip/transpose, placing the permutations in the columns.
   >2\    Compare columns pairwise with vectorizing greater-than.
          This generates a 1 in the column for each rise in that permutation.
      S   Compute the vectorizing sum of the columns, counting the number of rises.
       ċ  Count how many times m appears in the computed counts.

Dennis
fuente

6

JavaScript (ES6), 50 46 45 bytes

f=(n,m,d=n-m)=>m?d&&f(--n,m)*++m+f(n,m-2)*d:1

Basado en la fórmula recursiva:

A(n, m) = (n - m)A(n - 1, m - 1) + (m + 1)A(n - 1, m)

Casos de prueba

Mostrar fragmento de código

f=(n,m,d=n-m)=>m?d&&f(--n,m)*++m+f(n,m-2)*d:1

console.log(f( 0,  0));  // 1
console.log(f( 1,  0));  // 1
console.log(f( 1,  1));  // 0
console.log(f( 2,  0));  // 1
console.log(f( 2,  1));  // 1
console.log(f( 2,  2));  // 0
console.log(f( 3,  0));  // 1
console.log(f( 3,  1));  // 4
console.log(f( 3,  2));  // 1
console.log(f( 3,  3));  // 0
console.log(f( 4,  0));  // 1
console.log(f( 4,  1));  // 11
console.log(f( 4,  2));  // 11
console.log(f( 4,  3));  // 1
console.log(f( 4,  4));  // 0
console.log(f( 5,  1));  // 26
console.log(f( 7,  4));  // 1191
console.log(f( 9,  5));  // 88234
console.log(f(10,  5));  // 1310354
console.log(f(10,  7));  // 47840
console.log(f(10, 10));  // 0
console.log(f(12,  2));  // 478271
console.log(f(15,  6));  // 311387598411
console.log(f(17,  1));  // 131054
console.log(f(20, 16));  // 1026509354985
console.log(f(42, 42));  // 0

Expandir fragmento

Arnauld
fuente

4

MATL , 10 bytes

:Y@!d0>s=s

Pruébalo en línea!

Explicación

Considere como ejemplo las entradas n=3,m=1 . Puede colocar un %símbolo para comentar el código desde ese punto en adelante y así ver los resultados intermedios. Por ejemplo, el enlace muestra la pila después del primer paso.

:      % Input n implicitly. Push [1 2 ... n]
       % STACK: [1 2 ... n]
Y@     % Matrix of all permutations, one on each row
       % STACK: [1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1]
!      % Transpose
       % STACK: [1 1 2 2 3 3; 2 3 1 3 1 2; 3 2 3 1 2 1]
d      % Consecutive differences along each column
       % STACK: [1 2 -1 1 -2 -1; 1 -1 2 -2 1 -1]
0>     % True for positive entries
       % STACK: [1 1 0 1 0 0; 1 0 1 0 1 0]
s      % Sum of each column
       % STACK: [2 1 1 1 1 0]
=      % Input m implicitly. Test each entry for equality with m
       % STACK: [0 1 1 1 1 0]
s      % Sum. Implicitly display
       % STACK: 4

Luis Mendo
fuente

4

CJam ( 21 19 bytes - o 18 si el orden de los argumentos es libre)

{\e!f{2ew::>1b=}1b}

Este es un bloque anónimo (función) que toma n men la pila. (Si se permite tomar m nla pila, entonces \se puede guardar). Calcula todas las permutaciones y filtros, por lo que el conjunto de pruebas en línea debe ser bastante limitado.

Gracias a Martin por señalar una aproximación a filter-with-parameter.

Disección

{        e# Define a block. Stack: n m
  \      e#   Flip the stack to give m n
  e!f{   e#   Generate permutations of [0 .. n-1] and map with parameter m
    2ew  e#     Stack: m perm; generate the list of n-1 pairs of consecutive
         e#     elements of perm
    ::>  e#     Map each pair to 1 if it's a rise and 0 if it's a fall
    1b   e#     Count the falls
    =    e#     Map to 1 if there are m falls and 0 otherwise
  }
  1b     e#   Count the permutations with m falls
}

Tenga en cuenta que los números de Eulerian son simétricos: E(n, m) = E(n, n-m)por lo tanto, es irrelevante si cuenta caídas o subidas.

Eficientemente: 32 bytes

{1a@{0\+_ee::*(;\W%ee::*W%.+}*=}

Conjunto de pruebas en línea .

Esto implementa la recurrencia en filas enteras.

{          e# Define a block. Stack: n m
  1a@      e#   Push the row for n=0: [1]; and rotate n to top of stack
  {        e#   Repeat n times:
           e#     Stack: m previous-row
    0\+_   e#     Prepend a 0 to the row and duplicate
    ee::*  e#     Multiply each element by its index
           e#     This gives A[j] = j * E(i-1, j-1)
    (;     e#     Pop the first element, so that A[j] = (j+1) * E(i-1, j)
    \W%    e#     Get the other copy of the previous row and reverse it
    ee::*  e#     Multiply each element by its index
           e#     This gives B[j] = j * E(i-1, i-1-j)
    W%     e#     Reverse again, giving B[j] = (i-j) * E(i-1, j-1)
    .+     e#     Pointwise addition
  }*
  =        e#   Extract the element at index j
}

Peter Taylor
fuente

Es más corto para evitar la variable mediante el uso de un mapa: {e!f{2ew::>1b=}1e=}. O solo por diversión:{e!f{2ew::>+:-}0e=}

Martin Ender

Eso fue estúpido, por supuesto. El 1e=en la primera solución puede ser 1b.

Martin Ender

Puede usar su propio orden de argumentos

millas del

3

Python, 55 56 bytes

a=lambda n,m:n>=m>0and(n-m)*a(n-1,m-1)-~m*a(n-1,m)or m<1

Todas las pruebas en repl.it

Aplica la fórmula recursiva en OEIS.
Tenga en cuenta que +(m+1)*a(n-1,m)se juega al golf -~m*a(n-1,m).
(Puede devolver valores booleanos para representar 1o 0. Devuelve Truecuando n<0 and m<=0o m<0.)

Jonathan Allan
fuente

Hay varias otras formas de manejar los casos límite. Es suficiente para manejar m<1 ? 1 : m==n ? 0 : formula, de manera equivalente m%n<1 ? (m<1) : formula; o alternativamente m<1 ? (n>=0) : formula.

Peter Taylor

Lo tengo, solo actualizando gracias

Jonathan Allan

Como nuestras respuestas son muy similares y la suya se publicó primero (y es más corta), continuaré y eliminaré la mía.

Loovjo

@Loovjo Sin embargo, un poco de ajustes frenéticos :( ¡Recibiste un voto mío de todos modos!

Jonathan Allan el

3

Mathematica, 59 56 bytes

_~f~0=1
n_~f~m_:=If[m>n,0,(n-m)f[n-1,m-1]+(m+1)f[n-1,m]]

Y aquí hay una versión de 59 bytes que implementa la definición más literalmente:

Count[Count@1/@Sign/@Differences/@Permutations@Range@#,#2]&

Martin Ender
fuente

¿Por qué no solo f[n_,m_]:=...por 49?

Jonathan Allan

@ JonathanAllan No estoy seguro de entender. ¿Cómo maneja eso el caso base?

Martin Ender

OK, algo se almacenó en caché, solo lo hice en una nueva hoja de trabajo y falló con el límite de recursión. :)

Jonathan Allan

También existe la fórmula que usa 46 bytes Sum[Binomial[#+1,k](#2+1-k)^#(-1)^k,{k,0,#2}]&que podrían ser posibles para jugar más golf

millas del

3

Python, 53 bytes

t=lambda n,k:n and(n-k)*t(n-1,k-1)-~k*t(n-1,k)or k==0

Recursión de OEIS. Salidas booleanas Truecomo 1cuando n==k.

xnor
fuente

2

MATLAB / Octave, 40 bytes

@(n,m)sum(sum(diff((perms(1:n))')>0)==m)

Este es un puerto de mi respuesta MATL, en forma de una función anónima. Llámalo como ans(7,4).

Pruébalo en Ideone .

Luis Mendo
fuente

2

Lenguaje GameMaker, 62 bytes

Este es un script recursivo Abasado en la fórmula de @ Arnauld.

n=argument0;m=argument1;return (n-m)*A(n-1,m-1)+(m+1)*A(n-1,m)

Timtech
fuente

¡No he visto ESO en mucho tiempo!

tomsmeding

1

Perl, 98 bytes

sub a{my($b,$c)=@_;return$c?$c>$b?0:($b-$c)*a($b-1,$c-1)+($c+1)*a($b-1,$c):1;}print a(@ARGV[0,1]);

Basado en la misma propiedad que la respuesta de Arnauld.

Gabriel Benamy
fuente

1

R, 72 bytes

Función recursiva que sigue la lógica en OEIS.

A=function(n,m)if(!m)1 else if(m-n)0 else(n-m)*A(n-1,m-1)+(m+1)*A(n-1,m)

Este desafío resultó ser bastante cercano entre los diferentes enfoques que probé. Por ejemplo, usar la fórmula de wikipedia y recorrer la suma dio como resultado 92 bytes:

function(n,m){s=0;if(!n)1 else for(k in -1:m+1)s=c(s,(-1)^k*choose(n+1,k)*(m+1-k)^n);sum(s)}

o la versión vectorizada para 87 bytes:

function(n,m)if(!m)1 else sum(sapply(-1:m+1,function(k)(-1)^k*choose(n+1,k)*(m+1-k)^n))

y finalmente la solución de fuerza bruta (103 bytes) que genera una matriz de todas las permutaciones usando el permutepaquete y la función allPerms. Sin n<8embargo, este enfoque solo funciona .

function(n,m){if(!m)1 else sum(apply(rbind(1:n,permute:::allPerms(n)),1,function(x)sum(diff(x)>0))==m)}

Billywob
fuente

1

Raqueta 141 bytes

(count(λ(x)(= x m))(for/list((t(permutations(range 1(+ 1 n)))))(count
(λ(x)x)(for/list((i(sub1 n)))(>(list-ref t(+ 1 i))(list-ref t i))))))

Sin golf:

(define (f n m)
  (let* ((l (range 1 (add1 n)))                ; create a list till n
         (pl (permutations l))                 ; get all permutations
         (enl (for/list ((t pl))               ; check each permutation; 
                (define rl
                  (for/list ((i (sub1 n)))     ; check if an element is a 'rise'
                    (> (list-ref t (add1 i))
                       (list-ref t i))))
                (count (lambda(x)x) rl))))     ; how many numbers are 'rises'
    (count (lambda(x) (= x m)) enl)))          ; how many permutations had m rises
                                               ; i.e. Eulerian number

Pruebas:

(f 3 0)
(f 3 1)
(f 3 2)
(f 3 3)
(f 4 2)
(f 5 1)
(f 7 4)

Salida:

rnso
fuente

1

En realidad , 21 19 bytes

Esta respuesta usa un algoritmo similar al que Dennis usa en su respuesta Jelly . La definición original cuenta <mientras yo cuento> . Esto termina siendo equivalente al final. Sugerencias de golf bienvenidas. Pruébalo en línea!

;R╨`;\ZdX"i>"£MΣ`Mc

No golfista

         Implicit input m, then n.
;        Duplicate n. Stack: n, n, m
R        Push range [1..n].
╨        Push all n-length permutations of the range.
`...`M   Map the following function over each permutation p.
  ;\       Duplicate and rotate p so that we have a list of the next elements of p.
  Z        Zip rot_p and p.
           (order of operands here means the next element is first,
            so we need to use > later)
  dX       Remove the last pair as we don't compare the last and first elements of the list.
  "i>"£    Create a function that will flatten a list and check for a rise.
  M        Map that function over all the pairs.
  Σ        Count how many rises there are in each permutation.
c        Using the result of the map and the remaining m, 
          count how many permutations have m rises.
         Implicit return.

Sherlock9
fuente

1

Swift 3 , 8288 Bytes

func A(_ n:Int,_ m:Int)->Int{return m<1 ?1:n>m ?(n-m)*A(n-1,m-1)+(m+1)*A(n-1,m):0}

La misma fórmula recursiva en un idioma que definitivamente no es para el golf

apolíneo
fuente

0

J, 28 bytes

+/@((!>:)~*(^~#\.)*_1^])i.,]

Usa la fórmula

fórmula

Uso

   f =: +/@((!>:)~*(^~#\.)*_1^])i.,]
   0 f 0
1
   1 f 0
1
   1 f 1
0
   (f"+i.,]) 6
1 57 302 302 57 1 0
   20x f 16x
1026509354985

Explicación

+/@((!>:)~*(^~#\.)*_1^])i.,]  Input: n (LHS), m (RHS)
                        i.    Range [0, 1, ..., m-1]
                           ]  Get m
                          ,   Join to get k = [0, 1, ..., m]
                      ]       Get k
                   _1^        Raise -1 to each in k
              #\.               Get the length of each suffix of k
                                Forms the range [m+1, m, ..., 2, 1]
            ^~                  Raise each value by n
                  *           Multiply elementwise with (-1)^k
    (   )~                      Commute operators
      >:                        Increment n
     !                          Binomial coefficient, C(n+1, k)
          *                   Multiply elementwise
+/@                           Reduce by addition to get the sum and return

millas
fuente

Calcule el número euleriano

Reglas

Casos de prueba

Respuestas:

Jalea , 8 bytes

Cómo funciona

JavaScript (ES6), 50 46 45 bytes

Casos de prueba

MATL , 10 bytes

Explicación

CJam ( 21 19 bytes - o 18 si el orden de los argumentos es libre)

Disección

Eficientemente: 32 bytes

Python, 55 56 bytes

Mathematica, 59 56 bytes

Python, 53 bytes

MATLAB / Octave, 40 bytes

Lenguaje GameMaker, 62 bytes

Perl, 98 bytes

R, 72 bytes

Raqueta 141 bytes

En realidad , 21 19 bytes

Swift 3 , 8288 Bytes

J, 28 bytes

Uso

Explicación