組み合わせ爆発の凄さ
私（自分）の好きなプログラミング言語で理解してもらおうと言語別の索引をつけてみました。私はプログラムを自分で書き換えて試さないと理論を理解できない傾向にあります。いろいろ書き換えてみようと思っています。たぶんpython。
『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！
『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！
https://www.youtube.com/watch?v=Q4gTV4r0zRs
同じところを 2度通らない経路の数を数えるアルゴリズムについて 川原 純 湊 真一 JETRO 湊離散構造処理系プロジェクト/北海道大学 情報科学研究科
http://www-erato.ist.hokudai.ac.jp/docs/img/main3.pdf
「フカシギの数え方」― 組合せ爆発に立ち向かう 最先端アルゴリズム技術 湊 真一 北海道大学 / JST ERATO
https://www.nii.ac.jp/userimg/openhouse/2013/lec_minato.pdf
フカシギおねえさん問題の高速計算アルゴリズム 岩下 洋哲 JST ERATO 湊離散構造処理系プロジェクト 2013/7/26
http://www.edu.kobe-u.ac.jp/istc-tamlab/cspsat/pdf-open/cspsat2_mtg203_iwashita.pdf
メディアラボ第11期展示「フカシギの数え方」展示解説
https://www.youtube.com/watch?v=TcjSu3_LMKY
「フカシギの数え方」 同じところを2度通らない道順の数
https://www.youtube.com/watch?v=ge8vy4tc_kQ
メディアラボ第11期展示「フカシギの数え方」インタビュー
https://www.youtube.com/watch?v=SfC0W1TQcVg
日本科学未来館第11期メディアラボ展示「フカシギの数え方」
http://www-erato.ist.hokudai.ac.jp/html/php/sub_html.php?id=19
フロンティア法:BDD/ZDDを用いた 高速なグラフ列挙索引化アルゴリズム
湊 真一 北海道大学 情報科学研究科 / JST ERATO 2012年8月9日
https://www.ieice.org/~netsci/wp-content/uploads/2012/08/NetSci201208_Minato.pdf
同じ所を２度通らない道順の数
http://shogo82148.github.io/letscount/
おねぇさぁぁぁぁぁん！ 日本科学未来館のアニメに狂気が宿っていると話題に
https://nlab.itmedia.co.jp/nl/articles/1209/11/news104.html
おねえさんのコンピュータを作ってみた
https://shogo82148.github.io/blog/2012/09/22/letscount/
vim
Vimおねえさんといっしょ！みんなで数えてみよう！: pla.log
http://pla.asablo.jp/blog/2012/09/30/6588034
perl
「フカシギの数え方」をPerlで解く
http://hiratara.hatenadiary.jp/entry/20120916/1347796826
VB(Visual Basic)
僕も組み合わせ爆発の凄さをみんなに伝えたくなりました^0^！
https://www.nicovideo.jp/watch/sm18920750
https://box.yahoo.co.jp/guest/viewer?sid=box-l-dohryx5swstii3sh27xxkh535i-1001&uniqid=476500bf-e1ff-4810-8ee6-0777e11a4c92&viewtype=detail
PHP
『フカシギの数え方』 おねえさんといっしょ！ PHPで数えてみよう！
https://sisidovski.hatenablog.com/entry/2012/09/13/023947
https://github.com/sisidovski/CombinationalExplosion
java
2012-10-19 おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった
https://nowokay.hatenablog.com/entry/20121019/1350607290
python
ZDDを自作して数え上げお姉さんを救ってみた
https://qiita.com/cabernet_rock/items/01c48dd06178ba0768f9
C++ + python
おねえさんのコンピュータを作ってみた
2012年9月15日土曜日「フカシギの数え方」の問題を解いてみた
http://handasse.blogspot.com/2012/09/blog-post.html
Graphillion
Graphillion: 数え上げおねえさんを救え / Don't count naively
https://www.youtube.com/watch?v=R3Hp9k876Kk
「フカシギの数え方」から広がる世界 ~離散構造処理の現在と今後の展望~
湊 真一 北海道大学 大学院 情報科学研究科 教授
http://www.kecl.ntt.co.jp/openhouse/2014/talk/invite2/talk_minato.pdf
オープンハウス2013：基調講演「フカシギの数え方― 組合せ爆発に立ち向かう最先端アルゴリズム技術」湊真一
https://www.youtube.com/watch?v=8xqEBQc1nTo
サイエンティスト・トーク「フカシギの不思議」
https://www.youtube.com/watch?v=QVVHEZCdY_k
参考資料(reference)
graphillionを使ってみた
https://qiita.com/cabernet_rock/items/50f955afc16287244154
dockerで
docker run -v /tmp/work:/tmp/work -it kaizenjapan/zdd /bin/bash
/tmp/workはdockerを起動する前に存在するフォルダ。:/tmp/workは、docker上にできるが、docker終了後はdocker hubに登録してもdocker上には残らないので、docker hubに登録する場合は、必要なデータは/home/pythonのような入れ物を作って保存しておくと良い。
ソフトが導入済みの状態。プログラムは/home/pythonに入れてある。
プログラムは下記のようにprintを加えて出力するように。
# https://qiita.com/cabernet_rock/items/50f955afc16287244154
# https://qiita.com/kaizen_nagoya/items/f309b0c2bb015bbc71c3
# https://qiita.com/kaizen_nagoya/items/3a8d89f095489b6e1f56
# https://qiita.com/kaizen_nagoya/items/819f10124ec453b7ef27
# 必要なモジュールのインポート
from graphillion import GraphSet
import graphillion.tutorial as tl
import time # 計算時間を調べる。
# グリッドのサイズを指定
universe = tl.grid(2, 2)
GraphSet.set_universe(universe)
tl.draw(universe)
start = 1 # スタート位置
goal = 9 # ゴールの位置
paths = GraphSet.paths(start, goal)
print (len(paths))
#
key = 4 # 1箇所目
treasure = 2 # 2箇所目
paths_to_key = GraphSet.paths(start, key).excluding(treasure)
treasure_paths = paths.including(paths_to_key).including(treasure)
print (len(treasure_paths))
#
universe = tl.grid(8, 8) # 9×9のグリッド
GraphSet.set_universe(universe)
start = 1
goal = 81
s = time.time() # 計算開始時刻
paths = GraphSet.paths(start, goal)
print (time.time() - s )# 計算時間
print (len(paths))
実行結果は
# python3 gra.py
12
2
0.25122714042663574
3266598486981642
9を12にしたらKilledで終わらなかった。10,11でもkilled.メモリを使い果たしているかも。
主記憶16GBだがdockerに割り当てが少ないかも。
dockerに12GBに割り当てて10で実行したら、１２時間たつがまだkilledにはなっていない。
docker 作成と登録
なお、上記docker hubへ登録したものは次のように作成した。
$ docker run -v /tmp/work:/tmp/work -it ubuntu /bin/bash
起動したら
# apt update;apt -y upgrade
# apt install -y python3 python3-pip vim wget curl sudo apt-utils
# pip3 insatll networks matplotlib graphillion
apt installでvim以降は個人的に利用するために入れたもの。
docker hub への登録は
$ docker commit 04b268b5a441 kaizenjapan/zdd
$ docker push kaizenjapan/zdd
04b268b5a441 の値は、docker psでもわかるが、コマンドプロンプトにも値が出てる。
関連資料(related document)
今日のpython error:ModuleNotFoundError: No module named
https://qiita.com/kaizen_nagoya/items/3a8d89f095489b6e1f56
今日のpython error: invalid keyword argument for this function
https://qiita.com/kaizen_nagoya/items/819f10124ec453b7ef27
後書き(post script)
この資料は、Knuthの著作に出てくる問題で、湊 真一 が考案したZDD方式をKnuthの著作の新版でも取り上げている題材です。
Knuthの名著"The Art of Computer Programming"(Vol.4, Fascicle 1, 2009年)において, 湊が考案したデータ構造「ZDD」 が項目として詳しく掲載された（日本人初）
日本のプログラマが、この題材をよりよくプログラミングすることにより、技術の伝搬速度を高めようとするための試みです。
ありとあらゆる言語で記述してみて、分かりやすく、応用しやすい記述を模索します。
関連資料
' @kazuo_reve 私が効果を確認した「小川メソッド」
https://qiita.com/kazuo_reve/items/a3ea1d9171deeccc04da
' @kazuo_reve 新人の方によく展開している有益な情報
https://qiita.com/kazuo_reve/items/d1a3f0ee48e24bba38f1
' @kazuo_reve Vモデルについて勘違いしていたと思ったこと
https://qiita.com/kazuo_reve/items/46fddb094563bd9b2e1e
Engineering Festa 2024前に必読記事一覧
登壇直後版 色使い(JIS安全色) Qiita Engineer Festa 2023〜私しか得しないニッチな技術でLT〜 スライド編 0.15
https://qiita.com/kaizen_nagoya/items/f0d3070d839f4f735b2b
プログラマが知っていると良い「公序良俗」
https://qiita.com/kaizen_nagoya/items/9fe7c0dfac2fbd77a945
逆も真：社会人が最初に確かめるとよいこと。OSEK(69)、Ethernet(59)
https://qiita.com/kaizen_nagoya/items/39afe4a728a31b903ddc
統計の嘘。仮説（127）
https://qiita.com/kaizen_nagoya/items/63b48ecf258a3471c51b
自分の言葉だけで論理展開できるのが天才なら、文章の引用だけで論理展開できるのが秀才だ。仮説（136）
https://qiita.com/kaizen_nagoya/items/97cf07b9e24f860624dd
参考文献駆動執筆(references driven writing)・デンソークリエイト編
https://qiita.com/kaizen_nagoya/items/b27b3f58b8bf265a5cd1
「何を」よりも「誰を」。１０年後のために今見習いたい人たち
https://qiita.com/kaizen_nagoya/items/8045978b16eb49d572b2
Qiitaの記事に３段階または５段階で到達するための方法
https://qiita.com/kaizen_nagoya/items/6e9298296852325adc5e
出力(output)と呼ばないで。これは状態(state)です。
https://qiita.com/kaizen_nagoya/items/80b8b5913b2748867840
coding (101) 一覧を作成し始めた。omake:最近のQiitaで表示しない5つの事象
https://qiita.com/kaizen_nagoya/items/20667f09f19598aedb68
あなたは「勘違いまとめ」から、勘違いだと言っていることが勘違いだといくつ見つけられますか。人間の間違い(human error(125))の種類と対策
https://qiita.com/kaizen_nagoya/items/ae391b77fffb098b8fb4
プログラマの「プログラムが書ける」思い込みは強みだ。３つの理由。仮説（168）統計と確率(17) , OSEK(79)
https://qiita.com/kaizen_nagoya/items/bc5dd86e414de402ec29
出力(output)と呼ばないで。これは状態(state)です。
https://qiita.com/kaizen_nagoya/items/80b8b5913b2748867840
これからの情報伝達手段の在り方について考えてみよう。炎上と便乗。
https://qiita.com/kaizen_nagoya/items/71a09077ac195214f0db
ISO/IEC JTC1 SC7 Software and System Engineering
https://qiita.com/kaizen_nagoya/items/48b43f0f6976a078d907
アクセシビリティの知見を発信しよう！（再び）
https://qiita.com/kaizen_nagoya/items/03457eb9ee74105ee618
統計論及確率論輪講（再び）
https://qiita.com/kaizen_nagoya/items/590874ccfca988e85ea3
読者の心をグッと惹き寄せる7つの魔法
https://qiita.com/kaizen_nagoya/items/b1b5e89bd5c0a211d862
「@kazuo_reve 新人の方によく展開している有益な情報」確認一覧
https://qiita.com/kaizen_nagoya/items/b9380888d1e5a042646b
ソースコードで議論しよう。日本語で議論するの止めましょう（あるプログラミング技術の議論報告）
https://qiita.com/kaizen_nagoya/items/8b9811c80f3338c6c0b0
脳内コンパイラの3つの危険
https://qiita.com/kaizen_nagoya/items/7025cf2d7bd9f276e382
心理学の本を読むよりはコンパイラ書いた方がよくね。仮説（34）
https://qiita.com/kaizen_nagoya/items/fa715732cc148e48880e
NASAを超えるつもりがあれば読んでください。
https://qiita.com/kaizen_nagoya/items/e81669f9cb53109157f6
データサイエンティストの気づき!「勉強して仕事に役立てない人。大嫌い!!」『それ自分かも?』ってなった!!!
https://qiita.com/kaizen_nagoya/items/d85830d58d8dd7f71d07
「ぼくの好きな先生」「人がやらないことをやれ」プログラマになるまで。仮説（37）
https://qiita.com/kaizen_nagoya/items/53e4bded9fe5f724b3c4
なぜ経済学徒を辞め、計算機屋になったか（経済学部入学前・入学後・卒業後対応） 転職(1)
https://qiita.com/kaizen_nagoya/items/06335a1d24c099733f64
プログラミング言語教育のXYZ。 仮説（52）
https://qiita.com/kaizen_nagoya/items/1950c5810fb5c0b07be4
【24卒向け】9ヶ月後に年収１０００万円を目指す。二つの関門と三つの道。
https://qiita.com/kaizen_nagoya/items/fb5bff147193f726ad25
「【25卒向け】Qiita Career Meetup for STUDENT」予習の勧め
https://qiita.com/kaizen_nagoya/items/00eadb8a6e738cb6336f
大学入試不合格でも筆記試験のない大学に入って卒業できる。卒業しなくても博士になれる。
https://qiita.com/kaizen_nagoya/items/74adec99f396d64b5fd5
全世界の不登校の子供たち「博士論文」を書こう。世界子供博士論文遠隔実践中心 安全(99)
https://qiita.com/kaizen_nagoya/items/912d69032c012bcc84f2
小川メソッド 覚え（書きかけ）
https://qiita.com/kaizen_nagoya/items/3593d72eca551742df68
DoCAP（ドゥーキャップ）って何ですか？
https://qiita.com/kaizen_nagoya/items/47e0e6509ab792c43327
views 20,000越え自己記事一覧
https://qiita.com/kaizen_nagoya/items/58e8bd6450957cdecd81
Views１万越え、もうすぐ１万記事一覧 最近いいねをいただいた213記事
https://qiita.com/kaizen_nagoya/items/d2b805717a92459ce853
自己記事一覧
Qiitaで逆リンクを表示しなくなったような気がする。時々、スマフォで表示するとあらわっることがあり、完全に削除したのではなさそう。
４月以降、せっせとリンクリストを作り、統計を取って確率を説明しようとしている。
2025年２月末を目標にしている。
物理記事 上位100
https://qiita.com/kaizen_nagoya/items/66e90fe31fbe3facc6ff
量子(0) 計算機, 量子力学
https://qiita.com/kaizen_nagoya/items/1cd954cb0eed92879fd4
数学関連記事１００
https://qiita.com/kaizen_nagoya/items/d8dadb49a6397e854c6d
統計(0)一覧
https://qiita.com/kaizen_nagoya/items/80d3b221807e53e88aba
図(0) state, sequence and timing. UML and お絵描き
https://qiita.com/kaizen_nagoya/items/60440a882146aeee9e8f
品質一覧
https://qiita.com/kaizen_nagoya/items/2b99b8e9db6d94b2e971
言語・文学記事 １００
https://qiita.com/kaizen_nagoya/items/42d58d5ef7fb53c407d6
医工連携関連記事一覧
https://qiita.com/kaizen_nagoya/items/6ab51c12ba51bc260a82
自動車 記事 １００
https://qiita.com/kaizen_nagoya/items/f7f0b9ab36569ad409c5
通信記事１００
https://qiita.com/kaizen_nagoya/items/1d67de5e1cd207b05ef7
日本語（０）一欄
https://qiita.com/kaizen_nagoya/items/7498dcfa3a9ba7fd1e68
英語(0) 一覧
https://qiita.com/kaizen_nagoya/items/680e3f5cbf9430486c7d
転職(0)一覧
https://qiita.com/kaizen_nagoya/items/f77520d378d33451d6fe
仮説（0）一覧（目標100現在40）
https://qiita.com/kaizen_nagoya/items/f000506fe1837b3590df
音楽 一覧(0)
https://qiita.com/kaizen_nagoya/items/b6e5f42bbfe3bbe40f5d
「@kazuo_reve 新人の方によく展開している有益な情報」確認一覧
https://qiita.com/kaizen_nagoya/items/b9380888d1e5a042646b
Qiita(0)Qiita関連記事一覧（自分）
https://qiita.com/kaizen_nagoya/items/58db5fbf036b28e9dfa6
鉄道（０）鉄道のシステム考察はてっちゃんがてつだってくれる
https://qiita.com/kaizen_nagoya/items/26bda595f341a27901a0
安全（0）安全工学シンポジウムに向けて: 21
https://qiita.com/kaizen_nagoya/items/c5d78f3def8195cb2409
一覧の一覧( The directory of directories of mine.) Qiita(100)
https://qiita.com/kaizen_nagoya/items/7eb0e006543886138f39
Ethernet 記事一覧 Ethernet(0)
https://qiita.com/kaizen_nagoya/items/88d35e99f74aefc98794
Wireshark 一覧 wireshark(0)、Ethernet(48)
https://qiita.com/kaizen_nagoya/items/fbed841f61875c4731d0
線網（Wi-Fi）空中線(antenna)(0) 記事一覧(118/300目標)
https://qiita.com/kaizen_nagoya/items/5e5464ac2b24bd4cd001
OSEK OS設計の基礎 OSEK(100)
https://qiita.com/kaizen_nagoya/items/7528a22a14242d2d58a3
Error一覧 error(0)
https://qiita.com/kaizen_nagoya/items/48b6cbc8d68eae2c42b8
++ Support(0)
https://qiita.com/kaizen_nagoya/items/8720d26f762369a80514
Coding(0) Rules, C, Secure, MISRA and so on
https://qiita.com/kaizen_nagoya/items/400725644a8a0e90fbb0
coding (101) 一覧を作成し始めた。omake:最近のQiitaで表示しない5つの事象
https://qiita.com/kaizen_nagoya/items/20667f09f19598aedb68
プログラマによる、プログラマのための、統計(0)と確率のプログラミングとその後
https://qiita.com/kaizen_nagoya/items/6e9897eb641268766909
なぜdockerで機械学習するか 書籍・ソース一覧作成中 (目標100)
https://qiita.com/kaizen_nagoya/items/ddd12477544bf5ba85e2
言語処理100本ノックをdockerで。python覚えるのに最適。:10+12
https://qiita.com/kaizen_nagoya/items/7e7eb7c543e0c18438c4
プログラムちょい替え（0）一覧:4件
https://qiita.com/kaizen_nagoya/items/296d87ef4bfd516bc394
Python(0)記事をまとめたい。
https://qiita.com/kaizen_nagoya/items/088c57d70ab6904ebb53
官公庁・学校・公的団体（NPOを含む）システムの課題、官（０）
https://qiita.com/kaizen_nagoya/items/04ee6eaf7ec13d3af4c3
「はじめての」シリーズ ベクタージャパン
https://qiita.com/kaizen_nagoya/items/2e41634f6e21a3cf74eb
AUTOSAR(0)Qiita記事一覧, OSEK(75)
https://qiita.com/kaizen_nagoya/items/89c07961b59a8754c869
プログラマが知っていると良い「公序良俗」
https://qiita.com/kaizen_nagoya/items/9fe7c0dfac2fbd77a945
LaTeX(0) 一覧
https://qiita.com/kaizen_nagoya/items/e3f7dafacab58c499792
自動制御、制御工学一覧（０）
https://qiita.com/kaizen_nagoya/items/7767a4e19a6ae1479e6b
Rust(0) 一覧
https://qiita.com/kaizen_nagoya/items/5e8bb080ba6ca0281927
100以上いいねをいただいた記事16選
https://qiita.com/kaizen_nagoya/items/f8d958d9084ffbd15d2a
小川清最終講義、最終講義（再）計画, Ethernet(100) 英語(100) 安全(100)
https://qiita.com/kaizen_nagoya/items/e2df642e3951e35e6a53
＜この記事は個人の過去の経験に基づく個人の感想です。現在所属する組織、業務とは関係がありません。＞
This article is an individual impression based on my individual experience. It has nothing to do with the organization or business to which I currently belong.
文書履歴(document history)
ver. 0.01 初稿 20240728
最後までおよみいただきありがとうございました。
いいね 💚、フォローをお願いします。
Thank you very much for reading to the last sentence.
Please press the like icon 💚 and follow me for your happy life.
文書履歴(document history)
ver. 0.01 初稿 20200121 午前
ver. 0.02 プログラム追記 20200121 昼
ver. 0.03 docker登録 20200121 午後
ver. 0.04 Knuth追記 20200122 午前
ver. 0.05 The Art of Computer Programming 表紙追記 20200122午後
ver. 0.06 ありがとう追記 20230505
https://b.hatena.ne.jp/guide/bbutton
最後までおよみいただきありがとうございました。
いいね 💚、フォローをお願いします。
Thank you very much for reading to the last sentence.
Please press the like icon 💚 and follow me for your happy life.