Номер разбиения положительного целого числа определяется как количество способов, которыми оно может быть выражено как сумма положительных целых чисел. Другими словами, количество целочисленных разделов у него есть. Например, номер 4имеет следующие разделы:

[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

Следовательно, у него есть 5разделы. Это OEIS A000041 .

задача

По положительному целому числу N определить номер его раздела.

• Все стандартные правила применяются.

• Ввод и вывод могут быть обработаны любым разумным способом.

• Это код-гольф , поэтому выигрывает самый короткий код в байтах.

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

Вход | Выход

1 | 1
2 | 2
3 | 3
4 | 5
5 | 7
6 | 11
7 | 15
8 | 22
9 | 30
10 | 42

Pyth , 3 байта

l./

Попробуй это здесь! или попробуйте тестовый пакет.

Форматирование ответа заняло гораздо больше времени, чем написание самого кода: P.

Как?

Pyth - правильный инструмент для работы.

л. / Полная программа с неявным вводом.

 ./ Целочисленные разделы. Вернуть все отсортированные списки натуральных чисел, которые добавляются к входным данным.
длина.
      Неявно выведите результат.

Mathematica, 11 байт

PartitionsP

объяснение

¯\_(ツ)_/¯

Python 2 , 85 83 байта

-2 байта благодаря @notjagan

lambda n:n<1or sum(sum(i*((n-k)%i<1)for i in range(1,n+1))*p(k)for k in range(n))/n

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

Использование рекурсивной формулы из OEIS A000041 .

Эмоджикод 0,5, 204 201 байт

🐋🚂🍇🐖🅰️➡🚂🍇🍊⬅🐕1🍇🍎1🍉🍮s 0🔂k⏩0🐕🍇🍦t➖🐕k🍮r t🔂i⏩1 t🍇🍊😛🚮t i 0🍇🍮➕r i🍉🍉🍮➕s✖r🅰️k🍉🍎➗s🐕🍉🍉

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

-3 байта, используя «меньше или равно 1» вместо «меньше 2», потому что эмодзи «меньше чем» имеет довольно длинную кодировку UTF-8. Также сделал tзаморозку, чтобы заставить замолчать предупреждение, не влияя на количество байтов.

Расширяет класс inte (целое число) методом с именем 🅰️. Вы можете написать простую программу, которая берет число из ввода, вызывает 🅰️ на номер и печатает результат следующим образом:

🏁🍇
 🍦str🔷🔡😯🔤Please enter a number🔤
 🍊🍦num🚂str 10🍇
  😀🔡🅰️num 10
 🍉🍓🍇
  😀🔤Learn what a number is, you moron!🔤
 🍉
🍉

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

Ungolfed

🐋🚂🍇
 🐖🅰️➡🚂🍇
  🍊◀️🐕2🍇
   🍎1
  🍉
  🍮sum 0
  🔂k⏩0🐕🍇
   🍦nmk➖🐕k
   🍮sig nmk
   🔂i⏩1 nmk🍇
    🍊😛🚮nmk i 0🍇
     🍮➕sig i
    🍉
   🍉
   🍮➕sum✖sig🅰️k
  🍉
  🍎➗sum🐕
 🍉
🍉

объяснение

Примечание: большой выбор смайликов не имеет особого смысла в смайликах 0.5. В конце концов, это 0.x 0.6 исправит это.

Emojicode - это объектно-ориентированный язык программирования, включающий в себя шаблоны, протоколы, дополнительные функции и замыкания, но эта программа не использует замыканий, и все шаблоны и протоколы могут считаться неявными, тогда как в заглушке ввода-вывода отображается только дополнительная опция.

Программа работает только с несколькими типами: 🚂 является целочисленным типом, 🔡 является типом строки и ⏩ является типом диапазона. Также появляется несколько логических значений (👌), но они используются только в условиях. Логические значения могут принимать значения 👍 или 👎, которые соответствуют истинам и ложностям соответственно.

В настоящее время в Emojicode нет операторов, поэтому сложение, сравнения и другие операции, которые обычно являются операторами, реализованы в виде функций, эффективно позволяя выражениям использовать префиксную нотацию . Операторы также запланированы в 0,6.

Давайте сначала займемся тестовой программой.

🏁

Это блок 🏁, который можно сравнить с основным из других языков.

🍇 ... 🍉

Виноград и арбузы объявляют кодовые блоки в смайлик.

🍦str🔷🔡😯🔤Please enter a number🔤

Это объявляет «замороженное» имя strи устанавливает его значение для новой строки, созданной с использованием инициализатора (конструктора) 😯, который принимает приглашение в виде строки, а затем вводит строку от пользователя. Зачем использовать замороженную вместо переменной? Это не изменится, поэтому переменная выдаст предупреждение.

🍊🍦num🚂str 10

Давайте разберемся с этим. 🚂str 10вызывает метод on для объекта strс аргументом 10. По соглашению, методы, названные с именем типа, преобразуют объект в этот тип. 10 - это база для целочисленного преобразования. Этот метод возвращает необязательный 🍬🚂. Необязательные могут содержать значение базового типа или пустоты, ⚡. Если строка не содержит числа, возвращается ⚡. Чтобы использовать значение, необходимо развернуть необязательное значение с помощью 🍺, что вызывает ошибку времени выполнения, если значение равно ⚡. Следовательно, хорошей практикой является проверка на пустоту перед развертыванием необязательного. Фактически, это так часто, что у Emojicode есть сокращение для этого. Обычно 🍊это «если».🍊🍦 variable expressionозначает: оценить выражение. Если необязательный элемент содержит пустоту, условие оценивается как 👎 (false). В противном случае, замороженное имя variableсоздается с развернутым значением необязательного значения, а условие оценивается как 👍 (true). Поэтому при нормальном использовании 🍇 ... 🍉вводится блок, следующий за условным.

😀🔡🅰️num 10

🅰️ - это метод, к которому основной код добавляет 🚂 с помощью 🐋, который вычисляет количество разделов. Это вызывает 🅰️ для numзамороженного объекта, который мы объявили в условном выражении, и преобразует результат в строку, используя базу 10 методом 🔡. Затем 😀 печатает результат.

🍓🍇 ... 🍉

🍓 означает «еще», поэтому этот блок вводится, когда пользователь неправильно ввел номер.

😀🔤Learn what a number is, you moron!🔤

Печатает строковый литерал.

Теперь давайте посмотрим на основную программу. Я объясню неоправданную версию; В версии для гольфа только что были удалены пробелы и переменные переименованы в одинарные буквы.

🐋🚂🍇 ... 🍉

Расширьте класс 🚂. Это функция, которая не часто встречается в языках программирования. Вместо создания нового класса с 🚂 в качестве суперкласса, 🐋 изменяет 🐋 напрямую.

🐖🅰️➡🚂🍇 ... 🍉

Создает новый метод с именем 🅰️, который возвращает 🚂. Возвращает количество разделов, рассчитанное по формулеa(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k)

🍊⬅🐕1🍇
 🍎1
🍉

🐕 аналогичен thisили selfиз других языков и относится к объекту метод был вызван. Эта реализация является рекурсивной, так что это условие завершения: если число, для которого был вызван метод, меньше или равно 1, вернуть 1.

🍮sum 0

Создайте новую переменную sumи установите для нее значение 0. Неявно предполагается тип type.

🔂k⏩0🐕

🔂 перебирает все, что реализует протокол 🔂🐚⚪️, тогда как ⏩ является литералом диапазона, который реализуется implement. Диапазон имеет начальное значение, конечное значение и значение шага, которое предполагается равным 1, если start < stop, или -1 в противном случае. Можно также указать значение шага, используя ⏭, чтобы создать литерал диапазона. Начальное значение является включающим, а конечное значение - исключительным, поэтому оно эквивалентно for k in range(n)или Sum_{k=0..n-1}в формуле.

🍦nmk➖🐕k

Нам нужно вычислить сигма (n - k) или сумму делителей n - kдругими словами, и аргумент необходим несколько раз, поэтому он сохраняется n - kв переменной, nmkчтобы сохранить несколько байтов.

🍮sig nmk
🔂i⏩1 nmk

Это устанавливает sigпеременную в аргумент сигма и перебирает все числа от 1 до nmk - 1. Я мог бы инициализировать переменную до 0 и итерировать по 1..nmk, но сделать это таким образом короче.

🍊😛🚮nmk i 0

🚮 вычисляет остаток, или модуль и 😛 проверяет равенство, поэтому условие будет 👍, если iделитель nmk.

🍮➕sig i

Это задание по вызову, похожее на семейство += -= >>=операторов в некоторых низших языках без смайликов. Эта строка также может быть записана как 🍮 sig ➕ sig i. Поэтому после завершения внутреннего цикла sigбудет содержать сумму делителей n - kилиsigma(n - k)

🍮➕sum✖sig🅰️k

Еще одно назначение по вызову, так что это добавляет sigma(n - k) * A(k)к итогу, как в формуле.

🍎➗sum🐕

Наконец, сумма делится на n и частное возвращается. Это объяснение, вероятно, заняло в три раза больше времени, чем написание самого кода ...

Пари / ГП , 8 байт

numbpart

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

Октава, 18 байт

partcnt(input(''))

Использует встроенную функцию partcnt.

Не можете сделать это правильно, используя анонимную функцию с помощью @, некоторая помощь будет оценена.

Сетчатка , 34 байта

.+
$*
+%1`\B
;$'¶$`,
,

%O`1+
@`.+

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

объяснение

.+
$*

Преобразовать ввод в унарный.

+%1`\B
;$'¶$`,

Это вычисляет все 2 ^n-1 разделов списка унитарных цифр. Мы делаем это путем многократного ( +) сопоставления первой ( 1) границы \B, не входящей в число слов ( то есть положения между двумя 1s) в каждой строке ( %), и замены его на ;все после него ( $'), перевод строки ( ¶), все перед это ( $`) и ,. Пример:

1;1,111

становится

      vv
1;1,1;11
1;1,1,11
^^^^^

Где vотмечает результат $'и ^отмечает результат $`. Это обычная идиома для получения результата двух разных замен одновременно (мы в основном вставляем как замену, так ;и ,замену, а также недостающие «половинки» строки для завершения двух полных замен).

Мы будем рассматривать ;как фактические разделы и ,как заполнители, которые не позволяют последующим \Bсопоставлениям там. Так что дальше ...

,

... мы удаляем эти запятые. Это дает нам все разделы. Например, для ввода 4мы получаем:

1;1;1;1
1;1;11
1;11;1
1;111
11;1;1
11;11
111;1
1111

Мы не заботимся о заказе, хотя:

%O`1+

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

@`.+

Наконец, мы подсчитываем @совпадения unique ( ) .+, то есть сколько разных строк / разделов мы получили. Я добавил эту @опцию давным-давно, затем совершенно забыл об этом и только недавно переоткрыл ее. В этом случае он сохраняет байт поверх первой дедупликации строк с D`.

Python 2 , 54 53 байта

f=lambda n,k=1:1+sum(f(n-j,j)for j in range(k,n/2+1))

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

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

Каждое разбиение n может быть представлено в виде списка x = [x ₁ , ⋯, x _m ], такого что x ₁ + ⋯ + x _m = n . Это представление становится уникальным, если мы требуем, чтобы x ₁ ≤ ⋯ ≤ x _m .

Определим вспомогательную функцию f (n, k), которая подсчитывает разбиения с нижней границей k , т. Е. Списки x такие, что x ₁ + ⋯ + x _m = n и k ≤ x ₁ ≤ ⋯ ≤ x _m . Для ввода n задача, таким образом, запрашивает вывод f (n, 1) .

Для натуральных чисел n и k , для которых k ≤ n , существует хотя бы одно разбиение с нижней границей k : одноэлементный список [n] . Если n = k (в частности, если n = 1 ), это единственный приемлемый раздел. С другой стороны, если k> n , решений вообще нет.

Если k <n , мы можем рекурсивно подсчитать оставшиеся разделы, построив их слева направо следующим образом. Для каждого j такого, что k ≤ j ≤ n / 2 , мы можем построить разбиения [x ₁ , ⋯, x _m ] = [j, y ₁ , ⋯, y _m-1 ] . Мы имеем, что x ₁ + ⋯ + x _m = n тогда и только тогда, когда y ₁ + ⋯ + y _m-1 = n - j . Кроме того, x ₁ ≤ ⋯ ≤ x _m, если и только если j ≤ y ₁ ≤ ₁ ≤ y _m-1 .

Следовательно, разделы x из n , начинающиеся с j, могут быть вычислены как f (n - j, j) , что считает действительные разделы y . Требуя, чтобы j ≤ n / 2 , мы гарантируем, что j ≤ n - j , поэтому существует по крайней мере один y . Таким образом, мы можем подсчитать все разбиения n путем суммирования 1 (для [n] ) и f (n - j, j) для всех допустимых значений j .

Код представляет собой простую реализацию математической функции f . Кроме того, для k по умолчанию задано значение 1 , поэтому f(n)вычисляется значение f (n, 1) для ввода n .

J , 37 35 байт

0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:

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

объяснение

0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:  Input: n
                                 1:  Constant 1
  ]                                  Get n
   1&(                          )    Repeat n times on x = [1]
                          \            For each prefix
                         #               Length
                      q:@                Prime factors
                 /.~&                    Group equal factors
              #.~                        Compute p+p^2+...+p^k for each group
           >:@                           Increment
                    &.q:                 Product
                           %           Divide
                            #          Length
         ]                             Get x
          *                            Times
   1   #.                              Sum
                              ,        Joim
                               ]       Get x
                                       Set this as next value of x
0{                                   Select value at index 0

JavaScript, 125 121 байт

n=>(z=(a,b)=>[...Array(a)].map(b))(++n**n,(_,a)=>z[F=z(n,_=>a%(a/=n,n)|0).sort().join`+`]=b+=eval(F)==n-1&!z[F],b=0)|b||1

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

Предупреждение: сложность времени и пространства экспоненциальна. Работает очень медленно для больших чисел.

Python 2 , 89 байт

-9 байт от Mr.Xcoder -1 байт от notjagan

lambda n:len(p(n))
p=lambda n,I=1:{(n,)}|{y+(x,)for x in range(I,n/2+1)for y in p(n-x,x)}

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

Желе , 13 байт

JÆsæ.:L;
1Ç¡Ḣ

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

Требуется 5 секунд, чтобы решить n = 1000 на TIO.

Java 8 (229 байт)

import java.util.function.*;class A{static int j=0;static BiConsumer<Integer,Integer>f=(n,m)->{if(n==0)j++;else for(int i=Math.min(m,n);i>=1;i--)A.f.accept(n-i,i);};static Function<Integer,Integer>g=n->{f.accept(n,n);return j;};}

Ungolfed:

import java.util.function.*;

class A {
    static int j = 0;
    static BiConsumer<Integer, Integer> f = (n, m) -> {
        if (n == 0)
            j++;
        else
            for (int i = Math.min(m, n); i >= 1; i--)
                A.f.accept(n - i, i);
    };
    static Function<Integer, Integer> g = n -> {
        f.accept(n, n);
        return j;
    };
}

Желе , 3 байта

ŒṗАтом недавно был добавлен, и это означает «целое число разделов».

ŒṗL

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

ŒṗL - Полная программа.

Œṗ - целочисленные разбиения.
  L - длина.
      - Вывод неявно.

Пыть , 2 байта

←ᵱ

Объяснение:

←          Get input
 ᵱ         Number of partitions

JavaScript ES7, 69 байт

n=>(f=(i,s)=>i?[for(c of Array(1+n))f(i-1,s,s-=i)]:c+=!s)(n,n,c=0)&&c

JavaScript ES6, 71 байт

n=>(f=(i,s)=>i?[...Array(1+n)].map(_=>f(i-1,s,s-=i)):c+=!s)(n,n,c=0)&&c

Сложность времени O (n ^ n), поэтому будьте осторожны (на моем компьютере появляется очевидная задержка F(6))