<jupyter_start><jupyter_text>**IMPORTANT: ** When submitting this homework notebook, only modify the cells that start with:```python modify this cell``` Do not add any new cells and do not import any packages. For working on the notebook, we reccomend you create a copy that you can use to test ideas.  Integer compositionsA $k$-composition of an integer $n$ is a $k$-tuple of positive integesrs that sum to $n$. As we saw, there are $\binom{n-1}{k-1}$ such compositions. For example, there are $\binom{4-1}{3-1}=\binom32=3\quad$ 3-compositions of 4: $(1,1,2)$, $(1,2,1)$, and $(2,1,1)$.The following problems ask you to generate such compositions, verify the above formula computationally, and to generate and enumerate constrined compositions.  Helper Code<jupyter_code>import sys
import numpy as np
import scipy as sp
from scipy.special import *<jupyter_output><empty_output><jupyter_text>This helper function not used in your homework. You don't need to know how it works.<jupyter_code>def print_compositions(func_out):
    for x in func_out:
        string = ""
        for i in x:
           string = string + str(i)+ " + "
        print(string[0:-2])<jupyter_output><empty_output><jupyter_text>Problem 1 Write a function **compositions** that takes two natural numbers $k$ and $n$ as inputs and returns the set of all tuples of size $k$ that sum to $n$.  **Code:**```pythonfunc_out = compositions(3,4)print "all possible combinations: "print_compositions(func_out)print;print "Actual Output from compositions(3,4)"; func_out``` **Output**```all possible combinations: 1 + 2 + 1 2 + 1 + 1 1 + 1 + 2 Actual Output from: compositions(3,4){(1, 1, 2), (1, 2, 1), (2, 1, 1)}```<jupyter_code>def compositions(k, n):
    # inputs: k and n are of type 'int'
    # output: a set of tuples
    
    s = set(get_tuples(k,n))
    return s
    
    
def get_tuples(length, sum):  
    if length == 1: 
        yield (sum,)
        return
    
    for i in range(1,sum):
        for j in get_tuples(length-1, sum-i):
            yield (i,)+j
# Check Function
func_out = compositions(2, 8)
assert type(func_out).__name__ == "set"
assert func_out == {(1, 7), (2, 6), (3, 5), (4, 4), (5, 3), (6, 2), (7, 1)}

#
# AUTOGRADER TEST - DO NOT REMOVE
#<jupyter_output><empty_output><jupyter_text>Problem 2Write a function **composition_formula** that takes two positive integers, $k$ and $n$,and returns the number of $k$-compositions of $n$ calculated in two different ways:first by calculating the number of compositions returned by **compositions**, then by using the binomial formula $\binom{n-1}{k-1}$. The returned value should be atuple consisting of the (same) integer calculated in the two ways. **Code**```pythonprint len(compositions(3, 4))print int(binom(4-1, 3-1))print composition_formula(3, 4)``` **Output**```python33(3, 3)```<jupyter_code>def composition_formula(k, n):
    # inputs: k and n are of type 'int'
    # output: a set of tuples, (int, int)
    
    length = len(compositions(k,n))
    bi = int(binom(n-1,k-1))
    return (length,bi)
    

# Check Function
assert composition_formula(4, 12) == (165,165)

#
# AUTOGRADER TEST - DO NOT REMOVE
#<jupyter_output><empty_output><jupyter_text>Problem 3Let $\boldsymbol{m}=(m_1,...,m_k)$ be a vector of $k$ positive integers. A $k$-composition $(a_1,...,a_k)$ of $n$ is $\boldsymbol{m}$-constrained if $a_i\leq m_i$ for all $1\le i\le k$. For example, $(1,1,3)$ and $(2,1,2)$ are the only $(2,1,4)$-constrined 3-partitions of 5. Write a function **constrained_compositions** that takes a natural number $n$ and a vector $\boldsymbol{m}$ of $k$ positive integers, and prints the set of all $\boldsymbol m$-constrained $k$-compositions of $n$. Note that $k$ can be inferred from $\boldsymbol m$. Hint: You may invoke the **compositions** function. **Code**```pythonfunc_out = constrained_compositions(7, [3, 2, 5])print "all possible combinations: "print_compositions(func_out)print;print "Actual Output from compositions(3,7)"; func_out``` **Output**```all possible combinations: 1 + 2 + 4 2 + 1 + 4 3 + 2 + 2 3 + 1 + 3 1 + 1 + 5 2 + 2 + 3 Actual Output from compositions(3,7){(1, 1, 5), (1, 2, 4), (2, 1, 4), (2, 2, 3), (3, 1, 3), (3, 2, 2)}```<jupyter_code>def constrained_compositions(n, m):
    # inputs: n is of type 'int' and m is a list of integers
    # output: a set of tuples
    
    length = len(m)
    set_u = compositions(length,n)
    set_c = set()
    
    for i in set_u:
        flag = 1
        
        for j in range(length):
            if i[j] > m[j]:
                flag = 0
        
        if flag==1:
            set_c.add(i)
            
    return set_c
# Check Function
func_out = constrained_compositions(7, [1,4,4])
assert type(func_out).__name__ == "set"
assert constrained_compositions(7, [1,4,4]) == {(1, 2, 4), (1, 3, 3), (1, 4, 2)}

#
# AUTOGRADER TEST - DO NOT REMOVE
#<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14294478527607363, 'fraction_numerical': 0.03496932515337423, 'mean_word_length': 3.8425742574257424, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '192355', 'license': 'MIT', 'n_tokens_mistral': 1796, 'n_tokens_neox': 1627, 'n_words': 589, 'path': 'Assignment/HW_4.ipynb', 'repo_name': 'iamryf/ECE-225A', 'size': '4890'}