enumerate.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# グラフ探索（深さ優先探索）を元にした列挙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 部分集合の列挙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "与えられた集合の部分集合は非常に多い．\n",
    "例えば，要素数が$n$の集合の部分集合は全部で$2^n$個になる．\n",
    "\n",
    "しかし，$n$があまり多くない場合には，部分集合の列挙が役に立つ場合も多い．\n",
    "以下に，部分集合を列挙するPythonコードを関数enumerate_all_subsetsとして定義する．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def subset_from_vector(v, a_set):\n",
    "    '''特性列と集合を元に，部分集合を返す関数．\n",
    "    '''\n",
    "    \n",
    "    if len(v) != len(a_set):\n",
    "        return []\n",
    "    subset = []\n",
    "    for vi, element in zip(v, a_set):\n",
    "        if vi == 1:\n",
    "            subset += [element]\n",
    "    return subset\n",
    "    \n",
    "\n",
    "def enumerate_all_subsets(a_set=['a', 'b', 'c']):\n",
    "    '''部分集合を列挙する関数．\n",
    "    深さ優先探索を元に部分集合の特性列（characteristic sequence）を列挙する．\n",
    "    列挙された部分集合をまとめて最後に返す．\n",
    "    '''\n",
    "    \n",
    "    subsets = [] # 部分集合を保存するためのリスト\n",
    "    S = [[]] # スタック\n",
    "    while len(S) > 0: # スタックが空でない限り以下を繰り返す．\n",
    "        v = S.pop() # スタックから0-1列を1つ取り出す．\n",
    "        if len(v) == len(a_set): # 0-1列が集合の要素数と同じ長さならば，\n",
    "            subsets += [subset_from_vector(v, a_set)] # その0-1ベクトルが特性列であると見なして，部分集合を作り，保存する．\n",
    "        else: # 0-1列が集合の要素数よりも短いならば，\n",
    "            S += [v + [0]] # それに0を追加した列をスタックに入れる．\n",
    "            S += [v + [1]] # それに1を追加した列もスタックに入れる．\n",
    "    return subsets # 最後にまとめて，全ての部分集合を返す．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3つの要素からなる集合をenumerate_all_subsetsに与えてみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['a', 'b', 'c'], ['a', 'b'], ['a', 'c'], ['a'], ['b', 'c'], ['b'], ['c'], []]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enumerate_all_subsets(['a', 'b', 'c'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "確かに列挙できているようだ．\n",
    "\n",
    "この例では，列挙したものを最後にまとめて返している．\n",
    "しかし，多くの場合では，それぞれの部分集合が出来た時点で何らかの処理を施す方が良い．\n",
    "\n",
    "また，部分集合をすべて必要とはせず，「何らかの条件を満たす」部分集合だけを欲しい場合も多い．\n",
    "そのような場合には上記のコードを適切にカスタマイズする能力が要求される．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 順列の列挙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$n$個の要素を並べるやり方は$n!$通りある．\n",
    "\n",
    "しかし，$n$があまり多くない場合には，順列の列挙が役に立つ場合も多い．\n",
    "以下に，順列を列挙するPythonコードを関数enumerate_all_permutationsとして定義する．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def enumerate_all_permutations(sequence=['a', 'b', 'c']):\n",
    "    '''順列を列挙する関数．\n",
    "    深さ優先探索探索を元に順列を列挙する．\n",
    "    '''\n",
    "    \n",
    "    permutations = [] # 順列を保存するためのリスト\n",
    "    S = [([], sequence)] # 「順列の部分列」と「部分列で使われていない残り」の組をスタックに保存する．\n",
    "    while len(S) > 0: # スタックが空でない限り以下を繰り返す．\n",
    "        subsequence, remaining = S.pop() # スタックから（「部分列」，「残り」）を1つ取り出す．\n",
    "        if len(remaining) == 0: # 「部分列で使われていない残り」が空ならば，部分列は順列になっているはずなので，\n",
    "            permutations += [subsequence] # その部分列を順列に加える．\n",
    "        else: # 「部分列で使われていない残り」があるならば\n",
    "            for r in remaining: # その残りのそれぞれに関して，\n",
    "                remaining_copy = remaining[:] \n",
    "                remaining_copy.remove(r) # 残りを1つ取り除いて，\n",
    "                S += [(subsequence + [r], remaining_copy)] # それを部分列に追加した列と残りをスタックに入れる．\n",
    "    return permutations # 最後にまとめて，全ての部分集合を返す．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['c', 'b', 'a'],\n",
       " ['c', 'a', 'b'],\n",
       " ['b', 'c', 'a'],\n",
       " ['b', 'a', 'c'],\n",
       " ['a', 'c', 'b'],\n",
       " ['a', 'b', 'c']]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enumerate_all_permutations(['a', 'b', 'c'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "確かに列挙できているようだ．\n",
    "\n",
    "この例では，列挙したものを最後にまとめて返している．\n",
    "しかし，多くの場合では，それぞれの順列が出来た時点で何らかの処理を施す方が良い．\n",
    "\n",
    "実はPythonの標準モジュールであるitertoolsには順列を列挙してくれる関数が用意されている．\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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}