「トポロジカルソートについて勉強する前に一人で考えてみた」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
ページ製作者
兵庫県加古川市加古川町南備後の森元さんからは小学校の算数までしかできないと言われている堀江伸一さんのページ。
学校の勉強でといっても私はほとんど寝たきりで学校に行ってないのですが。
何かについて授業を受ける前にそれについて自分で考えてみようという学習方法があるそうです。
自分で考えた後で先生に正しい考え方を教えてもらうことで学習効果があがるという話だそうです。
この学習効果を期待してトポロジカルソートについてちょっと考えてみました。
まず
数字列
Ans=014714243,,,,
という有限の長さの0～9までの数字で構成された不明な数字列がある。
これから離れた2桁を取った組み合わせのデータPが与えられた場合、これは答えが一意に定まらない。
違ったAnsが同じPを導き出すから。
今の疑問
では離れた3桁を順序をたがえず取った場合は特定できるのか？
何桁なら特定できるか？
2桁取る場合でも答えが一意に特定できる場合は計算が可能かも？
先頭桁はPから、12と21や２２と２２のように逆順にしたものを1対１で削除してこれをP1とし。
残ったP1の
0A Aは一ケタの数字
1A
、、、
9A
と0～9に固定した時P1の要素とマッチできるものが一番多い数字が先頭桁になるような気はしました。
以下は失敗作の発想。
数字列
Ans=014714243,,,,
という0～9までの数字で構成された不明な数がある。
Ansの左から右へ2桁数字を選んだ結果がデータとして与えられる。
14
17
24
のようにである。
Ansを一意かつ最小桁数で推測できるだけのデータが与えられるとき、どのような考え方を行えばよいか？
まず与えられたデータを全部繋げた文字列を考える。
そして文字列中で各数字の出てきた数を数え点に置き換える。
0が3個出てきたら点(0,1),(0,2),(0,3)で表現される点と考え他の数字も同様に点に置き換える。
例えば4が2個なら(4,1),(4,2)で区別される点を考える。
04
というデータが出てきたら
(0,1),(0,2),(0,3)から(4,1),(4,2)への全組み合わせで矢印を結ぶ。
これを全部のデータで繰り返す。
次に0～9の数字の(0,1),(1,1),,,(9,1)にポインタを合わせる。
このうち一つも矢印が入ってない点が左端の数字の点となる。
この点から出る矢印を全部消し、例えば消した点が(0,1)なら今度は(0,2)へポインタを進める。
ないならそのポインタを消す。
今度は(0,2)、(1,1),(2,1),,,(9,1)のうち矢印の入ってないものを選び同様の操作を続けて数字を確定していく。
そして一ケタ確定するたびに全てのデータと照合し、全てのデータと矛盾がないことが判明したらその数字列が条件を満たす最小桁数の答えとなる。
と考えたが現実はどうだろうか？
ページ製作者
兵庫県加古川市加古川町南備後の森元さんからは小学校の算数までしかできないと言われている堀江伸一さんのページ。
学校の勉強でといっても私はほとんど寝たきりで学校に行ってないのですが。
何かについて授業を受ける前にそれについて自分で考えてみようという学習方法があるそうです。
自分で考えた後で先生に正しい考え方を教えてもらうことで学習効果があがるという話だそうです。
この学習効果を期待してトポロジカルソートについてちょっと考えてみました。
まず
数字列
Ans=014714243,,,,
という有限の長さの0～9までの数字で構成された不明な数字列がある。
これから離れた2桁を取った組み合わせのデータPが与えられた場合、これは答えが一意に定まらない。
違ったAnsが同じPを導き出すから。
今の疑問
では離れた3桁を順序をたがえず取った場合は特定できるのか？
何桁なら特定できるか？
2桁取る場合でも答えが一意に特定できる場合は計算が可能かも？
先頭桁はPから、12と21や２２と２２のように逆順にしたものを1対１で削除してこれをP1とし。
残ったP1の
0A Aは一ケタの数字
1A
、、、
9A
と0～9に固定した時P1の要素とマッチできるものが一番多い数字が先頭桁になるような気はしました。
何故か深夜3時誰もYahoo知恵袋をやってないはずの時間にこの質問を投稿したら３分もたたないうちに31アクセスいったのが怖かった。
まるで投稿内容を監視されているかのようなアクセス数でした、、、
以下は失敗作の発想。
数字列
Ans=014714243,,,,
という0～9までの数字で構成された不明な数がある。
Ansの左から右へ2桁数字を選んだ結果がデータとして与えられる。
14
17
24
のようにである。
Ansを一意かつ最小桁数で推測できるだけのデータが与えられるとき、どのような考え方を行えばよいか？
まず与えられたデータを全部繋げた文字列を考える。
そして文字列中で各数字の出てきた数を数え点に置き換える。
0が3個出てきたら点(0,1),(0,2),(0,3)で表現される点と考え他の数字も同様に点に置き換える。
例えば4が2個なら(4,1),(4,2)で区別される点を考える。
04
というデータが出てきたら
(0,1),(0,2),(0,3)から(4,1),(4,2)への全組み合わせで矢印を結ぶ。
これを全部のデータで繰り返す。
次に0～9の数字の(0,1),(1,1),,,(9,1)にポインタを合わせる。
このうち一つも矢印が入ってない点が左端の数字の点となる。
この点から出る矢印を全部消し、例えば消した点が(0,1)なら今度は(0,2)へポインタを進める。
ないならそのポインタを消す。
今度は(0,2)、(1,1),(2,1),,,(9,1)のうち矢印の入ってないものを選び同様の操作を続けて数字を確定していく。
そして一ケタ確定するたびに全てのデータと照合し、全てのデータと矛盾がないことが判明したらその数字列が条件を満たす最小桁数の答えとなる。
と考えたが現実はどうだろうか？
