1: 2016-09-21 (水) 22:33:16 osinko |
現: 2016-09-22 (木) 21:47:23 osinko |
| + | #jsmath |
| **問題を解く [#b956373c] | | **問題を解く [#b956373c] |
| | | |
- | プログラムを組んで作成した回転置換により元が書き変わらない置換を探す | + | <問題2> |
- | これは | + | 赤、青、黄のカラー被覆の銅線を6本束ねたケーブルで製品として異なるものは何種類作れるか? |
| + | このケーブルは回転させたり、前後を逆(裏返し)にして利用できるものとする。(書籍「なっとくする群・環・体」 P51問2より) |
| | | |
- | AAAAAA : ι , σ , σ2 , σ3 , σ4 , σ5 , τ , τσ , τσ2 , τσ3 , τσ4 , τσ5 , | + | 上記の様な問題を解く。まず順番に考えるために、より小さなスケールに問題を書き換えて考えることにする |
- | BAAAAA : ι , τσ , | + | 問題を以下のように書き換える |
- | ABAAAA : ι , τσ3 , | + | |
- | BBAAAA : ι , τσ2 , | + | <問題2-a> |
- | AABAAA : ι , τσ5 , | + | A、Bの2種の銅線を6本束ねたケーブルで製品として異なるものは何種類作れるか? |
- | BABAAA : ι , τσ3 , | + | このケーブルは回転させたり、前後を逆(裏返し)にして利用できるものとする |
- | ABBAAA : ι , τσ4 , | + | |
- | BBBAAA : ι , τσ3 , | + | この問題を回転する置換群で考えてモデル化すると集合と置換関数は以下になる |
- | AAABAA : ι , τσ , | + | |
- | BAABAA : ι , σ3 , τσ , τσ4 , | + | \(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}\) |
- | ABABAA : ι , τσ5 , | + | |
- | BBABAA : ι , | + | \(\iota\)が恒等置換(置換しない置換)。\(\sigma\)が回転を表す置換関数。\(\tau\)が反転、この問題の場合「裏返し」をシミュレーションする置換関数となる |
- | AABBAA : ι , τ , | + | これらの関数で群を作成するが、この時、\(\sigma\)と\(\tau\)の二項演算に対して演算の順番によって結果が変わることを考慮する必要がある |
- | BABBAA : ι , | + | 実際にこれを確認すると以下のようになっていた |
- | ABBBAA : ι , τσ5 , | + | |
- | BBBBAA : ι , τσ4 , | + | \(\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}\) |
- | AAAABA : ι , τσ3 , | + | |
- | BAAABA : ι , τσ5 , | + | 以上の結果を踏まえると、\(\tau\)を先に演算させるか後に演算させるか、どちらかに統一してまとめてしまえば裏返しはシミュレーションできるという事が分かる |
- | ABAABA : ι , σ3 , τ , τσ3 , | + | よって群は以下のようなものとした |
- | BBAABA : ι , | + | |
- | AABABA : ι , τσ , | + | \(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\} \) |
- | BABABA : ι , σ2 , σ4 , τσ , τσ3 , τσ5 , | + | |
- | ABBABA : ι , | + | この群\(T\)を使いX,Yから作成される順列のひとつひとつに群内の関数により元が書き変わらない置換(つまり演算結果が\(\iota\)になる関数)を探した |
- | BBBABA : ι , τσ3 , | + | 結果は以下となった(ここで後述のプログラムコードを利用する) |
- | AAABBA : ι , τσ2 , | + | |
- | BAABBA : ι , | + | \(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,\) |
- | ABABBA : ι , | + | |
- | BBABBA : ι , σ3 , τσ2 , τσ5 , | + | 回転置換の出現回数を数えると以下になる |
- | AABBBA : ι , τσ , | + | |
- | BABBBA : ι , τσ , | + | \(\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 }回\) |
- | ABBBBA : ι , τ , | + | |
- | BBBBBA : ι , τσ5 , | + | 順列における各置換関数の使用回数がこれで解った |
- | AAAAAB : ι , τσ5 , | + | ここで書籍「なっとくする群・環・体」で説明されているフロベニウス(P69定理2)を利用する。公式に沿って式を作ると以下になる |
- | BAAAAB : ι , τ , | + | |
- | ABAAAB : ι , τσ , | + | \(同値類の個数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\) |
- | BBAAAB : ι , τσ , | + | |
- | AABAAB : ι , σ3 , τσ2 , τσ5 , | + | ここから問題2が解ける。書籍「なっとくする群・環・体」ではP70に、この問題の答えを書いてくれている(途中経過や式は無い) |
- | BABAAB : ι , | + | そこで天下り的に、答えが合致すれば「フロベニウスの利用方法が合っている」と考え計算式を以下のように作って答え合わせをしてみると・・・ |
- | ABBAAB : ι , | + | |
- | BBBAAB : ι , τσ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\{ { 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\) |
- | AAABAB : ι , τσ3 , | + | |
- | BAABAB : ι , | + | 合っていたようだ |
- | ABABAB : ι , σ2 , σ4 , τσ , τσ3 , τσ5 , | + | |
- | BBABAB : ι , τσ , | + | &font(Silver){<個人的認識>&br;これはあくまで演習であり群の利用方法のひとつを学ぶ事が目的だと考えた方が良い(この場合、群Tの存在を認識する事。フロベニウスのようなものが存在すると認識する事が目的)&br;同値類を求めるだけなら、もっとシンプルに直球なコードをブルートフォースで組んでしまう方が早いと思われる(このような回転置換を考える時、PCの計算支援は非常に強力で便利)&br;}; |
- | AABBAB : ι , | + | |
- | BABBAB : ι , σ3 , τ , τσ3 , | + | 資料:[[フロベニウス方程式:http://reference.wolfram.com/language/tutorial/Frobenius.ja.html]] |
- | ABBBAB : ι , τσ5 , | + | |
- | BBBBAB : ι , τσ3 , | + | |
- | AAAABB : ι , τσ4 , | + | <メモ> |
- | BAAABB : ι , τσ5 , | + | 群の中の関数は「互いに素」の関係に近い? |
- | ABAABB : ι , | + | |
- | BBAABB : ι , τ , | + | ***支援コード [#c44bc7d8] |
- | AABABB : ι , | + | この計算を解く目的だけに作っている。汎用性はない |
- | BABABB : ι , τσ5 , | + | 回転置換群はもっと汎用的に作れる |
- | ABBABB : ι , σ3 , τσ , τσ4 , | + | |
- | BBBABB : ι , τσ , | + | #code(csharp){{ |
- | AAABBB : ι , τσ3 , | + | using UnityEngine; |
- | BAABBB : ι , τσ4 , | + | using System.Collections; |
- | ABABBB : ι , τσ3 , | + | using System.Collections.Generic; |
- | BBABBB : ι , τσ5 , | + | using System.IO; |
- | AABBBB : ι , τσ2 , | + | |
- | BABBBB : ι , τσ3 , | + | public class Model2 : MonoBehaviour |
- | ABBBBB : ι , τσ , | + | { |
- | BBBBBB : ι , σ , σ2 , σ3 , σ4 , σ5 , τ , τσ , τσ2 , τσ3 , τσ4 , τσ5 , | + | void Start() |
| + | { |
| + | List<string> strList = Permutation(6, new char[] { 'A', 'B' }); |
| + | RotateGropup rg = new RotateGropup(); |
| + | |
| + | List<string> rotList = new List<string>(); |
| + | for (int i = 0; i < strList.Count; i++) |
| + | { |
| + | rotList.Add(string.Format("{0} : {1}", strList[i],rg.Where(new Rotate(strList[i])))); |
| + | } |
| + | |
| + | string folder = Application.dataPath; //これだけでunityの実行ファイルがあるフォルダがわかる |
| + | SaveText(folder, @"\置換サーチ結果.txt", rotList.ToArray()); |
| + | } |
| + | |
| + | //順列作成 |
| + | public List<string> Permutation(int x, char[] y) |
| + | { |
| + | |
| + | int[] Z = new int[x+1]; |
| + | for (int i = 0; i < Z.Length; i++) |
| + | { |
| + | Z[i] = (int)Mathf.Pow(y.Length, i); //指数を利用して作成した数列 |
| + | } |
| + | int total = Z[Z.Length - 1]; |
| + | |
| + | |
| + | List<char[]> charList = new List<char[]>(); |
| + | for (int i = 0; i < total; i++) |
| + | { |
| + | charList.Add(new char[x]); |
| + | } |
| + | |
| + | for (int i = 0; i < x; i++) |
| + | { |
| + | int mod = 0; |
| + | char set = y[mod]; |
| + | for (int j = 0; j < total; j++) |
| + | { |
| + | //指数の数列と回転置換群との関係をここで利用してる |
| + | if (j % Z[i] == 0) |
| + | { |
| + | set = y[mod % (y.Length)]; |
| + | mod++; |
| + | |
| + | } |
| + | charList[j][i] = set; //二次元配列的なListの使用方法 |
| + | } |
| + | } |
| + | |
| + | List<string> strList = charList.ConvertAll<string>(z => new string(z)); //こういう変換方法もある |
| + | return strList; |
| + | } |
| + | |
| + | //テキストファイルとしてセーブ |
| + | public void SaveText(string fileFolder, string filename, string[] dataStr) |
| + | { |
| + | using (StreamWriter w = new StreamWriter(fileFolder + filename, false, System.Text.Encoding.GetEncoding("shift_jis"))) |
| + | { |
| + | foreach (var item in dataStr) |
| + | { |
| + | w.WriteLine(item); |
| + | } |
| + | } |
| + | } |
| + | |
| + | } |
| + | |
| + | class RotateGropup |
| + | { |
| + | public List<Rotate> rx = new List<Rotate>(); |
| + | |
| + | public RotateGropup() |
| + | { |
| + | rx.Add(new Rotate("ι", new int[] { 0, 1, 2, 3, 4, 5 })); |
| + | rx.Add(new Rotate("σ", new int[] { 5, 0, 1, 2, 3, 4 })); |
| + | rx.Add(new Rotate("σ2", new int[] { 4, 5, 0, 1, 2, 3 })); |
| + | rx.Add(new Rotate("σ3", new int[] { 3, 4, 5, 0, 1, 2 })); |
| + | rx.Add(new Rotate("σ4", new int[] { 2, 3, 4, 5, 0, 1 })); |
| + | rx.Add(new Rotate("σ5", new int[] { 1, 2, 3, 4, 5, 0 })); |
| + | rx.Add(new Rotate("τ", new int[] { 5, 4, 3, 2, 1, 0 })); |
| + | rx.Add(new Rotate("τσ", new int[] { 0, 5, 4, 3, 2, 1 })); |
| + | rx.Add(new Rotate("τσ2", new int[] { 1, 0, 5, 4, 3, 2 })); |
| + | rx.Add(new Rotate("τσ3", new int[] { 2, 1, 0, 5, 4, 3 })); |
| + | rx.Add(new Rotate("τσ4", new int[] { 3, 2, 1, 0, 5, 4 })); |
| + | rx.Add(new Rotate("τσ5", new int[] { 4, 3, 2, 1, 0, 5 })); |
| + | } |
| + | |
| + | public string Where(Rotate f) |
| + | { |
| + | System.Text.StringBuilder sb = new System.Text.StringBuilder(); |
| + | |
| + | for (int i = 0; i < rx.Count; i++) |
| + | { |
| + | if (f * rx[0] == f * rx[i]) sb.Append(rx[i].name + " , "); |
| + | } |
| + | return sb.ToString(); |
| + | } |
| + | } |
| + | |
| + | //回転をモデル化した置換群R |
| + | class Rotate |
| + | { |
| + | public string name; |
| + | public string X; |
| + | public int[] shift; |
| + | |
| + | public Rotate(string name, int[] shift) |
| + | { |
| + | this.name = name; |
| + | this.X = "012345"; |
| + | this.shift = shift; |
| + | } |
| + | |
| + | public Rotate(string X) |
| + | { |
| + | this.name = "func"; |
| + | this.X = X; |
| + | this.shift = new int[] { 0, 1, 2, 3, 4, 5 }; |
| + | } |
| + | |
| + | //演算子「*」のオーバーロード |
| + | public static Rotate operator *(Rotate left, Rotate right) |
| + | { |
| + | char[] temp = new char[left.X.Length]; |
| + | char[] temp2 = new char[left.X.Length]; |
| + | for (int i = 0; i < left.shift.Length; i++) |
| + | { |
| + | temp[i] = left.X[left.shift[i]]; |
| + | } |
| + | for (int i = 0; i < right.shift.Length; i++) |
| + | { |
| + | temp2[i] = temp[right.shift[i]]; |
| + | } |
| + | |
| + | //あたらしいRotate型を作って返す |
| + | //演算後はιで文字列の配置が変わった物を渡している。これが連続する二項演算の左辺になる |
| + | Rotate iota = new Rotate("iota", new int[] { 0, 1, 2, 3, 4, 5 }); |
| + | iota.X = new string(temp2); |
| + | return iota; |
| + | } |
| + | |
| + | //演算子「==」のオーバーロード |
| + | public static bool operator ==(Rotate left, Rotate right) |
| + | { |
| + | //オブジェクトとして同一かどうか |
| + | if (object.ReferenceEquals(left, right)) |
| + | { |
| + | return true; |
| + | } |
| + | |
| + | //オブジェクトとしてnullかどうか |
| + | if (((object)left == null) || ((object)right == null)) |
| + | { |
| + | return false; |
| + | } |
| + | |
| + | return (left.X == right.X); |
| + | } |
| + | |
| + | //演算子「==」と共に必ず設定する必要がある |
| + | public static bool operator !=(Rotate left, Rotate right) |
| + | { |
| + | return !(left == right); //これはoperatorの処理で判定している |
| + | } |
| + | |
| + | //文字表示 |
| + | public override string ToString() |
| + | { |
| + | return X; |
| + | } |
| + | } |
| + | }} |