![[PukiWiki]](http://unitylabo.s601.xrea.com/xoops/modules/xpwiki/image/pukiwiki.png "[PukiWiki]")
メモ7 のバックアップの現在との差分(No.2)
2: 2016-09-21 (水) 23:17:35 osinko  |
現: 2016-09-22 (木) 21:47:23 osinko |
||
|---|---|---|---|
| Line 2: | Line 2: | ||
| **問題を解く [#b956373c] | **問題を解く [#b956373c] | ||
| - | プログラムを組んで回転置換により元が書き変わらない置換を探した。 | + | ＜問題2＞ |
| - | 条件は\(X=\left\{ 1,2,3,4,5,6 \right\} ,Y=\left\{ A,B \right\} \)。出力結果が以下になる | + | 赤、青、黄のカラー被覆の銅線を6本束ねたケーブルで製品として異なるものは何種類作れるか？ |
| + | このケーブルは回転させたり、前後を逆（裏返し）にして利用できるものとする。（書籍「なっとくする群・環・体」 P51問2より） | ||
| + | |||
| + | 上記の様な問題を解く。まず順番に考えるために、より小さなスケールに問題を書き換えて考えることにする | ||
| + | 問題を以下のように書き換える | ||
| + | |||
| + | ＜問題2-a＞ | ||
| + | A、Bの２種の銅線を6本束ねたケーブルで製品として異なるものは何種類作れるか？ | ||
| + | このケーブルは回転させたり、前後を逆（裏返し）にして利用できるものとする | ||
| + | |||
| + | この問題を回転する置換群で考えてモデル化すると集合と置換関数は以下になる | ||
| + | |||
| + | \(X=\left\{ 1,2,3,4,5,6 \right\} \\ Y=\left\{ A,B \right\} \\ \iota =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{pmatrix}\\ \sigma =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 1 & 2 & 3 & 4 & 5 \end{pmatrix}\\ \tau =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix}\) | ||
| + | |||
| + | \(\iota\)が恒等置換（置換しない置換）。\(\sigma\)が回転を表す置換関数。\(\tau\)が反転、この問題の場合「裏返し」をシミュレーションする置換関数となる | ||
| + | これらの関数で群を作成するが、この時、\(\sigma\)と\(\tau\)の二項演算に対して演算の順番によって結果が変わることを考慮する必要がある | ||
| + | 実際にこれを確認すると以下のようになっていた | ||
| + | |||
| + | \(\begin{matrix} \iota \cdot \tau =\tau \cdot \iota \quad & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix} \\ \sigma \cdot \tau =\tau \cdot { \sigma }^{ 5 } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 4 & 3 & 2 & 1 & 6 \end{pmatrix} \\ { \sigma }^{ 2 }\cdot \tau =\tau \cdot { \sigma }^{ 4 } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 3 & 2 & 1 & 6 & 5 \end{pmatrix} \\ { \sigma }^{ 3 }\cdot \tau =\tau \cdot { \sigma }^{ 3 } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 1 & 6 & 5 & 4 \end{pmatrix} \\ { \sigma }^{ 4 }\cdot \tau =\tau \cdot { \sigma }^{ 2 } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 6 & 5 & 4 & 3 \end{pmatrix} \\ { \sigma }^{ 5 }\cdot \tau =\tau \cdot { \sigma } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 6 & 5 & 4 & 3 & 2 \end{pmatrix} \end{matrix}\) | ||
| + | |||
| + | 以上の結果を踏まえると、\(\tau\)を先に演算させるか後に演算させるか、どちらかに統一してまとめてしまえば裏返しはシミュレーションできるという事が分かる | ||
| + | よって群は以下のようなものとした | ||
| + | |||
| + | \(T=\left\{ \iota ,\sigma ,{ \sigma }^{ 2 },{ \sigma }^{ 3 },{ \sigma }^{ 4 },{ \sigma }^{ 5 },\tau ,\tau \sigma ,\tau { \sigma }^{ 2 },\tau { \sigma }^{ 3 },\tau { \sigma }^{ 4 },\tau { \sigma }^{ 5 } \right\} \) | ||
| + | |||
| + | この群\(T\)を使いX,Yから作成される順列のひとつひとつに群内の関数により元が書き変わらない置換（つまり演算結果が\(\iota\)になる関数）を探した | ||
| + | 結果は以下となった（ここで後述のプログラムコードを利用する） | ||
| \(AAAAAA:ι,σ,σ2,σ3,σ4,σ5,τ,τσ,τσ2,τσ3,τσ4,τσ5,\\ BAAAAA:ι,τσ,\\ ABAAAA:ι,τσ3,\\ BBAAAA:ι,τσ2,\\ AABAAA:ι,τσ5,\\ BABAAA:ι,τσ3,\\ ABBAAA:ι,τσ4,\\ BBBAAA:ι,τσ3,\\ AAABAA:ι,τσ,\\ BAABAA:ι,σ3,τσ,τσ4,\\ ABABAA:ι,τσ5,\\ BBABAA:ι,\\ AABBAA:ι,τ,\\ BABBAA:ι,\\ ABBBAA:ι,τσ5,\\ BBBBAA:ι,τσ4,\\ AAAABA:ι,τσ3,\\ BAAABA:ι,τσ5,\\ ABAABA:ι,σ3,τ,τσ3,\\ BBAABA:ι,\\ AABABA:ι,τσ,\\ BABABA:ι,σ2,σ4,τσ,τσ3,τσ5,\\ ABBABA:ι,\\ BBBABA:ι,τσ3,\\ AAABBA:ι,τσ2,\\ BAABBA:ι,\\ ABABBA:ι,\\ BBABBA:ι,σ3,τσ2,τσ5,\\ AABBBA:ι,τσ,\\ BABBBA:ι,τσ,\\ ABBBBA:ι,τ,\\ BBBBBA:ι,τσ5,\\ AAAAAB:ι,τσ5,\\ BAAAAB:ι,τ,\\ ABAAAB:ι,τσ,\\ BBAAAB:ι,τσ,\\ AABAAB:ι,σ3,τσ2,τσ5,\\ BABAAB:ι,\\ ABBAAB:ι,\\ BBBAAB:ι,τσ2,\\ AAABAB:ι,τσ3,\\ BAABAB:ι,\\ ABABAB:ι,σ2,σ4,τσ,τσ3,τσ5,\\ BBABAB:ι,τσ,\\ AABBAB:ι,\\ BABBAB:ι,σ3,τ,τσ3,\\ ABBBAB:ι,τσ5,\\ BBBBAB:ι,τσ3,\\ AAAABB:ι,τσ4,\\ BAAABB:ι,τσ5,\\ ABAABB:ι,\\ BBAABB:ι,τ,\\ AABABB:ι,\\ BABABB:ι,τσ5,\\ ABBABB:ι,σ3,τσ,τσ4,\\ BBBABB:ι,τσ,\\ AAABBB:ι,τσ3,\\ BAABBB:ι,τσ4,\\ ABABBB:ι,τσ3,\\ BBABBB:ι,τσ5,\\ AABBBB:ι,τσ2,\\ BABBBB:ι,τσ3,\\ ABBBBB:ι,τσ,\\ BBBBBB:ι,σ,σ2,σ3,σ4,σ5,τ,τσ,τσ2,τσ3,τσ4,τσ5,\) | \(AAAAAA:ι,σ,σ2,σ3,σ4,σ5,τ,τσ,τσ2,τσ3,τσ4,τσ5,\\ BAAAAA:ι,τσ,\\ ABAAAA:ι,τσ3,\\ BBAAAA:ι,τσ2,\\ AABAAA:ι,τσ5,\\ BABAAA:ι,τσ3,\\ ABBAAA:ι,τσ4,\\ BBBAAA:ι,τσ3,\\ AAABAA:ι,τσ,\\ BAABAA:ι,σ3,τσ,τσ4,\\ ABABAA:ι,τσ5,\\ BBABAA:ι,\\ AABBAA:ι,τ,\\ BABBAA:ι,\\ ABBBAA:ι,τσ5,\\ BBBBAA:ι,τσ4,\\ AAAABA:ι,τσ3,\\ BAAABA:ι,τσ5,\\ ABAABA:ι,σ3,τ,τσ3,\\ BBAABA:ι,\\ AABABA:ι,τσ,\\ BABABA:ι,σ2,σ4,τσ,τσ3,τσ5,\\ ABBABA:ι,\\ BBBABA:ι,τσ3,\\ AAABBA:ι,τσ2,\\ BAABBA:ι,\\ ABABBA:ι,\\ BBABBA:ι,σ3,τσ2,τσ5,\\ AABBBA:ι,τσ,\\ BABBBA:ι,τσ,\\ ABBBBA:ι,τ,\\ BBBBBA:ι,τσ5,\\ AAAAAB:ι,τσ5,\\ BAAAAB:ι,τ,\\ ABAAAB:ι,τσ,\\ BBAAAB:ι,τσ,\\ AABAAB:ι,σ3,τσ2,τσ5,\\ BABAAB:ι,\\ ABBAAB:ι,\\ BBBAAB:ι,τσ2,\\ AAABAB:ι,τσ3,\\ BAABAB:ι,\\ ABABAB:ι,σ2,σ4,τσ,τσ3,τσ5,\\ BBABAB:ι,τσ,\\ AABBAB:ι,\\ BABBAB:ι,σ3,τ,τσ3,\\ ABBBAB:ι,τσ5,\\ BBBBAB:ι,τσ3,\\ AAAABB:ι,τσ4,\\ BAAABB:ι,τσ5,\\ ABAABB:ι,\\ BBAABB:ι,τ,\\ AABABB:ι,\\ BABABB:ι,τσ5,\\ ABBABB:ι,σ3,τσ,τσ4,\\ BBBABB:ι,τσ,\\ AAABBB:ι,τσ3,\\ BAABBB:ι,τσ4,\\ ABABBB:ι,τσ3,\\ BBABBB:ι,τσ5,\\ AABBBB:ι,τσ2,\\ BABBBB:ι,τσ3,\\ ABBBBB:ι,τσ,\\ BBBBBB:ι,σ,σ2,σ3,σ4,σ5,τ,τσ,τσ2,τσ3,τσ4,τσ5,\) | ||
| Line 11: | Line 37: | ||
| \(\iota \quad 64={ 2 }^{ 6 }回\\ \sigma \quad 2={ 2 }^{ 1 }回\\ \sigma ^{ 2 }\quad 4={ 2 }^{ 2 }回\\ \sigma ^{ 3 }\quad 8={ 2 }^{ 3 }回\\ \sigma ^{ 4 }\quad 4={ 2 }^{ 2 }回\\ \sigma ^{ 5 }\quad 2={ 2 }^{ 1 }回\\ \tau \quad 8={ 2 }^{ 3 }回\\ \tau \sigma \quad 16={ 2 }^{ 4 }回\\ \tau \sigma ^{ 2 }\quad 8={ 2 }^{ 3 }回\\ \tau \sigma ^{ 3 }\quad 16={ 2 }^{ 4 }回\\ \tau \sigma ^{ 4 }\quad 8={ 2 }^{ 3 }回\\ \tau \sigma ^{ 5 }\quad 16={ 2 }^{ 4 }回\) | \(\iota \quad 64={ 2 }^{ 6 }回\\ \sigma \quad 2={ 2 }^{ 1 }回\\ \sigma ^{ 2 }\quad 4={ 2 }^{ 2 }回\\ \sigma ^{ 3 }\quad 8={ 2 }^{ 3 }回\\ \sigma ^{ 4 }\quad 4={ 2 }^{ 2 }回\\ \sigma ^{ 5 }\quad 2={ 2 }^{ 1 }回\\ \tau \quad 8={ 2 }^{ 3 }回\\ \tau \sigma \quad 16={ 2 }^{ 4 }回\\ \tau \sigma ^{ 2 }\quad 8={ 2 }^{ 3 }回\\ \tau \sigma ^{ 3 }\quad 16={ 2 }^{ 4 }回\\ \tau \sigma ^{ 4 }\quad 8={ 2 }^{ 3 }回\\ \tau \sigma ^{ 5 }\quad 16={ 2 }^{ 4 }回\) | ||
| - | 同値類の個数は | + | 順列における各置換関数の使用回数がこれで解った |
| + | ここで書籍「なっとくする群・環・体」で説明されているフロベニウス（P69定理2）を利用する。公式に沿って式を作ると以下になる | ||
| + | |||
| + | \(同値類の個数d=\left\{ W\left( \iota \right) +W\left( \sigma \right) +W\left( { \sigma }^{ 2 } \right) +W\left( { \sigma }^{ 3 } \right) +W\left( { \sigma }^{ 4 } \right) +W\left( { \sigma }^{ 5 } \right) +W\left( \tau \right) +W\left( \tau \sigma \right) +W\left( \tau { \sigma }^{ 2 } \right) +W\left( \tau { \sigma }^{ 3 } \right) +W\left( \tau { \sigma }^{ 4 } \right) +W\left( \tau { \sigma }^{ 5 } \right) \right\} \div \left| T \right| \\ d=\left\{ { 2 }^{ 6 }+{ 2 }^{ 1 }{ +2 }^{ 2 }+{ 2 }^{ 3 }+{ 2 }^{ 2 }+{ 2 }^{ 1 }\quad +{ 2 }^{ 3 }+{ 2 }^{ 4 }{ +2 }^{ 3 }+{ 2 }^{ 4 }+{ 2 }^{ 3 }+{ 2 }^{ 4 } \right\} \div 12\\ \quad =\frac { 84+72 }{ 12 } =\frac { 156 }{ 12 } =13\) | ||
| + | |||
| + | ここから問題２が解ける。書籍「なっとくする群・環・体」ではP70に、この問題の答えを書いてくれている（途中経過や式は無い） | ||
| + | そこで天下り的に、答えが合致すれば「フロベニウスの利用方法が合っている」と考え計算式を以下のように作って答え合わせをしてみると・・・ | ||
| + | |||
| + | \(同値類の個数d=\left\{ W\left( \iota \right) +W\left( \sigma \right) +W\left( { \sigma }^{ 2 } \right) +W\left( { \sigma }^{ 3 } \right) +W\left( { \sigma }^{ 4 } \right) +W\left( { \sigma }^{ 5 } \right) +W\left( \tau \right) +W\left( \tau \sigma \right) +W\left( \tau { \sigma }^{ 2 } \right) +W\left( \tau { \sigma }^{ 3 } \right) +W\left( \tau { \sigma }^{ 4 } \right) +W\left( \tau { \sigma }^{ 5 } \right) \right\} \div \left| T \right| \\ d=\left\{ { 3 }^{ 6 }+3^{ 1 }{ +3 }^{ 2 }+3^{ 3 }+{ 3 }^{ 2 }+{ 3 }^{ 1 }\quad +3^{ 3 }+3^{ 4 }{ +3 }^{ 3 }+3^{ 4 }+3^{ 3 }+3^{ 4 } \right\} \div 12\\ \quad =\frac { 780+324 }{ 12 } =\frac { 1104 }{ 12 } =92\) | ||
| + | |||
| + | 合っていたようだ | ||
| - | \(同値類の個数d=\left\{ W\left( \iota \right) +W\left( \sigma \right) +W\left( { \sigma }^{ 2 } \right) +W\left( { \sigma }^{ 3 } \right) +W\left( { \sigma }^{ 4 } \right) +W\left( { \sigma }^{ 5 } \right) +W\left( \tau \right) +W\left( \tau \sigma \right) +W\left( \tau { \sigma }^{ 2 } \right) +W\left( \tau { \sigma }^{ 3 } \right) +W\left( \tau { \sigma }^{ 4 } \right) +W\left( \tau { \sigma }^{ 5 } \right) \right\} \div \left| G \right| \\ d=\left\{ { 2 }^{ 6 }+{ 2 }^{ 1 }{ +2 }^{ 2 }+{ 2 }^{ 3 }+{ 2 }^{ 2 }+{ 2 }^{ 1 }\quad +{ 2 }^{ 3 }+{ 2 }^{ 4 }{ +2 }^{ 3 }+{ 2 }^{ 4 }+{ 2 }^{ 3 }+{ 2 }^{ 4 } \right\} \div 12\\ \quad =\frac { 84+72 }{ 12 } =\frac { 156 }{ 12 } =13\) | + | &font(Silver){＜個人的認識＞&br;これはあくまで演習であり群の利用方法のひとつを学ぶ事が目的だと考えた方が良い（この場合、群Tの存在を認識する事。フロベニウスのようなものが存在すると認識する事が目的）&br;同値類を求めるだけなら、もっとシンプルに直球なコードをブルートフォースで組んでしまう方が早いと思われる（このような回転置換を考える時、PCの計算支援は非常に強力で便利）&br;}; |
| - | ここから問題２が解ける | + | 資料：[[フロベニウス方程式:http://reference.wolfram.com/language/tutorial/Frobenius.ja.html]] |
| - | \(同値類の個数d=\left\{ W\left( \iota \right) +W\left( \sigma \right) +W\left( { \sigma }^{ 2 } \right) +W\left( { \sigma }^{ 3 } \right) +W\left( { \sigma }^{ 4 } \right) +W\left( { \sigma }^{ 5 } \right) +W\left( \tau \right) +W\left( \tau \sigma \right) +W\left( \tau { \sigma }^{ 2 } \right) +W\left( \tau { \sigma }^{ 3 } \right) +W\left( \tau { \sigma }^{ 4 } \right) +W\left( \tau { \sigma }^{ 5 } \right) \right\} \div \left| G \right| \\ d=\left\{ { 3 }^{ 6 }+3^{ 1 }{ +3 }^{ 2 }+3^{ 3 }+{ 3 }^{ 2 }+{ 3 }^{ 1 }\quad +3^{ 3 }+3^{ 4 }{ +3 }^{ 3 }+3^{ 4 }+3^{ 3 }+3^{ 4 } \right\} \div 12\\ \quad =\frac { 780+324 }{ 12 } =\frac { 1104 }{ 12 } =92\) | ||
| - | ・・・これは個人的な考えですが、回転置換群を考える時ある程度PCの計算支援が無いと計算量的にイメージがつかめないような気がします。本の読み方がわるいんだろうか・・・ | + | ＜メモ＞ |
| + | 群の中の関数は「互いに素」の関係に近い？ | ||
| ***支援コード [#c44bc7d8] | ***支援コード [#c44bc7d8] | ||
| - | この計算を解く目的だけに作っています。汎用性はありません | + | この計算を解く目的だけに作っている。汎用性はない |
| - | 回転置換群はもっと汎用的に作れると思います。悪い例 | + | 回転置換群はもっと汎用的に作れる |
| #code(csharp){{ | #code(csharp){{ | ||
- メモ7 のバックアップ一覧
- メモ7 のバックアップの現在との差分(No. All)
- 1: 2016-09-21 (水) 22:33:16 osinko
- 2: 2016-09-21 (水) 23:17:35 osinko
- 3: 2016-09-22 (木) 02:06:19 osinko
- 4: 2016-09-22 (木) 16:46:49 osinko
- 5: 2016-09-22 (木) 18:02:03 osinko
