},
{
"cell_type": "code",
- "execution_count": 7,
+ "execution_count": 2,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 26,
+ "execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
- "data": {
- "text/plain": [
- "654"
- ]
- },
- "execution_count": 26,
- "metadata": {},
- "output_type": "execute_result"
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "100 loops, best of 3: 14.2 ms per loop\n"
+ ]
}
],
"source": [
+ "%%timeit\n",
"partials = []\n",
"for c in containers:\n",
" new_partials = []\n",
" for p in partials:\n",
" if sum(p) + c <= target:\n",
" new_partials += [[c] + p]\n",
- " new_partials += [p]\n",
" if c <= target:\n",
" new_partials += [[c]]\n",
- " partials = new_partials\n",
+ " partials += new_partials\n",
+ "solutions = list(filter(lambda p: sum(p) == target, partials))\n",
+ "len(solutions)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loops, best of 3: 753 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "partials = []\n",
+ "for c in containers:\n",
+ " new_partials = []\n",
+ " for p in partials:\n",
+ " if sum(p) + c <= target:\n",
+ " partials = [[c] + p] + partials\n",
+ " if c <= target:\n",
+ " partials = [[c]] + partials\n",
"solutions = list(filter(lambda p: sum(p) == target, partials))\n",
"len(solutions)"
]
},
{
"cell_type": "code",
- "execution_count": 66,
+ "execution_count": 9,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 63,
+ "execution_count": 10,
"metadata": {
"collapsed": false
},
},
{
"cell_type": "code",
- "execution_count": 64,
+ "execution_count": 11,
"metadata": {
"collapsed": false
},
"[True, False, False, False, True, True, False, False]"
]
},
- "execution_count": 64,
+ "execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 59,
+ "execution_count": 12,
"metadata": {
"collapsed": false
},
"[]"
]
},
- "execution_count": 59,
+ "execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
- "import itertools\n",
"valids = []\n",
"c_small = containers[:5]\n",
"for i in range(2**len(c_small)):\n",
},
{
"cell_type": "code",
- "execution_count": 65,
+ "execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
- "data": {
- "text/plain": [
- "654"
- ]
- },
- "execution_count": 65,
- "metadata": {},
- "output_type": "execute_result"
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loops, best of 3: 4.41 s per loop\n"
+ ]
}
],
"source": [
- "import itertools\n",
+ "%%timeit\n",
"valids = []\n",
"for i in range(2**len(containers)):\n",
" mask = int_to_bitstring(i, len(containers))\n",