2011年12月27日

【数学】順列出力関数の作成(1)〜再帰関数で汎用化

 このBlogの「たけしのコマ大数学科」のお題に対するPythonコードは原則発想が簡単で、あまり試行錯誤せずに素早く完成出来る仕様とする様に心掛けている。従って、これ迄盛んに数字や記号の組合せから作る順列は、その並びの桁数分のループを入れ子で直書きし、順列としては不要な要素重複分もループさせる形式を採らせて頂いた次第だ。そちらの方が実践的だし、何といっても皆様にとって解読し易いからである。
 でも、ここの所似た様な順列問題を続けてコーディングしていて、処理時間の待ちが発生すると、心に引っかっていた「再帰関数で汎用化」という想いが大きくなってしまった。

 ということで結果として作成には結構な時間を要したものの、CPU負荷が少ないかなり軽快なまだ自己満足の域を出ないレベルの試作品ながらも、順列リストの生成の汎用関数を作成出来たので、ここに掲載させて頂く。実用上の課題があるバージョンではあるが一度に全ての実装をすると他人には判り辛いものなので、今回はそのままの掲載とさせて頂いた。

               ~/junretsu_pre2.py


#!/usr/bin/python2.6
# -*- coding: utf-8 -*-
U"""
順列リスト作成関数(試作1号)
※ 9要素迄なら実用になるが、10桁では仮想メモリー領域を大量に使う為、実用にならない。
items: 順列要素のリスト
keta : 桁数(順列要素数以下である必要があります。)
kumis: 追記する先頭要素

"""

__author__ = "Mire in Japan"
__version__ = '0.0.1a'
__copyright__ = 'Copyright (c) 2011-12-26 Mire'
__license__ = 'GPL'
__url__ = 'http://pythonlife.up.seesaa.net/article/242842146.html '

def junretsu(items=[1, 2, 3], keta=3, kumis=[]):
"""
順列リスト出力関数本体
items: 順列要素のリスト
keta : 桁数(順列要素数以下である必要があります。)
kumis: 追記する先頭要素
"""

history = u"""
0.0.1 2011-12-26 初版
0.0.1a 2011-12-28 コメント附記, clean up
"""

from time import time, localtime
st = time() #処理開始時刻をstに代入
news = [] #新たな順列リストを空リストに初期化
if kumis==[]: #初回時は
for i in items: # 全itemsについて
news.append([i]) # 要素を一つずつ含むリストを追加して行く
else: #それ以外は
for kumi in kumis: # 生成済の上位桁数の全順列について
loop=items[:] # 全itemsをloopにコピーし
for item in kumi: # 配置済の全要素について
loop.remove(item) # loopから取り除いた上で
for i in loop: # 残りの未配置の全要素について
k = kumi[:] # kに順列をコピーした上で
k.append(i) # そのリストkに要素を一つずつ追加後
news.append(k) # 新たな順列リストに追加して行く
kumis = news #処理完了に付、生成済順列リストを新たな順列リストに置換
et = time() #処理終了時刻をetに代入
print '%2d:%15d [%12.3f sec]' % (keta #処理桁位置と
, len(news) #全生成順列の数に
, et - st) #処理時間をコンソール表示

if keta<=1: #既に再帰終了条件最終桁に達していたら
return kumis #全順列リストを返し再帰終了する
else: #未処理桁があるなら
return junretsu(items=items #同じitemsに対し、
, keta=keta-1 #桁数を一つ減らし
, kumis=kumis) #生成済の前桁迄の順列リストを指定して自関数に再帰

#### コードの実行開始 ####
if __name__ == "__main__":
items = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'] #順列生成用要素をリスト指定し
keta = len(items) #全要素数を順列桁数として
junretsus = junretsu(items=items, keta=keta) #順列出力関数を実行し順列リストをを取得
for jun in junretsus: #全順列を一つずつコンソール出力
print '[%s, %s, %s, %s, %s, %s, %s, %s, %s]' % tuple(jun)
(※2011-12-28:コード説明を兼ねてコメント附記)
 ご覧の通り、関数junretsu()には、汎用的に並べる要素をリストで、並べる数を数字で与える様にしている。また汎用化する為に、その処理は1つずつ処理した結果を自関数に渡し並べる数迄繰返しその結果を返す仕組みとした。いわゆるNEST入れ子構造の再帰処理関数としての定義法をとった。この様にすることで指定回数だけNESTし生成出来た値をまとめてリストで返すことが出来る様に出来たしCPU負荷面の課題はほぼ解消出来た。しかし、再帰関数の処理結果をリスト実体生成としたことから、一桁増えるとn+1倍のメモリー消費を招き実用的なのは以下の実行結果通り9要素9桁迄となる。このソースコードには予め関数の各桁の処理にかかった所要時間と発生順列の数を処理中に書出す様にした。それで、下の例では計6秒未満で全順列のリストを作成出来たということがお判り頂けることと思う。




[mire@localhost ~]$ python kumiawase.py
9: 9 [ 0.000 sec]
8: 72 [ 0.000 sec]
7: 504 [ 0.001 sec]
6: 3024 [ 0.007 sec]
5: 15120 [ 0.022 sec]
4: 60480 [ 0.107 sec]
3: 181440 [ 0.490 sec]
2: 362880 [ 1.782 sec]
1: 362880 [ 2.953 sec]
[A, B, C, D, E, F, G, H, I]
[A, B, C, D, E, F, G, I, H]
[A, B, C, D, E, F, H, G, I]
[A, B, C, D, E, F, H, I, G]
[A, B, C, D, E, F, I, G, H]
[A, B, C, D, E, F, I, H, G]
[A, B, C, D, E, G, F, H, I]
[A, B, C, D, E, G, F, I, H]
[A, B, C, D, E, G, H, F, I]
[A, B, C, D, E, G, H, I, F]
[A, B, C, D, E, G, I, F, H]
[A, B, C, D, E, G, I, H, F]
[A, B, C, D, E, H, F, G, I]
[A, B, C, D, E, H, F, I, G]
[A, B, C, D, E, H, G, F, I]
[A, B, C, D, E, H, G, I, F]
[A, B, C, D, E, H, I, F, G]
[A, B, C, D, E, H, I, G, F]
[A, B, C, D, E, I, F, G, H]
[A, B, C, D, E, I, F, H, G]
[A, B, C, D, E, I, G, F, H]
[A, B, C, D, E, I, G, H, F]
[A, B, C, D, E, I, H, F, G]
[A, B, C, D, E, I, H, G, F]
[A, B, C, D, F, E, G, H, I]
[A, B, C, D, F, E, G, I, H]
[A, B, C, D, F, E, H, G, I]
[A, B, C, D, F, E, H, I, G]
[A, B, C, D, F, E, I, G, H]
[A, B, C, D, F, E, I, H, G]
[A, B, C, D, F, G, E, H, I]
<中略>
[I, H, G, F, D, E, C, B, A]
[I, H, G, F, E, A, B, C, D]
[I, H, G, F, E, A, B, D, C]
[I, H, G, F, E, A, C, B, D]
[I, H, G, F, E, A, C, D, B]
[I, H, G, F, E, A, D, B, C]
[I, H, G, F, E, A, D, C, B]
[I, H, G, F, E, B, A, C, D]
[I, H, G, F, E, B, A, D, C]
[I, H, G, F, E, B, C, A, D]
[I, H, G, F, E, B, C, D, A]
[I, H, G, F, E, B, D, A, C]
[I, H, G, F, E, B, D, C, A]
[I, H, G, F, E, C, A, B, D]
[I, H, G, F, E, C, A, D, B]
[I, H, G, F, E, C, B, A, D]
[I, H, G, F, E, C, B, D, A]
[I, H, G, F, E, C, D, A, B]
[I, H, G, F, E, C, D, B, A]
[I, H, G, F, E, D, A, B, C]
[I, H, G, F, E, D, A, C, B]
[I, H, G, F, E, D, B, A, C]
[I, H, G, F, E, D, B, C, A]
[I, H, G, F, E, D, C, A, B]
[I, H, G, F, E, D, C, B, A]
[mire@localhost ~]$

 でも、10要素10桁の全順列になると「10! = 3628800」個のリストに大量の記憶領域が必要なことからLinuxのSWAPメモリーを利用する様になり「disk sleep」状態を発生させてしまう課題を抱えてしまう。その場合、実行時間はメモリーの居所次第の様で運が良ければ、以下の様に12時間以内に処理出来ることがあった(CPU: INTEL DUAL CORE2 2GHz / MEMORY: 2G Bite)。



[mire@localhost ~]$ python kumiawase_by_bit.py
10: 10 [ 0.000 sec]
9: 90 [ 0.000 sec]
8: 720 [ 0.001 sec]
7: 5040 [ 0.008 sec]
6: 30240 [ 0.038 sec]
5: 151200 [ 0.263 sec]
4: 604800 [ 1.725 sec]
3: 1814400 [ 12.950 sec]
2: 3628800 [ 61.495 sec]
1: 3628800 [ 42008.382 sec]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
[0, 1, 2, 3, 4, 5, 6, 8, 9, 7]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
<後略>

 原因は、この関数が組合せリストの実体を出力させる仕様の為、その格納メモリー分のメモリー消費を招いてしまうからである。小手先の解決策としては先ず変更しないリストをタプル化することが考えられるので、次稿ではその修正コードを掲載したいと思う。また、ある程度数をこなすと感覚的にも判るものと思うが、組合せは、その要素の名前に関係なく一定の規則により成り立つので、文字一つを要素として内部的に扱う様にすれば文字種数が上限となる制限を加わるもののより省メモリーなものとすることも可能である。さらに、既にCPU速度の課題は解決出来る目処はあるので、イテレータ関数化や組合せ条件による自動コード生成、あるいは予め組合せファイルを作成し利用する等対応方法は色々と考えられる。これらも順次試みようと思っている。

 一般に数学問題程度なら、あまりコンピュータのCPU速度やメモリー容量の問題を考える必要もないが、例えば52枚のトランプをよく切ってから並べた時のあらゆる組合せについて処理したい等課題となると一般のコンピュータ言語の整数値の限界を早々と越えてしまい処理不能となってしまう。幸いPythonでは標準で制限のない長整数も扱えるので気にせずに挑戦して行くつもりでいる。
posted by Mire at 03:30 | Comment(0) | TrackBack(0) | Pythonプログラミング | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/242842146
※ブログオーナーが承認したトラックバックのみ表示されます。

この記事へのトラックバック
月額見放題1,000円開始キャンペーンバナー(画像ありver)
紺碧の艦隊 ルパン三世 GREAT CHASE クリックプロモーション
<< 2013年01月 >>
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
カテゴリ
タグクラウド
ファン
利用中のオープンソース
最近のコメント
最近の記事
過去ログ
QRコード
レガシーなアプリはいかが?
Dell 法人のお客様ページ
  • 【法人様向け】デル、お得なキャンペーン情報
  • 法人のお客様向け ストレージソリューション
  • 法人のお客様向け ネットワークソリューション
  • 【SOHO法人様向け】デル・オンライン広告限定ページ
  • デル-個人のお客様ページ
  • 【個人のお客様向け】デル・オンライン広告限定ページ
  • オンライン広告限定キャンペーンページ
  • ソフトウェア&周辺機器 パソコン工房
    ツートップインターネットショップ(twotop.co.jp) マウスコンピューター/G-Tune
  • ×

    この広告は1年以上新しい記事の投稿がないブログに表示されております。