{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# Combinations of lists (or maybe how itertools.product works)!?\n",
    "\n",
    "So here's a little challenge I need a generator for testing that produces all combinations of inputs from a number of lists. For example:"
   ]
  },
  {
   "cell_type": "code",
   "source": [
    "a,b,c = [1,2], [1,2,3], [1,2]"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "source": [
    "So how do we go about that?\n",
    "\n",
    "Python's `itertools.combinations` can't help us because it won't allow multiple lists as inputs.\n",
    "We need `itertools.product` instead:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "outputs": [],
   "source": [
    "import itertools"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 1, 1)\n",
      "(1, 1, 2)\n",
      "(1, 2, 1)\n",
      "(1, 2, 2)\n",
      "(1, 3, 1)\n",
      "(1, 3, 2)\n",
      "(2, 1, 1)\n",
      "(2, 1, 2)\n",
      "(2, 2, 1)\n",
      "(2, 2, 2)\n",
      "(2, 3, 1)\n",
      "(2, 3, 2)\n"
     ]
    }
   ],
   "source": [
    "for combination in itertools.product(*[a,b,c]):\n",
    "    print(combination)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "So how does it work?\n",
    "\n",
    "The simplest implementation I can come up with is to create a list of keys, and increment them step by step.\n",
    "\n",
    "Then, when the key reaches it's maximum index, we reset the values up to it."
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [],
   "source": [
    "def product(scales):\n",
    "    keys = [0 for _ in scales]\n",
    "    counter = 1\n",
    "    for sub_scale in scales:\n",
    "        counter *= len(sub_scale)\n",
    "\n",
    "    for c in range(counter):\n",
    "        v = [sub_scale[ix] for ix, sub_scale in zip(keys, scales)]\n",
    "        yield v\n",
    "\n",
    "        for pointer, sub_scale in enumerate(scales):\n",
    "            if keys[pointer] + 1 == len(sub_scale):\n",
    "                keys[pointer] = 0\n",
    "            else:\n",
    "                keys[pointer] += 1\n",
    "                break"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1]\n",
      "[2, 1, 1]\n",
      "[1, 2, 1]\n",
      "[2, 2, 1]\n",
      "[1, 3, 1]\n",
      "[2, 3, 1]\n",
      "[1, 1, 2]\n",
      "[2, 1, 2]\n",
      "[1, 2, 2]\n",
      "[2, 2, 2]\n",
      "[1, 3, 2]\n",
      "[2, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "for combination in product([a,b,c]):\n",
    "    print(combination)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "With this approach I can also pick out the nth combination, simply be recalculating the indices."
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [],
   "source": [
    "def nth_combination(n, scales):\n",
    "    counter = 1\n",
    "    for sub_scale in scales:\n",
    "        counter *= len(sub_scale)\n",
    "    if not 0 < n and n <= counter:\n",
    "        raise ValueError(f\"{n} > counter\")\n",
    "    values = []\n",
    "    multiplier = 1\n",
    "\n",
    "    for scale_no, sub_scale in enumerate(scales):\n",
    "        ix = (n % (len(sub_scale) * multiplier)) // multiplier\n",
    "        multiplier *= len(sub_scale)\n",
    "        values.append(sub_scale[ix])\n",
    "\n",
    "    return tuple(values)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 1, 4, 6) == (1, 1, 4, 6)\n",
      "(1, 1, 4, 7) == (1, 1, 4, 7)\n",
      "(1, 1, 4, 8) == (1, 1, 4, 8)\n",
      "(1, 1, 4, 9) == (1, 1, 4, 9)\n",
      "(1, 1, 5, 6) == (1, 1, 5, 6)\n",
      "(1, 1, 5, 7) == (1, 1, 5, 7)\n",
      "(1, 1, 5, 8) == (1, 1, 5, 8)\n",
      "(1, 1, 5, 9) == (1, 1, 5, 9)\n",
      "(1, 2, 4, 6) == (1, 2, 4, 6)\n",
      "(1, 2, 4, 7) == (1, 2, 4, 7)\n",
      "(1, 2, 4, 8) == (1, 2, 4, 8)\n",
      "(1, 2, 4, 9) == (1, 2, 4, 9)\n",
      "(1, 2, 5, 6) == (1, 2, 5, 6)\n",
      "(1, 2, 5, 7) == (1, 2, 5, 7)\n",
      "(1, 2, 5, 8) == (1, 2, 5, 8)\n",
      "(1, 2, 5, 9) == (1, 2, 5, 9)\n",
      "(1, 3, 4, 6) == (1, 3, 4, 6)\n",
      "(1, 3, 4, 7) == (1, 3, 4, 7)\n",
      "(1, 3, 4, 8) == (1, 3, 4, 8)\n",
      "(1, 3, 4, 9) == (1, 3, 4, 9)\n",
      "(1, 3, 5, 6) == (1, 3, 5, 6)\n",
      "(1, 3, 5, 7) == (1, 3, 5, 7)\n",
      "(1, 3, 5, 8) == (1, 3, 5, 8)\n",
      "(1, 3, 5, 9) == (1, 3, 5, 9)\n",
      "(2, 1, 4, 6) == (2, 1, 4, 6)\n",
      "(2, 1, 4, 7) == (2, 1, 4, 7)\n",
      "(2, 1, 4, 8) == (2, 1, 4, 8)\n",
      "(2, 1, 4, 9) == (2, 1, 4, 9)\n",
      "(2, 1, 5, 6) == (2, 1, 5, 6)\n",
      "(2, 1, 5, 7) == (2, 1, 5, 7)\n",
      "(2, 1, 5, 8) == (2, 1, 5, 8)\n",
      "(2, 1, 5, 9) == (2, 1, 5, 9)\n",
      "(2, 2, 4, 6) == (2, 2, 4, 6)\n",
      "(2, 2, 4, 7) == (2, 2, 4, 7)\n",
      "(2, 2, 4, 8) == (2, 2, 4, 8)\n",
      "(2, 2, 4, 9) == (2, 2, 4, 9)\n",
      "(2, 2, 5, 6) == (2, 2, 5, 6)\n",
      "(2, 2, 5, 7) == (2, 2, 5, 7)\n",
      "(2, 2, 5, 8) == (2, 2, 5, 8)\n",
      "(2, 2, 5, 9) == (2, 2, 5, 9)\n",
      "(2, 3, 4, 6) == (2, 3, 4, 6)\n",
      "(2, 3, 4, 7) == (2, 3, 4, 7)\n",
      "(2, 3, 4, 8) == (2, 3, 4, 8)\n",
      "(2, 3, 4, 9) == (2, 3, 4, 9)\n",
      "(2, 3, 5, 6) == (2, 3, 5, 6)\n",
      "(2, 3, 5, 7) == (2, 3, 5, 7)\n",
      "(2, 3, 5, 8) == (2, 3, 5, 8)\n",
      "(2, 3, 5, 9) == (2, 3, 5, 9)\n"
     ]
    }
   ],
   "source": [
    "a, b, c, d = [1, 2], [1, 2, 3], [4, 5], [6, 7, 8, 9]\n",
    "\n",
    "expected_result = list(itertools.product(*[a,b,c,d]))\n",
    "\n",
    "all_nth_combinations = [nth_combination(n, [a,b,c,d]) for n in range(1, (2*3*2*4)+1)]\n",
    "all_nth_combinations.sort()\n",
    "\n",
    "for a,b in zip(expected_result, all_nth_combinations):\n",
    "    sign = \"==\" if a==b else \"!=\"\n",
    "    print(a, sign ,b)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "pycharm-d2eb47b4",
   "language": "python",
   "display_name": "PyCharm (github-pages)"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}