Вычислить коэффициент многочлена

27

Время для еще одной простой задачи, в которой могут участвовать все!

Полиномиальная теорема гласит: Формула для вычисления n-й степени многочлена

Выражение в скобках - это множитель, определяемый как:

Полиномиальный коэффициент

Разрешение членам k i охватывать все целочисленные разбиения n дает n-й уровень m -симплекса Паскаля . Ваша задача - вычислить этот коэффициент.

задача

Напишите программу или функцию, которая принимает m чисел, n , k 1 , k 2 , ..., k m-1 и выводит или возвращает соответствующий коэффициент многочлена. Ваша программа может дополнительно принять m в качестве дополнительного аргумента, если это необходимо. Обратите внимание, что k m не на входе.

  • Эти числа могут быть введены в любом понравившемся формате, например, сгруппированы в списки или закодированы в унарном виде, или как угодно, если фактическое вычисление коэффициента многочлена выполняется вашим кодом, а не процессом кодирования.

  • Формат вывода также гибкий.

  • Весь код должен выполняться менее чем за одну минуту для n и m до 1000.

  • Не беспокойтесь о целочисленном переполнении.

  • Встроенные модули, предназначенные для вычисления коэффициента многочлена, не допускаются.

  • Применяются стандартные лазейки.

счет

Это код гольф: выигрывает самое короткое решение в байтах.

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

Input: 3, [2, 0]
Output: 3

Input: 3, [1, 1]
Output: 6

Input: 11, [1, 4, 4]
Output: 34650

Input: 4, [1,2]
Output: 12

Input: 15, [5,4,3,2]
Output: 37837800

Input: 95, [65,4,4]
Output: 1934550571913396675776550070308250

Input: 32, [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
Output: 4015057936610313875842560000000

Input: 15, [3,3,3,3]
Output: 168168000

Input: 1000, [10,10,10,10,10,10,10,10,10,10,100,100,100,100,100,100,100,100]
Output: 1892260836114766064839886173072628322819837473493540916521650371620708316292211493005889278395285403318471457333959691477413845818795311980925098433545057962732816261282589926581281484274178579110373517415585990780259179555579119249444675675971136703240347768185200859583936041679096016595989605569764359198616300820217344233610087468418992008471158382363562679752612394898708988062100932765563185864346460326847538659268068471585720069159997090290904151003744735224635733011050421493330583941651019570222984959183118891461330718594645532241449810403071583062752945668937388999711726969103987467123014208575736645381474142475995771446030088717454857668814925642941036383273459178373839445456712918381796599882439216894107889251444932486362309407245949950539480089149687317762667940531452670088934094510294534762190299611806466111882595667632800995865129329156425174586491525505695534290243513946995156554997365435062121633281021210807821617604582625046557789259061566742237246102255343862644466345335421894369143319723958653232683916869615649006682399919540931573841920000000000000

Input: 33, [17]
Output: 1166803110

Input: 55, [28]
Output: 3824345300380220
quintopia
источник
Можем ли мы иметь ошибки неточности? Т.е. вместо того 1934550571913396675776550070308250, можем ли мы выводить 1.9345505719133966e+33?
Конор О'Брайен
@ CᴏɴᴏʀO'Bʀɪᴇɴ Если вы использовали 64-битные числа с плавающей запятой, вы вообще не сможете представлять входные данные [1000 {999 ones}], потому что показатель степени намного превышает то, что может представлять 64-битные числа с плавающей запятой. (Возможно, будет достаточно 128-разрядных чисел с плавающей запятой, но я предполагаю, что вы хотите использовать собственный тип чисел в JavaScript?)
Мартин Эндер
@ MartinBüttner Да, это правильное предположение.
Конор О'Брайен
2
@quintopia «Время для еще одного легкого испытания, в котором все могут участвовать!». Все, кроме меня! (Поскольку я понятия не имею, что такое Паскальский симплекс и многочлены D :) LOL.
Эшвин Гупта
@AshwinGupta Не беспокойся об этом. Вы просто вычисляете выражение на втором изображении, и все готово! Qu
квинтопия

Ответы:

21

Желе , 7 6 байт

;_/!:/

Смотри, ма, нет Юникода! Эта программа принимает в качестве входных данных один список с n в первом индексе.

Попробуйте онлайн! или проверьте все тестовые случаи одновременно .

Как это работает

;_/!:/ Input: A (list)

 _/    Reduce A by subtraction. This subtracts all other elements from the first.
;      Concatenate A with the result to the right.
   !   Apply factorial to all numbers in the resulting list.
    :/ Reduce the result by division. This divides the first element by the others.
Деннис
источник
Это алгоритм, который я имел в виду как самый простой.
Quintopia
9

CJam, 11 байт

l~_:-+:m!:/

Ввод в виде единого списка с nпервым:

[95 65 4 4]

Это ручки входы до nи m1000 довольно много мгновенно.

Проверьте это здесь.

объяснение

l~  e# Read a line of input and evaluate it.
_   e# Duplicate.
:-  e# Fold subtraction over the list. A fold is essentially a foreach loop that starts
    e# from the second element. Hence, this subtracts all the k_i from n, giving k_m.
+   e# Append k_m to the list.
:m! e# Compute the factorial of each element in the list.
:/  e# Fold division over the list. Again, this divides n! by each of the k_i!.
Мартин Эндер
источник
Похоже, вы действительно проиграете соревнование по подсчету байтов, но я должен сказать, что впечатлен безумной краткостью CJam.
phord
@phord Ну CJam не подходит для Jelly (или Pyth в этом отношении). Но я сам был очень удивлен, насколько компактным он оказался. Мое первое решение имело 21 байт, и, хотя оно не казалось оптимальным, я не думал, что смогу сократить его вдвое.
Мартин Эндер
4

MATL , 21 15 байт

Давайте использовать функцию log-gamma . Это позволяет избежать внутреннего переполнения, работая с логарифмами факториалов, а не с самими факториалами.

1+ZgiO$Gs-h1+Zgs-ZeYo

Это работает в текущей версии (9.2.2) языка / компилятора, которая является более ранней, чем эта проблема.

Входные данные: сначала число, затем числовой вектор. Результат создается как a double, который ограничивает максимальную производительность где-то рядом 2^52.

пример

>> matl 1+ZgiO$Gs-h1+Zgs-ZeYo
> 15
> [5 4 3 2]
37837800

объяснение

1+       % implicit input (number). Add 1
Zg       % log-gamma function
i        % input (numeric vector).
0$G      % push both inputs
s-       % sum the second input (vector) and subtract from first
h1+      % append to vector. Add 1
Zg       % log-gamma function, element-wise on extended vector
s        % sum of results
-        % subtract from previous result of log-gamma
Ze       % exponential
Yo       % round. Implicit display
Луис Мендо
источник
4
Попробуйте онлайн! теперь есть экспериментальная поддержка MATL : matl.tryitonline.net/… Предложения приветствуются.
Деннис
1
@ Денис Эй! Какой сюрприз!!! Как я могу отблагодарить вас? У меня есть предложение: если вы когда-нибудь приедете в Мадрид, я должен вам хороший ужин и напитки
Луис Мендо
Я очень благодарен. Здорово иметь это онлайн. Как мы будем обрабатывать изменения? Я все еще постоянно обновляю язык, вы знаете ...
Луис Мендо
Сейчас я вручную обновляю переводчиков. Если вы сделаете обновление, просто пингуйте меня в «Девятнадцатом байте», и я вытащу его как можно скорее. - Мне придется поехать в Мадрид в ближайшее время, поэтому я буду помнить ваше предложение. ;)
Денис
@ Денис Отлично! Таким образом, мы можем встретиться лично!
Луис Мендо
4

PowerShell, 91 74 байта

Woo! Мой сотый ответ на PPCG!

param($n,$k)(1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)

Уф. Не собираюсь выигрывать кратчайший код, это точно. Тем не менее, использует несколько хитрых трюков с диапазонами. И это, вероятно, полный бред для всех, кто не знаком с PowerShell.

объяснение

Сначала мы берем ввод с param($n,$k)и ожидаем, $kчто он будет массивом, например .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Начнем с числителя (все слева от /). Это просто диапазон 1..$n, который был -joinотредактирован вместе с *и затем оценен iexдля вычисления факториала (то есть 1*2*3*...*$n).

Затем мы зацикливаемся $k|%{...}и на каждой итерации вычитаем текущее значение ( $_из $nкоторого мы больше не заботимся), чтобы сформулировать его $k_mпозже. Кроме того, мы генерируем диапазон 1..$k_iкаждой итерации, который остается на конвейере. Эти объекты конвейера объединяются в массив со вторым выражением, range 1..$n(который находится $k_mв этой точке). Все это, в конечном итоге, обрабатывается -joinвместе с *оценкой iex, аналогично числителю (это работает потому x! * y! = 1*2*3*...*x * 1*2*3*...*y, что нас не интересует индивидуальный порядок).

Наконец, /случается, числитель делится на знаменатель и выводится.

Правильно обрабатывает выходные данные для больших чисел, поскольку мы не приводим явным образом какие-либо переменные как какие-либо конкретные типы данных, поэтому PowerShell будет автоматически преобразовывать типы данных на лету по мере необходимости. Для больших чисел выходные данные через научную запись лучше сохраняют значимые цифры при повторном приведении типов данных. Например, .\compute-the-multinomial-coefficient.ps1 55 @(28)будет выводить 3.82434530038022E+15. Я предполагаю, что все будет в порядке, учитывая, что «формат вывода такой же гибкий» задан в вызове и в комментариях квинтопии «Если конечный результат может вписаться в искомо поддерживаемые целочисленные типы, то результат должен быть точным. нет никаких ограничений на то, что может быть выведено ".


альтернативно

В зависимости от решения о форматировании вывода, следующие в 92 байта

param($n,$k)((1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)).ToString('G17')

Что же , как и выше, просто использует явный вывод форматирования с .ToString('G17')для достижения требуемого количества цифр. Для 55 @(28)этого будет выходной3824345300380220.5


Edit1 - Сэкономил 17 байт, избавившись от него $dи просто вычислив его напрямую, а также избавившись от вычисления $k_m, связав его во время цикла $k
Edit2 - Добавлена ​​альтернативная версия с явным форматированием

AdmBorkBork
источник
3

APL (Dyalog Extended) , 9 байт

×/2!/+\⍛,

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

Используя идею из моего APL ответа на еще одну проблему, которая включает в себя многочлены .

Неявная функция, левый аргумент которой является списком k, а правый аргумент - n. Тестовые случаи проверяют, соответствует ли это решению Адама, когда левый и правый аргументы перевернуты.

Как это работает

×/2!/+\⍛,
     +\     Cumulative sum of k's (up to m-1'th element)
       ⍛,   Append n (sum of k_1 to k_m)
  2!/       Binomial of consecutive pairs
×/          Product

(k1+k2++km)!k1!k2!km!=(k1+k2)!k1!k2!×(k1+k2++km)!(k1+k2)!k3!km!

=(k1+k2)!k1!k2!×(k1+k2+k3)!(k1+k2)!k3!×(k1+k2++km)!(k1+k2+k3)!km!

==(k1+k2k1)(k1+k2+k3k1+k2)(k1++kmk1++km1)

фонтанчик для питья
источник
2

Mathematica, 26 байтов

#!/Times@@({#-+##2,##2}!)&

Пример:

In[1]:= #!/Times@@({#-+##2,##2}!)&[95,65,4,4]

Out[1]= 1934550571913396675776550070308250
alephalpha
источник
2

Питон 3, 93 91

Спасибо Деннису и FryAmTheEggman .

f=lambda x:0**x or x*f(x-1)
def g(n,k):
    r=f(n)
    for i in k:r//=f(i)
    return r//f(n-sum(k))

nкак целое число, kкак итеративный.

Ungolfed:

import functools #cache

@functools.lru_cache(maxsize=None) #cache results to speed up calculations
def factorial(x):
    if x <= 1: return 1
    else: return x * factorial(x-1)

def multinomial(n, k):
    ret = factorial(n)
    for i in k: ret //= factorial(i)
    km = n - sum(k)
    return ret//factorial(km)
Транг Оул
источник
1
Вы можете использовать один пробел вместо четырех для динамического пробела
Conor O'Brien
Я использовал вкладки, они были заменены в этом посте. Счетчик байтов в порядке. Я не уверен насчет результата с плавающей точкой и возможного переполнения.
Транг Оул
2
1. Это приводит к неправильному 95, [65, 4, 4]. Обратите внимание, что вход не содержит k_m . 2. Вы, кажется, не используете from functools import*вообще.
Деннис
2
1. Ваш гольф-код не используется reduce. 2. import math;f=math.factorialсохраняет байт. 3. Python 2 позволит вам избавиться от второго /входа //.
Деннис
1
Определение fсамостоятельно сохраняет несколько байт : f=lambda x:0**x or x*f(x-1).
FryAmTheEggman
2

APL (Dyalog Unicode) , 16 байтов SBCS

Всецело основано на математическом мастерстве моего коллеги Маршалла .

Анонимная инфиксная функция. Принимает k в качестве правого аргумента и n в качестве левого аргумента.

{×/⍵!⍺-+10,⍵}

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

{... } анонимная лямбда; левый аргумент ( n ) и правый аргумент ( k )

0,⍵ ставить ноль до k

¯1↓ выбросить последний элемент из этого

+\ накопленная сумма этого

⍺- вычесть это из п

⍵! ( k ) что

×/ продукт этого

Адам
источник
1

PARI / GP, 43 байта

Довольно просто; Помимо форматирования, версия без заглядывания вполне может быть идентична.

m(n,v)=n!/prod(i=1,#v,v[i]!)/(n-vecsum(v))!
Чарльз
источник
1

Matlab 48 байтов

Вам нужно установить , formatчтобы longзаранее , чтобы получить более высокую точность. Тогда это довольно просто:

@(n,k)factorial(n)/prod(factorial([k,n-sum(k)]))

ans(95, [65,4,4])
ans =

 1.934550571913395e+33
brainkz
источник
1

Pyth, 10 байт

/F.!MaQ-FQ

Попробуйте онлайн: демонстрация

Объяснение:

/F.!MaQ-FQ   implicit: Q = input list
       -FQ   reduce Q by subtraction
     aQ      append the result to Q
  .!M        compute the factorial for each number
/F           reduce by division
Jakube
источник
1

J, 16 байт

[(%*/)&:!],(-+/)

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

Для больших значений используется суффикс xдля обозначения целых чисел с расширенной точностью.

   f =: [(%*/)&:!],(-+/)
   11 f 1 4 4
34650
   15x f 5 4 3 2
37837800

объяснение

[(%*/)&:!],(-+/)  Input: n on LHS, A on RHS
             +/   Reduce A using addition
            -     Subtract that sum from n, this is the missing term
         ]        Get A
          ,       Append the missing term to A to make A'
[                 Get n
      &:!         Take the factorial of n and each value in A'
   */             Reduce using multiplication the factorials of A'
  %               Divide n! by that product and return
миль
источник
1

05AB1E , 8 байтов

Ƹ«!R.«÷

Попробуйте онлайн! Объяснение:

Æ           Subtract all the elements from the first
 ¸«         Append to the original list
   !        Take the factorial of all the elements
    R.«÷    Reduce by integer division

Кажется, я не могу найти лучшие способы выполнить шаг 2 или шаг 4.

Нил
источник
0

Clojure, 70 байт

#(let[a apply](a /(map(fn[x](a *(map inc(range x))))(conj %(a - %)))))

Создает анонимную функцию, принимающую все аргументы как один список, с nпервым.

30 символов «впустую», просто определяя чертову факториальную функцию. Ну что ж.

MattPutnam
источник
0

Perl 6 ,  52  50 байт

->\n,\k{[*](1..n)div[*] ([*] 1..$_ for |k,[-] n,|k)}

Попробуй это

->\n,\k{[*](1..n)/[*] ([*] 1..$_ for |k,[-] n,|k)}

Проверьте это (результат - Rational с знаменателем 1)

Expanded:

->     # pointy block lambda
  \n,
  \k
{
    [*]( 1 .. n )   # factorial of 「n」

  /                 # divide (produces Rational)

    [*]             # reduce the following using &infix:«*»

      (
          [*] 1..$_ # the factorial of

        for         # each of the following

          |k,       # the values of 「k」 (slipped into list)
          [-] n,|k  # 「n」 minus the values in 「k」
      )
}
Брэд Гилберт b2gills
источник