foo(n, k) возвращает все разбиения числа n, в которых слагаемые не больше k.
foo(0, k) возвращает пустой список
Находим рекуррентное соотношение, как [i] + каждое разбиение из foo(n-i, i) для i = (0, min(n, k))
def foo(n, k = None):
if k is None:
k = n
if n == 0:
return []
result = []
if n <= k:
result.append([n])
for i in range(1, 1+min(n, k)):
for l in foo(n-i, i):
result.append(l + [i])
return result
print(*foo(5), sep='n')
[5] [1, 1, 1, 1, 1] [1, 1, 1, 2] [1, 2, 2] [2, 3] [1, 1, 3] [1, 4]
То же, с list comprehension:
def foo(n, k = None):
if k is None:
k = n
if n == 0:
return []
return ([[n]] if n<=k else []) + [
l + [i]
for i in range(1, 1+min(n, k))
for l in foo(n-i, i)]
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Math module in Python contains a number of mathematical operations, which can be performed with ease using the module. math.comb() method in Python is used to get the number of ways to choose k items from n items without repetition and without order. It basically evaluates to n! / (k! * (n – k)!) when k n. It is also known as binomial coefficient because it is equivalent to the coefficient of k-th term in polynomial expansion of the expression (1 + x)n.
This method is new in Python version 3.8.
Syntax: math.comb(n, k)
Parameters:
n: A non-negative integer
k: A non-negative integerReturns: an integer value which represents the number of ways to choose k items from n items without repetition and without order.
Code #1: Use of math.comb() method
import math
n = 10
k = 2
nCk = math.comb(n, k)
print(nCk)
n = 5
k = 3
nCk = math.comb(n, k)
print(nCk)
Code #2: When k > n
import math
n = 3
k = 5
nCk = math.comb(n, k)
print(nCk)
Code #3: Use of math.comb() method to find coefficient of k-th term in binomial expansion of expression (1 + x)n
import math
n = 5
k = 2
nCk = math.comb(n, k)
print(nCk)
n = 8
k = 3
nCk = math.comb(n, k)
print(nCk)
Reference: Python math library
Last Updated :
23 Jan, 2020
Like Article
Save Article
Wolfram Mathworld:
P(n, k) denotes the number of ways of writing n as a sum of exactly k
terms or, equivalently, the number of partitions into parts of which
the largest is exactly k. (Note that if «exactly k» is changed to «k
or fewer» and «largest is exactly k,» is changed to «no element
greater than k,» then the partition function q is obtained.) For
example, P(5, 3) = 2, since the partitions of 5 of length 3 are {3, 1, 1}
and {2, 2, 1}, and the partitions of 5 with maximum element 3 are {3, 2}
and {3, 1, 1}.
…
P(n, k) can be computed from the recurrence relation
P(n, k) = P(n-1, k-1) + P(n-k, k)
(Skiena 1990, p. 58; Ruskey) with P(n, k) = 0 for k > n, P(n, n) = 1, and
P(n, 0) = 0.
So if we want to calculate the number of ways of writing n as a sum, we should calculate-
Let’s define P(n, k):
def p(n, k):
"""Gives the number of ways of writing n as a sum of exactly k terms or, equivalently,
the number of partitions into parts of which the largest is exactly k.
"""
if n < k:
return 0
if n == k:
return 1
if k == 0:
return 0
return p(n-1, k-1) + p(n-k, k)
Now we can calculate the number of ways of writing n as a sum:
n = 6
partitions_count = 0
for k in range(n + 1):
partitions_count += p(n, k)
print(partitions_count)
# Output:
# 11
As p(n, k) is a recursive function, you can boost the speed by saving values of each p(n, k) in a dictionary (thanks to the fast hash-based search!) and check if we have calculated the value (check if the value is in the dictionary) before calculating:
dic = {}
def p(n, k):
"""Gives the number of ways of writing n as a sum of exactly k terms or, equivalently,
the number of partitions into parts of which the largest is exactly k.
"""
if n < k:
return 0
if n == k:
return 1
if k == 0:
return 0
key = str(n) + ',' + str(k)
try:
temp = dic[key]
except:
temp = p(n-1, k-1) + p(n-k, k)
dic[key] = temp
finally:
return temp
Full function:
def partitions_count(n):
"""Gives the number of ways of writing the integer n as a sum of positive integers,
where the order of addends is not considered significant.
"""
dic = {}
def p(n, k):
"""Gives the number of ways of writing n as a sum of exactly k terms or, equivalently,
the number of partitions into parts of which the largest is exactly k.
"""
if n < k:
return 0
if n == k:
return 1
if k == 0:
return 0
key = str(n) + ',' + str(k)
try:
temp = dic[key]
except:
temp = p(n-1, k-1) + p(n-k, k)
dic[key] = temp
finally:
return temp
partitions_count = 0
for k in range(n + 1):
partitions_count += p(n, k)
return partitions_count
Helpful links:
- Partitions — Numberphile
- Partiton (number theory)
Рекурсия. Какие эмоции вызывает у вас это слово? Страх? Восторг? Тут возможны варианты. Но, честно говоря, рекурсия это просто еще один способ решения итеративных задач.
В наших циклах for мы выполняем какое-то действие Х десять раз. А в рекурсии Х — это повторный вызов того же метода. И вместо того чтобы вызывать его десять раз, мы вызываем его до тех пор, пока не будет соблюдено какое-то условие. Что это может быть за условие? Его мы определяем сами.
Давайте разберем это на примере решения задачи с собеседования.
Трамплин для прыжков в воду должен быть определенной длины и сделан из определенного числа досок. Имея список чисел (каждое число - длина какой-нибудь доски) и число k, определите, можно ли из любых двух чисел из списка составить число k. Например, если дан список [10, 15, 3, 7] и k = 17, нужно вернуть True, потому что 10 + 7 равно 17.
Для начала давайте подумаем, как нам решить эту задачу итеративно. Придумаем брутфорс-решение, так сказать.
Мы можем просто создать вложенный цикл for, в котором будем складывать каждое число списка с каждым из остальных чисел в списке, проверяя, равна ли их сумма k.
Начнем с создания метода add_to_k(), принимающего два параметра: наш список numbers и сумму k.
def add_to_k(numbers, k):
pass
В первом цикле for мы будем перебирать индексы в диапазоне от 0 до длины списка, уменьшенной на единицу. Мы вычитаем единицу, чтобы впоследствии не захватывать последний элемент списка: за ним уже ничего нет, так что не будет, с чем его сравнивать.
def add_to_k(numbers, k):
for i in range(len(numbers) - 1):
...
Внутри цикла мы возьмем первый выбранный элемент и поместим его в переменную current. После этого нам нужно пересмотреть все числа в списке, идущие за этим элементом. Тут нам поможет вложенный цикл for.
def add_to_k(numbers, k):
for i in range(len(numbers) - 1):
current = numbers[i]
for j in range(i + 1, len(numbers)):
...
Наконец, если сумма двух чисел равна k, мы вернем True. Если мы переберем весь список и не найдем подходящих слагаемых, дающих в сумме k, мы вернем False (вне цикла). Все вместе выглядит следующим образом:
def add_to_k(numbers, k):
for i in range(len(numbers) - 1):
current = numbers[i]
for j in range(i + 1, len(numbers)):
# print("checking", current, "+", numbers[j])
if current + numbers[j] == k:
return True
return False
Давайте попробуем запустить это решение.
num_list = [10, 15, 3, 7] k = 10 print(add_to_k(num_list, k)) # -> True
Отлично. Задача решена, но можно ли сделать то же самое рекурсивно?
Рекурсивный поиск
Начинаем писать метод точно так же. Он будет принимать параметры numbers и k.
def add_to_k_recursive(numbers, k):
pass
Далее нам нужно определить наш базовый случай (или случаи). Когда имеешь дело с рекурсией, нужно спросить себя: «Каким будет простейший случай?» Подключите своего внутреннего ленивого программиста. Если бы вам нужно было решить эту задачу, имея возможность выбрать список, какой бы вы выбрали?
Вероятно, это был бы список со всего одним элементом: в этом случае ответ точно был бы False. Это и будет наш первый базовый случай. Поставим длину списка меньше 2: таким образом пустые списки тоже попадут в эту категорию.
def add_to_k_recursive(numbers, k):
if (len(numbers) < 2):
return False
Что дальше? Нам нужно прописать еще один базовый случай. Если список должен содержать как минимум два элемента, самым простым вариантом будет список, содержащий ровно два элемента! В таком случае мы сможем просто сложить эти два числа и проверить, равна ли их сумма k. Поскольку длина списка нам не известна, давайте будем просто складывать первый и последний элемент списка.
def add_to_k_recursive(numbers, k):
if (len(numbers) < 2):
return False
elif numbers[0] + numbers[-1] == k:
return True
Теперь нам остается только прописать наш рекурсивный случай, т. е. тот, где мы заново вызываем наш метод.
Давайте подумаем. Наш список — [10, 15, 3, 7] и мы ищем числа, в сумме дающие 10.
Очевидно, что длина списка больше 2, так что мы пропускаем первое условие if. В elif мы видим, что первый и последний элементы в сумме дают 17, что не равно 10. И что теперь?
Нам нужно вызвать метод add_to_k_recursive() для меньшего списка, в котором первый и последний элементы будут другими. Мы можем проверить два варианта меньшего списка:
- Все те же числа, за исключением первого значения.
- Все те же числа, за исключением последнего значения.
На Python это выглядит следующим образом (см. срезы):
numbers[1:] numbers[:-1]
Таким образом, мы будем вызывать наш метод дважды, по разу для каждого из двух меньших списков. Что мы будем возвращать? Припомните, что в Python при помощи or можно вернуть первое истинное значение. Мы вернем один вызов метода или другой.
def add_to_k_recursive(numbers, k):
if (len(numbers) < 2):
return False
elif numbers[0] + numbers[-1] == k:
return True
else:
return add_to_k_recursive(numbers[:-1], k) or add_to_k_recursive(numbers[1:],
Проверяем
Запустим тот же код, что и раньше. Мы должны получить тот же результат — True.
num_list = [10, 15, 3, 7] k = 10 print(add_to_k_recursive(num_list, k))
Давайте посмотрим, что происходит под капотом.
Мы начинаем со списка [10, 15, 3, 7]. Как уже говорилось, первый и последний элементы в сумме не дают 10. Поэтому мы вызываем функцию снова для меньших списков, [10, 15, 3] и [15, 3, 7].
Каждый из этих списков снова разбивается надвое. Второй список разделится на [15, 3] и [3, 7]. Вызов нашего метода для последнего из этих списков вернет True. Таким образом True будет возвращаться по цепочке вверх до начального экземпляра метода.
Надеемся, это помогло вам приблизиться к пониманию рекурсии. Ее применение в данном случае ничуть не улучшило временную сложность решения. Нам все равно приходится просматривать каждое число дважды (примерно), а это O(N2). Но вы можете найти это решение более элегантным. К тому же, уметь применять рекурсию — совсем не плохо, особенно, когда в задаче на собеседовании нужно проверить «все возможные комбинации».
Найти такое разложение числа N на слагаемые, чтобы их произведение было максимальным
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| »’ | |
| Первый посыл: наибольшее значение получается, если разделить число на несколько одинаковых слагаемых, а потом их все перемножить. | |
| Тогда мы получим функцию (n/x)**x, где n — исходное число, x — количество слагаемых. | |
| Найдем экстремум этой функции, приравняв к нулю ее производную по числу слагаемых: | |
| [(n/x)^x]’ = (ln(n/x)-1)*(n/x)^x = 0, | |
| ln(n/x) = 1, | |
| x = n/e. | |
| Таким образом, получаем, что для максимизации данной функции надо разложить число на x слагаемых, | |
| каждое из которых как можно ближе к значению e=2.71828… Таких чисел два — 2 и 3. | |
| Второй посыл: из условия максимизации следует, что нам надо использовать как можно больше троек в разложении. | |
| В идеале n = 3x, а ответ к задаче — 3^x. | |
| Но что делать, если число не делится на три нацело? Здесь есть два случая: | |
| — n = 3x + 1: | |
| В этом случае мы теряем один множитель в итоговом разложении — умножение на единицу не меняет ответа. | |
| Но мы можем представить исходное число в ином виде и увеличить ответ: | |
| n = 3*(x-1) + 4, | |
| answer = 3^(x-1) * 4; | |
| — n = 3x + 2: | |
| В этом случае оставшаяся двойка будет играть роль последнего множителя, и мы получим: | |
| answer = 3^x * 2. | |
| »’ | |
| def task128(n): | |
| threes, remainder = divmod(n, 3) | |
| if remainder == 0: | |
| return 3**threes | |
| elif remainder == 1: | |
| return 4 * 3**(threes — 1) | |
| else: | |
| return 2 * 3**threes |