17

Эйлерово число A(n, m) есть число перестановок , [1, 2, ..., n]в которых ровно mэлементах больше , чем предыдущий элемент. Они также называются подъемами . Например, если n = 3есть 3! = 6 перестановок[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 ...

Таким образом, выходы A(3, m)для mв [0, 1, 2, 3]будут

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

Также это последовательность OEIS A173018 .

правила

Это код-гольф, поэтому выигрывает самый короткий код.
Входные данные nбудут неотрицательным целым числом и mбудут целым числом в диапазоне [0, 1, ..., n].

Тестовые случаи

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 миль
источник

Есть ли ограничения на n, m?

Loovjo

Ограничений нет, но не обязательно, чтобы ваше представление могло полностью выполнить тестовый набор за определенное время, только иметь правильную логику. Желательно, чтобы заявки обрабатывали значения до 20, но я оставил их без требования к производительности, чтобы разрешить грубые решения, которые могут работать только до n = 10.

миль

Может ли вход иметь m> = n, n> 0?

feersum

Не должно ли "m будет целым числом в диапазоне [0, 1, ..., n]" быть "... [0, 1, ..., n-1]"?

Джонатан Аллан

@feersum Ваше решение может поддерживать любое, mесли это необходимо, но я требую, чтобы оно действовало только для 0 <= m <= n с 0 <= n .

миль

9

Желе , 8 байт

Œ!Z>2\Sċ

Попробуйте онлайн! (занимает некоторое время) или проверьте меньшие контрольные примеры .

Как это устроено

Œ!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 байт

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

На основе рекурсивной формулы:

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

Контрольные примеры

Показать фрагмент кода

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

Развернуть фрагмент

Arnauld
источник

4

MATL , 10 байт

:Y@!d0>s=s

Попробуйте онлайн!

объяснение

Рассмотрим в качестве примера входов n=3,m=1 . Вы можете поместить %символ, чтобы закомментировать код с этого момента и, таким образом, увидеть промежуточные результаты. Например, ссылка показывает стек после первого шага.

:      % 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 байт - или 18, если порядок аргументов свободен)

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

Это анонимный блок (функция), который принимает n mстек. (Если разрешено брать m nв стек, то \можно сохранить). Он вычисляет все перестановки и фильтры, поэтому набор онлайн-тестов должен быть довольно ограниченным.

Спасибо Мартину за указание на приближение к filter-with-parameter.

рассечение

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

Обратите внимание, что эйлеровы числа симметричны: E(n, m) = E(n, n-m)поэтому не имеет значения, уменьшается ли число или увеличивается.

Эффективно: 32 байта

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

Набор онлайн-тестов .

Это реализует повторение на целых строках.

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

Питер Тейлор
источник

Это короче , чтобы избежать переменной с помощью карты: {e!f{2ew::>1b=}1e=}. Или просто для удовольствия:{e!f{2ew::>+:-}0e=}

Мартин Эндер

Это было глупо, конечно. В 1e=первом решении может быть 1b.

Мартин Эндер

Вам разрешено использовать свой собственный порядок аргументов

мили

3

Python, 55 56 байт

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

Все тесты на repl.it

Применяет рекурсивную формулу к OEIS.
Обратите внимание, что +(m+1)*a(n-1,m)это гольф -~m*a(n-1,m).
(Может возвращать логические значения для представления 1или 0. Возвращается, Trueкогда n<0 and m<=0или m<0.)

Джонатан Аллан
источник

Существуют различные другие способы обработки крайних случаев. Достаточно обращаться с ним m<1 ? 1 : m==n ? 0 : formulaэквивалентно m%n<1 ? (m<1) : formula; или альтернативно m<1 ? (n>=0) : formula.

Питер Тейлор

Я получил это, просто обновляя спасибо

Джонатан Аллан

Поскольку наши ответы очень похожи, а ваш был опубликован первым (и короче), я удалю свои.

Loovjo

@Loovjo Немного безумной настройки, хотя :( В любом случае, вы получили ^ голос от меня!

Джонатан Аллан

3

Mathematica, 59 56 байт

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

И вот 59-байтовая версия, реализующая это определение более буквально:

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

Мартин Эндер
источник

Почему не только f[n_,m_]:=...за 49?

Джонатан Аллан

@JonathanAllan Я не уверен, что понимаю. Как это обрабатывает базовый случай?

Мартин Эндер

Хорошо, что-то было кэшировано - просто сделал это на новом листе, и это не удалось с пределом рекурсии. :)

Джонатан Аллан

Существует также формула, которая использует 46 байтов, Sum[Binomial[#+1,k](#2+1-k)^#(-1)^k,{k,0,#2}]&которые могут быть возможны для игры в гольф

мили

3

Python, 53 байта

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

Рекурсия из OEIS. Выходы логические Trueкак и 1когда n==k.

XNOR
источник

2

MATLAB / Octave, 40 байт

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

Это порт моего ответа MATL в форме анонимной функции. Назовите это как ans(7,4).

Попробуйте это в Ideone .

Луис Мендо
источник

2

Язык GameMaker, 62 байта

Это рекурсивный скрипт, Aоснованный на формуле @ Арно.

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

Timtech
источник

Этого давно не видел!

Томсминг

1

Perl, 98 байт

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

На основании того же свойства, что и ответ Арно.

Габриэль Бенами
источник

1

R, 72 байта

Рекурсивная функция, следующая за логикой в 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)

Эта проблема оказалась довольно близкой между различными подходами, которые я пробовал. Например, при использовании формулы Википедии и циклическом пересчете суммы получается 92 байта:

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

или векторизованная версия для 87 байтов:

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

и, наконец, решение методом грубой силы (103 байта), которое генерирует матрицу всех перестановок с использованием permuteпакета и функции allPerms. Этот подход работает только до тех 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)}

Billywob
источник

1

Ракетка 141 байт

(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

Тестирование:

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

Выход:

rnso
источник

1

На самом деле , 21 19 байтов

Этот ответ использует алгоритм, аналогичный тому, который Деннис использует в своем ответе на желе . Исходное определение имеет значение, <пока я считаю >. Это в конечном итоге эквивалентно. Предложения по игре в гольф приветствуются. Попробуйте онлайн!

;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
источник

1

Свифт 3 , 8288 Б

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}

Точно такая же рекурсивная формула на языке, который определенно не для гольфа

посвященный Аполлону
источник

0

J, 28 байт

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

Использует формулу

формула

использование

   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

объяснение

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

миль
источник

Вычислить эйлерово число

правила

Тестовые случаи

Ответы:

Желе , 8 байт

Как это устроено

JavaScript (ES6), 50 46 45 байт

Контрольные примеры

MATL , 10 байт

объяснение

CJam ( 21 19 байт - или 18, если порядок аргументов свободен)

рассечение

Эффективно: 32 байта

Python, 55 56 байт

Mathematica, 59 56 байт

Python, 53 байта

MATLAB / Octave, 40 байт

Язык GameMaker, 62 байта

Perl, 98 байт

R, 72 байта

Ракетка 141 байт

На самом деле , 21 19 байтов

Свифт 3 , 8288 Б

J, 28 байт

использование

объяснение