Выведите n-й номер звонка

13

Номер Белл ( OEIS A000110 ) является количеством способов разбиения набора п меченых (различных) элементов. Номер 0-го звонка определяется как 1.

Давайте рассмотрим несколько примеров (я использую скобки для обозначения подмножеств и скобок для разделов):

1: {1}
2: {[1,2]}, {[1],[2]}
3: {[1,2,3]}, {[1,2],[3]}, {[1,3],[2]}, {[2,3],[1]}, {[1],[2],[3]}

Есть много способов вычислить числа Белла, и вы можете использовать любой из них. Один из способов будет описан здесь:

Самый простой способ вычислить числа Белла - это использовать числовой треугольник, напоминающий треугольник Паскаля, для биномиальных коэффициентов. Числа Белла появляются на краях треугольника. Начиная с 1, каждая новая строка в треугольнике строится путем взятия последней записи в предыдущей строке в качестве первой записи, а затем установки каждой новой записи для ее левого соседа плюс его верхнего левого соседа:

1
1    2
2    3    5
5    7   10   15
15  20   27   37   52

Вы можете использовать 0-индексирование или 1-индексирование. Если вы используете 0-индексирование, ввод 3должен выводить 5, но должен выводить, 2если вы используете 1-индексацию.

Ваша программа должна работать до 15-го числа Белла, выводя 1382958545. Теоретически, ваша программа должна быть способна обрабатывать большие числа (другими словами, не жестко кодировать решения). РЕДАКТИРОВАТЬ: вам не нужно обрабатывать ввод 0 (для индексации 0) или 1 (для индексации 1), потому что он не рассчитывается методом треугольника.

Тестовые случаи (при условии 0-индексации):

0 ->  1 (OPTIONAL)
1 ->  1 
2 ->  2 
3 ->  5 
4 ->  15 
5 ->  52 
6 ->  203 
7 ->  877 
8 ->  4140 
9 ->  21147 
10 -> 115975 
11 -> 678570 
12 -> 4213597 
13 -> 27644437 
14 -> 190899322 
15 -> 1382958545

Ответы, использующие встроенный метод (такой как BellB [n] в языке Wolfram Language), который напрямую генерирует числа Белла, будут неконкурентоспособными.

Самый короткий код (в байтах) выигрывает.

code-golf math сфальсифицированы
источник
Если вы используете 0 индексацию, ввод 3вывода должны5 были бы Ouput 15, верно? И с 1-индексированием это 5
Луис Мендо
Причиной этого было подсчет 0-го номера звонка как индекса 0 в 0-индексации и индекса 1 в 1-индексации. Ваш путь может быть более ясным, но существующие ответы работают так, поэтому я не могу изменить его сейчас. Я только что присоединился к этому сайту несколько часов назад
сфальсифицировано
Но вы говорите, что при 1-индексировании ввод 3должен выводиться 2. Тогда что даст вход 1с 1-индексацией?
Луис Мендо
1 -> 1, 2 -> 1, 3 -> 2 (соответствует номерам 0-го, 1-го и 2-го звонка), а не 0 -> 1, 1 -> 1, 2 -> 2 Возможно, я использую неправильное терминология
сфальсифицировано
Я думаю, я понял. Первая 1 отсутствует в вашем примере таблицы и вывода, что меня смутило
Луис Мендо

Ответы:

2

Желе , 9 байт

ṖµṀcæ.߀‘

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

формула

который закрыт всякий раз, когда п <2 .

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

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

ṖµṀcæ.߀‘  Main link. Argument: n

Ṗ          Pop; yield A := [1, ..., n-1].
 µ         Begin a new, monadic chain with argument A.
  Ṁ        Maximum; yield n-1.
   c       Combinatons; compute (n-1)C(k) for each k in A.
      ߀   Recursively map the main link over A.
    æ.     Take the dot product of the results to both sides.
        ‘  Increment; add 1 to the result.
Деннис
источник
8

JavaScript (ES6), 47 байт

f=(n,a=[b=1])=>n--?f(n,[b,...a.map(e=>b+=e)]):b
f=(n,a=[b=1])=>--n?f(n,[b,...a.map(e=>b+=e)]):b

Первый индексируется 0, второй индексируется 1.

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

Haskell, 36 байт

head.(iterate(last>>=scanl(+))[1]!!)

Использует метод треугольника, правильно обрабатывает 0, 0 на основе.

Кристиан Сиверс
источник
5

R , 31 байт

sum(gmp::Stirling2.all(scan()))

использует число Стирлинга формулы второго рода и вычисляет эти числа с помощью пакета gmp ; читает из стандартного ввода и возвращает значение в виде большого целого числа; терпит неудачу для 0; 1-индексироваться.

Giuseppe
источник
4

Mathematica, 24 байта

Sum[k^#/k!,{k,0,∞}]/E&

-13 байт от @Kelly Lowder!

J42161217
источник
Sum[k^#/k!,{k,0,∞}]/E& всего 24 байта
Келли Лоудер
3

Желе , 14 12 11 байт

ṫ0;⁸+\
1Ç¡Ḣ

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

Не совсем ударил сильные стороны желе с динамическим вводом в ¡, Ṫ всегда изменяя массив и отсутствие предваряющего атома (однобайтовый ;@или обратный ṭ).

PurkkaKoodari
источник
3

CJam (19 байт)

Xa{X\{X+:X}%+}qi*0=

Онлайн демо

рассечение

Xa         e# Start with an array [1]
{          e# Repeat...
  X\       e#   Put a copy of X under the current row
  {X+:X}%  e#   Map over x in row: push (X+=x)
  +        e#   Prepend that copy of last element of the previous row to get the next row
}
qi*        e# ... input() times
0=         e# Select the first element
Питер Тейлор
источник
3

MATL , 14 байтов

:dtEw1Zh1Ze/Yo

Ввод на основе 0. Попробуйте онлайн!

объяснение

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

введите описание изображения здесь

где p F q ( a 1 , ..., a p ; b 1 , ..., b q ; x ) - обобщенная гипергеометрическая функция .

:      % Implictly input n. Push array [1 2 ... n]
d      % Consecutive differences: array [1 ... 1] (n-1 entries)
tE     % Duplicate, multiply by 2: array [2 ... 2] (n-1 entries)
w      % Swap
1      % Push 1
Zh     % Hypergeometric function
1Ze    % Push number e
/      % Divide
Yo     % Round (to prevent numerical precision issues). Implicitly display
Луис Мендо
источник
3

Python , 42 байта

f=lambda n,k=0:n<1or k*f(n-1,k)+f(n-1,k+1)

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

Рекурсивная формула происходит от размещения nэлементов в разделах. Для каждого элемента по очереди мы решаем, разместить ли его:

  • В существующий раздел, из которого есть kвыбор
  • Чтобы начать новый раздел, который увеличивает количество вариантов k для будущих элементов

В любом случае количество оставшихся nэлементов уменьшается . Итак, мы имеем рекурсивную формулу f(n,k)=k*f(n-1,k)+f(n-1,k+1)и f(0,k)=1, с f(n,0)n-м числом Белла.

XNOR
источник
2

Python 2 , 91 байт

s=lambda n,k:n*k and k*s(n-1,k)+s(n-1,k-1)or n==k
B=lambda n:sum(s(n,k)for k in range(n+1))

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

B (n) рассчитывается как сумма чисел Стирлинга второго рода.

Час Браун
источник
Это хорошее решение. Обратите внимание, что использование встроенных чисел Стирлинга второго рода позволило бы вычислить числа Белла (при использовании Mathematica или аналогичных)
сфальсифицировано
Вы можете сохранить два байта непосредственно в определении s: поскольку рекурсивные вызовы всегда уменьшить nи нет деления на kвы можете потерять *kв первом члене.
Питер Тейлор
Или вы можете сохранить связку, сгруппировав одну лямбду, работая над целыми рядами:B=lambda n,r=[1,0]:n and B(n-1,[k*r[k]+r[k-1]for k in range(len(r))]+[0])or sum(r)
Питер Тейлор,
поскольку ваша функция Bне является рекурсивной, и это ваш окончательный ответ, вы можете опустить ее, B=чтобы сохранить 2 байта
Фелипе Нарди Батиста
2

MATLAB, 128 103 байта

function q(z)
r(1,1)=1;for x=2:z
r(x,1)=r(x-1,x-1);for y=2:x
r(x,y)=r(x,y-1)+r(x-1,y-1);end
end
r(z,z)

Довольно понятно. Пропуск точки с запятой в конце строки печатает результат.

25 байтов сэкономлено благодаря Луису Мендо.

сфальсифицированы
источник
2

Ом , 15 байт

2°M^┼ⁿ^!/Σ;αê/≈

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

Использует форумлу Добинского (даже работает на B (0) yay ).

объяснение

2°M^┼ⁿ^!/Σ;αê/≈
2°        ;     # Push 100
  M             # Do 100 times...
   ^             # Push index of current iteration
    ┼ⁿ           # Take that to the power of the user input
      ^!         # Push index factorial
        /        # Divide
         Σ       # Sum stack together
           αê   # Push e (2.718...)
             /  # Divide
              ≈ # Round to nearest integer (Srsly why doesn't 05AB1E have this???)
Datboi
источник
2

Python (79 байт)

B=lambda n,r=[1]:n and B(n-1,[r[-1]+sum(r[:i])for i in range(len(r)+1)])or r[0]

Онлайн-демонстрация в Python 2, но она также работает в Python 3.

Это строит треугольник Эйткена, используя рекурсивную лямбду для петли в гольфе.

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

J, 17 байт

0{]_1&({+/\@,])1:

Использует метод расчета треугольника.

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

объяснение

0{]_1&({+/\@,])1:  Input: integer n
               1:  The constant 1
  ]                Identity function, get n
   _1&(       )    Call this verb with a fixed left argument of -1 n times
                   on itself starting with a right argument [1]
             ]       Get right argument
       {             Select at index -1 (the last item)
            ,        Join
        +/\@         Find the cumulative sums
0{                 Select at index 0 (the first item)
миль
источник
1

Python 3 , 78 байт

from math import*
f=lambda n:ceil(sum(k**n/e/factorial(k)for k in range(2*n)))

Я решил попробовать другой путь для расчета. При этом используется формула Добински, 0-indexed, не работает для 0.

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

С МакЭвой
источник
1
поскольку ваша функция fне является рекурсивной, вы можете опустить f=и сохранить 2 байта
Felipe Nardi Batista
1

Python 3 , 68 60 байт

Простая рекурсивная конструкция треугольника, но она крайне неэффективна для практических целей. Вычисление до 15-го числа Белла приводит к тайм-ауту TIO, но он работает на моей машине.

Это использует 1-индексацию и возвращает Trueвместо 1.

f=lambda r,c=0:r<1or c<1and f(r-1,r-1)or f(r-1,c-1)+f(r,c-1)

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

Спасибо @FelipeNardiBatista за сохранение 8 байт!

Чейз Вогели
источник
60 байтов . возвращение логических значений вместо чисел (0,1) допустимо в питоне
Фелипе Нарди Батиста
1

PHP , 72 байта

рекурсивная функция 1-индексированная 

function f($r,$c=0){return$r?$c?f($r-1,$c-1)+f($r,$c-1):f($r-1,$r-2):1;}

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

PHP , 86 байт

0 индексированные 

for(;$r++<$argn;)for($c=~0;++$c<$r;)$l=$t[$r][$c]=$c?$l+$t[$r-1][$c-1]:($l?:1);echo$l;

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

PHP , 89 байт

рекурсивная функция с 0 индексами 

function f($r,$s=NULL){$c=$s??$r-1;return$r>1?$c?f($r-1,$c-1)+f($r,$c-1):f($r-1,$r-2):1;}

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

Йорг Хюльсерманн
источник
1

Алиса , 22 байта

/oi
\1@/t&wq]&w.q,+k2:

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

Это использует метод треугольника. Для n = 0 вместо этого вычисляется B (1), что обычно равно B (0).

объяснение

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

Программа использует стек в качестве расширяющейся круговой очереди для вычисления каждой строки треугольника. Во время каждой итерации после первой один неявный ноль под стеком становится явным нолем.

1     Append 1 to the implicit empty string on top of the stack
i     Get input n
t&w   Repeat outer loop that many times (push return address n-1 times)
q     Get tape position (initially zero)
]     Move right on tape
&w    On iteration k, push this return address k-1 times
      The following inner loop is run once for each entry in the next row
.     Duplicate top of stack (the last number calculated so far)
q,    Move the entry k spaces down to the top of the stack: this is the appropriate entry
      in the previous row, or (usually) an implicit zero if we're in the first column
+     Add these two numbers
k     Return to pushed address: this statement serves as the end of two loops simultaneously
2:    Divide by two: see below
o     Output as string
@     Terminate

Первая итерация фактически предполагает начальную глубину стека, равную нулю, несмотря на требуемую 1 на вершине стека. В результате 1 добавляется к самому себе, и весь треугольник умножается на 2. Деление окончательного результата на 2 дает правильный ответ.

Nitrodon
источник