HW_4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=\"4\" style=\"color:red;\"> **IMPORTANT: ** When submitting this homework notebook, only modify the cells that start with:</font>\n",
    "\n",
    "```python\n",
    "# modify this cell\n",
    "```\n",
    "\n",
    "<font style=\"color:red;\"> 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.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Integer compositions\n",
    "\n",
    "A $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)$.\n",
    "\n",
    "The following problems ask you to generate such compositions, verify the above formula computationally, and to generate and enumerate constrined compositions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Helper Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "import numpy as np\n",
    "import scipy as sp\n",
    "from scipy.special import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This helper function not used in your homework. You don't need to know how it works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_compositions(func_out):\n",
    "    for x in func_out:\n",
    "        string = \"\"\n",
    "        for i in x:\n",
    "           string = string + str(i)+ \" + \"\n",
    "        print(string[0:-2])   \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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$. \n",
    "\n",
    "<font  style=\"color:blue\"> **Code:**</font>\n",
    "```python\n",
    "func_out = compositions(3,4)\n",
    "\n",
    "print \"all possible combinations: \"\n",
    "print_compositions(func_out)\n",
    "print;print \"Actual Output from compositions(3,4)\"; func_out\n",
    "```\n",
    "\n",
    "\n",
    "<font  style=\"color:magenta\"> **Output**</font>\n",
    "```\n",
    "all possible combinations: \n",
    "1 + 2 + 1 \n",
    "2 + 1 + 1 \n",
    "1 + 1 + 2 \n",
    "\n",
    "Actual Output from: compositions(3,4)\n",
    "{(1, 1, 2), (1, 2, 1), (2, 1, 1)}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "ex1",
     "locked": true,
     "points": "5",
     "solution": false
    }
   },
   "source": [
    "#### This is not for general, but for specific (for 2)\n",
    "from itertools import combinations_with_replacement\n",
    "def compositions(k, n):\n",
    "    # inputs: k and n are of type 'int'\n",
    "    # output: a set of tuples\n",
    "    f=[]\n",
    "    l= range(1,n)\n",
    "    c= combinations_with_replacement(l,k)\n",
    "    for i,j in c:\n",
    "        if i+j==n:\n",
    "            f.append((i,j))\n",
    "            f.append((j,i))\n",
    "    return set(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# modify this cell\n",
    "\n",
    "def compositions(k, n):\n",
    "    # inputs: k and n are of type 'int'\n",
    "    # output: a set of tuples\n",
    "    if k == 1:\n",
    "        return {(n,)}\n",
    "    else:\n",
    "        s = set()\n",
    "        for i in range(1, n):\n",
    "            for j in compositions(k - 1, n - i): #i + n-i = n\n",
    "                s.add((i,) + j)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Check Function\n",
    "func_out = compositions(2, 8)\n",
    "assert type(func_out).__name__ == \"set\"\n",
    "assert func_out == {(1, 7), (2, 6), (3, 5), (4, 4), (5, 3), (6, 2), (7, 1)}\n",
    "\n",
    "#\n",
    "# AUTOGRADER TEST - DO NOT REMOVE\n",
    "#\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 2\n",
    "\n",
    "Write a function **composition_formula** that takes two positive integers, $k$ and $n$,\n",
    "and returns the number of $k$-compositions of $n$ calculated in two different ways:\n",
    "first by calculating the number of compositions returned by **compositions**, \n",
    "then by using the binomial formula $\\binom{n-1}{k-1}$. The returned value should be a\n",
    "tuple consisting of the (same) integer calculated in the two ways.\n",
    "\n",
    "<font  style=\"color:blue\"> **Code**</font>\n",
    "```python\n",
    "print len(compositions(3, 4))\n",
    "print int(binom(4-1, 3-1))\n",
    "print composition_formula(3, 4)\n",
    "```\n",
    "\n",
    "<font  style=\"color:magenta\"> **Output**</font>\n",
    "```python\n",
    "3\n",
    "3\n",
    "(3, 3)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "ex2",
     "locked": true,
     "points": "5",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# modify this cell\n",
    "\n",
    "def composition_formula(k, n):\n",
    "    # inputs: k and n are of type 'int'\n",
    "    # output: a set of tuples, (int, int)\n",
    "    a= len(compositions(k,n))\n",
    "    b= int(binom(n-1,k-1))\n",
    "    return a,b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Check Function\n",
    "assert composition_formula(4, 12) == (165,165)\n",
    "\n",
    "#\n",
    "# AUTOGRADER TEST - DO NOT REMOVE\n",
    "#\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 3\n",
    "\n",
    "Let $\\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. \n",
    "\n",
    "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$. \n",
    "\n",
    "Hint: You may invoke the **compositions** function.\n",
    "\n",
    "<font  style=\"color:blue\"> **Code**</font>\n",
    "```python\n",
    "func_out = constrained_compositions(7, [3, 2, 5])\n",
    "\n",
    "print \"all possible combinations: \"\n",
    "print_compositions(func_out)\n",
    "print;print \"Actual Output from compositions(3,7)\"; func_out\n",
    "```\n",
    "\n",
    "\n",
    "<font  style=\"color:magenta\"> **Output**</font>\n",
    "```\n",
    "all possible combinations: \n",
    "1 + 2 + 4 \n",
    "2 + 1 + 4 \n",
    "3 + 2 + 2 \n",
    "3 + 1 + 3 \n",
    "1 + 1 + 5 \n",
    "2 + 2 + 3 \n",
    "\n",
    "Actual Output from compositions(3,7)\n",
    "{(1, 1, 5), (1, 2, 4), (2, 1, 4), (2, 2, 3), (3, 1, 3), (3, 2, 2)}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "ex3",
     "locked": true,
     "points": "5",
     "solution": false
    }
   },
   "source": [
    "#### This is not for general, but for specific (for 3)\n",
    "def constrained_compositions(n, m):\n",
    "    # inputs: n is of type 'int' and m is a list of integers\n",
    "    # output: a set of tuples\n",
    "    l=[]\n",
    "    i=m[0]\n",
    "    j=m[1]\n",
    "    k=m[2]\n",
    "    while i>0:\n",
    "        if i+j+k==n:\n",
    "            l.append((i,j,k))\n",
    "        while j>0:\n",
    "            if i+j+k==n:\n",
    "                l.append((i,j,k))\n",
    "            while k>0:\n",
    "                if i+j+k==n:\n",
    "                    l.append((i,j,k))\n",
    "                k=k-1\n",
    "            k=m[2]\n",
    "            j=j-1\n",
    "        j=m[1]\n",
    "        i=i-1\n",
    "    \n",
    "    return set(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# modify this cell\n",
    "\n",
    "def constrained_compositions(n, m):\n",
    "    # inputs: n is of type 'int' and m is a list of integers\n",
    "    # output: a set of tuples\n",
    "    k = len(m)\n",
    "    s = set()\n",
    "    for c in compositions(k, n):\n",
    "        if sum([c[i] <= m[i] for i in range(k)]) == k: #taking the sets of all comb. which are less than equal to the given \n",
    "            s.add(c)\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Check Function\n",
    "func_out = constrained_compositions(7, [1,4,4])\n",
    "assert type(func_out).__name__ == \"set\"\n",
    "assert constrained_compositions(7, [1,4,4]) == {(1, 2, 4), (1, 3, 3), (1, 4, 2)}\n",
    "\n",
    "#\n",
    "# AUTOGRADER TEST - DO NOT REMOVE\n",
    "#\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "48px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}