17

Le nombre eulérien A(n, m) est le nombre de permutations [1, 2, ..., n]dont exactement les méléments sont supérieurs à l'élément précédent. Celles-ci sont également appelées hausses . Par exemple, si n = 3, il y en a 3! = 6 permutations 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 ...

Ainsi, les sorties pour A(3, m)pour mdans [0, 1, 2, 3]seront

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

Il s'agit également de la séquence OEIS A173018 .

Règles

C'est le code-golf donc le code le plus court l'emporte.
L'entrée nsera un entier non négatif et msera un entier dans la plage [0, 1, ..., n].

Cas de test

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 miles
la source

Des limites n, m?

Loovjo

Il n'y a pas de limite, mais il n'est pas nécessaire que votre soumission soit en mesure d'exécuter complètement un scénario de test dans un certain laps de temps, uniquement avec la logique correcte. De préférence, j'aimerais que les soumissions traitent des valeurs jusqu'à 20, mais je l'ai laissé sans exigence de performances pour autoriser des solutions de force brute qui ne peuvent fonctionner que jusqu'à n = 10.

miles

L'entrée peut-elle avoir m> = n, n> 0?

feersum

Ne devrait pas, "m sera un entier dans la plage [0, 1, ..., n]" être "... [0, 1, ..., n-1]"?

Jonathan Allan

@feersum Votre solution peut en prendre en charge msi vous le souhaitez, mais je demande seulement qu'elle soit valide pour 0 <= m <= n avec 0 <= n .

miles

9

Gelée , 8 octets

Œ!Z>2\Sċ

Essayez-le en ligne! (prend un certain temps) ou vérifiez les cas de test plus petits .

Comment ça fonctionne

Œ!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
la source

6

JavaScript (ES6), 50 46 45 octets

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

Basé sur la formule récursive:

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

Cas de test

Afficher l'extrait de code

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

Développer l'extrait

Arnauld
la source

4

MATL , 10 octets

:Y@!d0>s=s

Essayez-le en ligne!

Explication

Prenons comme exemple les entrées n=3,m=1 . Vous pouvez placer un %symbole pour commenter le code à partir de ce point et voir ainsi les résultats intermédiaires. Par exemple, le lien affiche la pile après la première étape.

:      % 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
la source

4

CJam ( 21 19 octets - ou 18 si l'ordre des arguments est libre)

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

Il s'agit d'un bloc (fonction) anonyme qui prend n mla pile. (S'il est permis de prendre m nla pile, alors le \peut être enregistré). Il calcule toutes les permutations et tous les filtres, donc la suite de tests en ligne doit être plutôt limitée.

Merci à Martin d'avoir signalé une approximation de filter-with-parameter.

Dissection

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

Notez que les nombres eulériens sont symétriques E(n, m) = E(n, n-m):, il est donc sans importance que vous comptiez les chutes ou les hausses.

Efficacement: 32 octets

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

Suite de tests en ligne .

Cela implémente la récurrence sur des lignes entières.

{          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
la source

Il est plus court pour éviter la variable en utilisant une carte: {e!f{2ew::>1b=}1e=}. Ou juste pour le plaisir:{e!f{2ew::>+:-}0e=}

Martin Ender

C'était stupide, bien sûr. La 1e=première solution peut être 1b.

Martin Ender

Vous êtes autorisé à utiliser votre propre ordre d'argument

miles

3

Python, 55 56 octets

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

Tous les tests sur repl.it

Applique la formule récursive sur OEIS.
Notez que +(m+1)*a(n-1,m)c'est joué au golf -~m*a(n-1,m).
(Peut renvoyer des valeurs booléennes pour représenter 1ou 0. Renvoie Truequand n<0 and m<=0ou m<0.)

Jonathan Allan
la source

Il existe plusieurs autres façons de gérer les cas de bord. Il suffit de le manipuler m<1 ? 1 : m==n ? 0 : formula, de manière équivalente m%n<1 ? (m<1) : formula; ou alternativement m<1 ? (n>=0) : formula.

Peter Taylor

Je l'ai, juste une mise à jour merci

Jonathan Allan

Comme nos réponses sont très similaires et que la vôtre a été publiée en premier (et est plus courte), je vais supprimer la mienne.

Loovjo

@Loovjo Un peu de peaufinage frénétique cependant :( Vous avez quand même obtenu un ^ vote de ma part!

Jonathan Allan

3

Mathematica, 59 56 octets

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

Et voici une version de 59 octets implémentant la définition plus littéralement:

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

Martin Ender
la source

Pourquoi pas seulement f[n_,m_]:=...pour 49?

Jonathan Allan

@JonathanAllan Je ne suis pas sûr de comprendre. Comment cela gère-t-il le cas de base?

Martin Ender

OK, quelque chose a été mis en cache - vient de le faire dans une nouvelle feuille de calcul et il a échoué avec une limite de récursivité. :)

Jonathan Allan

Il y a aussi la formule qui utilise 46 octets Sum[Binomial[#+1,k](#2+1-k)^#(-1)^k,{k,0,#2}]&qui pourraient être possibles pour jouer au golf plus

miles

3

Python, 53 octets

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

Récursivité depuis OEIS. Sorties booléennes Truecomme 1quand n==k.

xnor
la source

2

MATLAB / Octave, 40 octets

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

Il s'agit d'un portage de ma réponse MATL, sous la forme d'une fonction anonyme. Appelez-le comme ans(7,4).

Essayez-le chez Ideone .

Luis Mendo
la source

2

GameMaker Language, 62 octets

Il s'agit d'un script récursif Abasé sur la formule de @ Arnauld.

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

Timtech
la source

Je n'ai pas vu ça depuis un moment!

tomsmeding

1

Perl, 98 octets

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

Basé sur la même propriété que la réponse d'Arnauld.

Gabriel Benamy
la source

1

R, 72 octets

Fonction récursive suivant la logique sur 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)

Ce défi s'est avéré assez proche entre les différentes approches que j'ai essayées. Par exemple, l'utilisation de la formule wikipedia et le bouclage sur la somme ont donné 92 octets:

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 la version vectorisée pour 87 octets:

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

et enfin la solution de force brute (103 octets) qui génère une matrice de toutes les permutations en utilisant le permutepackage et la fonction allPerms. Cette approche ne fonctionne cependant n<8que.

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

Billywob
la source

1

Raquette 141 octets

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

Non 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

Essai:

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

Production:

rnso
la source

1

En fait , 21 19 octets

Cette réponse utilise un algorithme similaire à celui utilisé par Dennis dans sa réponse Jelly . La définition originale compte <pendant que je compte >. Cela finit par être équivalent au final. Suggestions de golf bienvenues. Essayez-le en ligne!

;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
la source

1

Swift 3 , 8288 Octets

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}

Juste la même formule récursive dans une langue qui n'est certainement pas pour le golf

Apollonian
la source

0

J, 28 octets

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

Utilise la formule

formule

Usage

   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

Explication

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

miles
la source

Calculer le nombre eulérien

Règles

Cas de test

Réponses:

Gelée , 8 octets

Comment ça fonctionne

JavaScript (ES6), 50 46 45 octets

Cas de test

MATL , 10 octets

Explication

CJam ( 21 19 octets - ou 18 si l'ordre des arguments est libre)

Dissection

Efficacement: 32 octets

Python, 55 56 octets

Mathematica, 59 56 octets

Python, 53 octets

MATLAB / Octave, 40 octets

GameMaker Language, 62 octets

Perl, 98 octets

R, 72 octets

Raquette 141 octets

En fait , 21 19 octets

Swift 3 , 8288 Octets

J, 28 octets

Usage

Explication