Oblicz liczbę Eulera


17

Liczba Eulera A(n, m) jest liczbą permutacji, [1, 2, ..., n]w których dokładnie melementy są większe niż poprzedni element. Są to również zwane wzrostami . Na przykład, jeśli n = 3są 3! = 6 permutacji z[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 ...

Tak wyjść na A(3, m)na mw [0, 1, 2, 3]będzie

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

Jest to również sekwencja OEIS A173018 .

Zasady

  • To jest więc wygrywa najkrótszy kod.
  • Wejście nbędzie nieujemną liczbą całkowitą i mbędzie liczbą całkowitą z zakresu [0, 1, ..., n].

Przypadki testowe

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

Jakieś ograniczenia n, m?
Loovjo,

Nie ma limitu, ale nie jest wymagane, aby zgłoszenie było w stanie całkowicie wykonać przypadek testowy w określonym czasie, mieć tylko prawidłową logikę. Najlepiej, gdybym chciał, aby zgłoszenia obsługiwały wartości do 20, ale pozostawiłem to bez wymogu wydajności, aby umożliwić rozwiązania brutalnej siły, które mogą działać tylko do n = 10.
mil

Czy dane wejściowe mogą mieć m> = n, n> 0?
feersum

Czy „m będzie liczbą całkowitą z zakresu [0, 1, ..., n]„ być ”... [0, 1, ..., n-1]?
Jonathan Allan,

@feersum Twoje rozwiązanie może obsługiwać dowolne w mrazie potrzeby, ale wymagam tylko, aby było ważne dla 0 <= m <= n z 0 <= n .
mil

Odpowiedzi:


9

Galaretka , 8 bajtów

Œ!Z>2\Sċ

Wypróbuj online! (zajmuje to chwilę) lub sprawdź mniejsze przypadki testowe .

Jak to działa

Œ!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.

6

JavaScript (ES6), 50 46 45 bajtów

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

Na podstawie rekurencyjnej formuły:

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

Przypadki testowe


4

MATL , 10 bajtów

:Y@!d0>s=s

Wypróbuj online!

Wyjaśnienie

Rozważmy jako przykład wejść n=3,m=1 . Możesz umieścić %symbol, aby skomentować kod od tego momentu i zobaczyć wyniki pośrednie. Na przykład link pokazuje stos po pierwszym kroku.

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

4

CJam ( 21 19 bajtów - lub 18, jeśli porządek argumentów jest bezpłatny)

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

Jest to anonimowy blok (funkcja), który przyjmuje n mstos. (Jeśli dozwolone jest wzięcie m nstosu, \można go zapisać). Oblicza wszystkie permutacje i filtry, więc zestaw testów online musi być raczej ograniczony.

Podziękowania dla Martina za wskazanie przybliżenia do filter-with-parameter.

Sekcja

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

Zauważ, że liczby Eulera są symetryczne: E(n, m) = E(n, n-m)więc nie ma znaczenia, czy liczysz upadki, czy wzrosty.

Wydajnie: 32 bajty

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

Zestaw testów online .

To implementuje powtarzalność w całych rzędach.

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

To krócej, aby uniknąć zmienną za pomocą mapy: {e!f{2ew::>1b=}1e=}. Lub dla zabawy:{e!f{2ew::>+:-}0e=}
Martin Ender

To oczywiście było głupie. 1e=W pierwszym roztworze może być 1b.
Martin Ender,

Możesz używać własnego porządku argumentów
mil

3

Python, 55 56 bajtów

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

Wszystkie testy w repl.it

Stosuje formułę rekurencyjną w OEIS.
Zauważ, że +(m+1)*a(n-1,m)gra w golfa -~m*a(n-1,m).
(Może zwracać wartości boolowskie do reprezentowania 1lub 0. Zwraca Truekiedy n<0 and m<=0lub m<0.)


Istnieją różne inne sposoby obsługi skrzynek krawędziowych. Wystarczy poradzić sobie m<1 ? 1 : m==n ? 0 : formularównorzędnie m%n<1 ? (m<1) : formula; lub alternatywnie m<1 ? (n>=0) : formula.
Peter Taylor

Mam, właśnie dziękuję za aktualizację
Jonathan Allan

Ponieważ nasze odpowiedzi są bardzo podobne, a twoje zostało opublikowane jako pierwsze (i jest krótsze), pójdę dalej i usunę moje.
Loovjo,

@Loovjo Trochę szalonych poprawek :( I tak masz ode mnie ^ głos!
Jonathan Allan

3

Mathematica, 59 56 bajtów

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

A oto 59-bajtowa wersja implementująca definicję bardziej dosłownie:

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

Dlaczego nie tylko f[n_,m_]:=...za 49?
Jonathan Allan,

@JonathanAllan Nie jestem pewien, czy rozumiem. Jak to obsługuje skrzynkę podstawową?
Martin Ender,

OK, coś zostało zapisane w pamięci podręcznej - właśnie zrobiłem to w nowym arkuszu i nie powiodło się z limitem rekurencji. :)
Jonathan Allan

Istnieje również formuła, która wykorzystuje 46 bajtów Sum[Binomial[#+1,k](#2+1-k)^#(-1)^k,{k,0,#2}]&, które mogą być możliwe do golfa więcej
mile

3

Python, 53 bajty

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

Rekursja z OEIS. Zwraca wartość logiczną Truejak w 1momencie n==k.


2

MATLAB / oktawa, 40 bajtów

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

Jest to część mojej odpowiedzi MATL w postaci anonimowej funkcji. Nazwij to jak ans(7,4).

Wypróbuj w Ideone .


2

GameMaker Language, 62 bajty

To jest skrypt rekurencyjny Aoparty na formule @ Arnauld.

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

Dawno tego nie widziałem!
tomsmeding

1

Perl, 98 bajtów

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

Na podstawie tej samej właściwości, co odpowiedź Arnaulda.


1

R, 72 bajty

Funkcja rekurencyjna zgodnie z logiką 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)

To wyzwanie okazało się dość bliskie między różnymi podejściami, które wypróbowałem. Na przykład użycie formuły wikipedia i zapętlenie sumy dało 92 bajty:

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

lub wektoryzowana wersja dla 87 bajtów:

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

i wreszcie rozwiązanie brutalnej siły (103 bajty), które generuje macierz wszystkich permutacji przy użyciu permutepakietu i funkcji allPerms. Takie podejście działa jednak tylko do n<8.

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

1

Rakieta 141 bajtów

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

Nie golfowany:

(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

Testowanie:

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

Wynik:

1
4
1
0
11
26
1191

1

faktycznie , 21 19 bajtów

Ta odpowiedź wykorzystuje algorytm podobny do tego, który Dennis stosuje w swojej odpowiedzi na żelki . Oryginalna definicja się liczy, <a ja liczę >. To ostatecznie jest równoważne. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj 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.


0

J, 28 bajtów

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

Korzysta ze wzoru

formuła

Stosowanie

   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

Wyjaśnienie

+/@((!>:)~*(^~#\.)*_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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.