數組組合

數組組合.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 數組組合\n",
    "http://www.mobile01.com/topicdetail.php?f=511&t=4663504  \n",
    "http://www.mobile01.com/topicdetail.php?f=511&t=4308913  \n",
    "\n",
    "問題如下，現在有一個總合數 例如1999  \n",
    "然後有好幾組數字，例如 123、332、347、183、314、333、1000、342、......  \n",
    "可能是2組加起來=1999  \n",
    "也可能是3組，也可能是4組  \n",
    "但是不知道是幾組加的  \n",
    "總之，不超過5組  \n",
    "有辦法做出一個表格，可以打總合打進去，數組打進去  \n",
    "然後可以得到是那幾個數字組加起來是等於總合數的嗎？  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import itertools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 數組\n",
    "numbers = [123, 332, 347, 183, 314, 333, 1000, 342, 478, 592, 639, 733, 856, 934]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 目標總和\n",
    "targetedSum = 1999"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 最多幾個數字\n",
    "numberCount = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 組合\n",
    "combinations = np.array(list(itertools.combinations_with_replacement(sorted(numbers + [0]), numberCount)), dtype = np.int32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 求解組合\n",
    "solutions = combinations[combinations.sum(axis = 1) == targetedSum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11628 個排列組合之中，總和為 1999 的組合 共有 8 組: \n",
      "[[   0    0  332  733  934]\n",
      " [   0  332  333  478  856]\n",
      " [   0  332  342  592  733]\n",
      " [   0  333  333  333 1000]\n",
      " [ 123  314  314  314  934]\n",
      " [ 123  332  333  478  733]\n",
      " [ 183  314  314  332  856]\n",
      " [ 333  333  347  347  639]]\n"
     ]
    }
   ],
   "source": [
    "print('{0} 個排列組合之中，總和為 {1} 的組合 共有 {2} 組: \\n{3}'.format(len(combinations), targetedSum, len(solutions), solutions))"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}