17

O número euleriano A(n, m) é o número de permutações [1, 2, ..., n]em que exatamente os melementos são maiores que o elemento anterior. Estes também são chamados de aumentos . Por exemplo, se n = 3houver 3! = 6 permutações 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 ...

Assim, as saídas para A(3, m)por mem [0, 1, 2, 3]será

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

Além disso, esta é a sequência OEIS A173018 .

Regras

Isso é código-golfe, então o código mais curto vence.
A entrada nserá um número inteiro não negativo e mserá um número inteiro no intervalo [0, 1, ..., n].

Casos de teste

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 milhas
fonte

Algum limite n, m?

Loovjo 19/10/16

Não há limite, mas não é necessário que seu envio seja capaz de executar completamente um caso de teste em um determinado período de tempo, apenas com a lógica correta. De preferência, eu gostaria que os envios lidassem com valores de até 20, mas deixei sem um requisito de desempenho para permitir soluções de força bruta que podem funcionar apenas até n = 10.

miles

A entrada pode ter m> = n, n> 0?

feersum

Não deveria "m será um número inteiro no intervalo [0, 1, ..., n]" será "... [0, 1, ..., n-1]"?

Jonathan Allan

@feersum Sua solução pode oferecer suporte a qualquer, mse desejado, mas eu exijo que seja válida para 0 <= m <= n com 0 <= n .

miles

9

Gelatina , 8 bytes

Œ!Z>2\Sċ

Experimente online!(demora um pouco) ou verifique os casos de teste menores .

Como 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
fonte

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

Com base na fórmula recursiva:

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

Casos de teste

Mostrar snippet 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 snippet

Arnauld
fonte

4

MATL , 10 bytes

:Y@!d0>s=s

Experimente online!

Explicação

Considere como um exemplo entradas n=3,m=1 . Você pode colocar um %símbolo para comentar o código a partir desse ponto e ver os resultados intermediários. Por exemplo, o link mostra a pilha após a primeira etapa.

:      % 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
fonte

4

CJam ( 21 19 bytes - ou 18 se a ordem dos argumentos estiver livre)

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

Este é um bloco anônimo (função) que assume n ma pilha. (Se é permitido assumir m na pilha, \pode ser salvo). Ele calcula todas as permutações e filtros, para que o conjunto de testes on - line deve ser bastante limitado.

Obrigado a Martin por apontar uma aproximação para filter-with-parameter.

Dissecação

{        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
}

Observe que os números eulerianos são simétricos:, E(n, m) = E(n, n-m)portanto, é irrelevante se você conta quedas ou aumentos.

Eficientemente: 32 bytes

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

Conjunto de testes online .

Isso implementa a recorrência em linhas inteiras.

{          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
fonte

É mais curto para evitar a variável usando um mapa: {e!f{2ew::>1b=}1e=}. Ou apenas por diversão:{e!f{2ew::>+:-}0e=}

Martin Ender

Isso foi estúpido, é claro. A 1e=primeira solução pode ser 1b.

Martin Ender

Você pode usar sua própria ordem de argumento

milhas

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

Todos os testes em repl.it

Aplica a fórmula recursiva no OEIS.
Observe que você +(m+1)*a(n-1,m)joga golfe -~m*a(n-1,m).
(Pode retornar valores booleanos para representar 1ou 0. Retorna Truequando n<0 and m<=0ou m<0.)

Jonathan Allan
fonte

Existem várias outras maneiras de lidar com os casos extremos. Basta lidar m<1 ? 1 : m==n ? 0 : formula, de forma equivalente m%n<1 ? (m<1) : formula; ou alternativamente m<1 ? (n>=0) : formula.

Peter Taylor

Eu tenho isso, apenas atualizando graças

Jonathan Allan

Como nossas respostas são muito semelhantes e as suas foram postadas primeiro (e são mais curtas), vou excluir as minhas.

Loovjo 19/10/16

@Loovjo Um pouco de ajustes frenética embora :( Você tem um ^ voto de mim de qualquer maneira!

Jonathan Allan

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

E aqui está uma versão de 59 bytes que implementa a definição mais literalmente:

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

Martin Ender
fonte

Por que não apenas f[n_,m_]:=...para 49 anos?

Jonathan Allan

@ JonathanAllan Não sei se entendi. Como isso lida com o caso base?

Martin Ender

OK, algo foi armazenado em cache - apenas o fiz em uma nova planilha e falhou com o limite de recursão. :)

Jonathan Allan

Há também é a fórmula que utiliza 46 bytes Sum[Binomial[#+1,k](#2+1-k)^#(-1)^k,{k,0,#2}]&que pode ser possível de golfe mais

milhas

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

Recursão do OEIS. Saídas booleanas Truecomo 1quando n==k.

xnor
fonte

2

MATLAB / oitava, 40 bytes

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

Esta é uma porta da minha resposta MATL, na forma de uma função anônima. Chame como ans(7,4).

Experimente em Ideone .

Luis Mendo
fonte

2

Idioma do GameMaker, 62 bytes

Este é um script recursivo Abaseado na fórmula de @ Arnauld.

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

Timtech
fonte

Não vejo isso há algum tempo!

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

Baseado na mesma propriedade que a resposta de Arnauld.

Gabriel Benamy
fonte

1

R, 72 bytes

Função recursiva seguindo a lógica no 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)

Esse desafio acabou sendo bem próximo entre as diferentes abordagens que tentei. Por exemplo, o uso da fórmula da Wikipedia e o loop sobre a soma resultaram em 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)}

ou a versão vetorizada 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))

e finalmente a solução de força bruta (103 bytes) que gera uma matriz de todas as permutações usando o permutepacote e a função allPerms. Essa abordagem funciona apenas no n<8entanto.

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

Billywob
fonte

1

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

Ungolfed:

(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

Teste:

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

Resultado:

rnso
fonte

1

Na verdade , 21 19 bytes

Essa resposta usa um algoritmo semelhante ao utilizado por Dennis em sua resposta Jelly . A definição original conta <enquanto conto >. Isso acaba sendo equivalente no final. Sugestões de golfe são bem-vindas. Experimente online!

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

Ungolfing

         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
fonte

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}

A mesma fórmula recursiva em um idioma que definitivamente não é para o golfe

Apollonian
fonte

0

J, 28 bytes

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

Usa a 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

Explicação

+/@((!>:)~*(^~#\.)*_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

milhas
fonte

Calcular o número euleriano

Regras

Casos de teste

Respostas:

Gelatina , 8 bytes

Como funciona

JavaScript (ES6), 50 46 45 bytes

Casos de teste

MATL , 10 bytes

Explicação

CJam ( 21 19 bytes - ou 18 se a ordem dos argumentos estiver livre)

Dissecação

Eficientemente: 32 bytes

Python, 55 56 bytes

Mathematica, 59 56 bytes

Python, 53 bytes

MATLAB / oitava, 40 bytes

Idioma do GameMaker, 62 bytes

Perl, 98 bytes

R, 72 bytes

Raquete 141 bytes

Na verdade , 21 19 bytes

Swift 3 , 8288 Bytes

J, 28 bytes

Uso

Explicação