1: 2016-09-21 (水) 22:33:16 osinko |
2: 2016-09-21 (水) 23:17:35 osinko |
| + | #jsmath |
| **問題を解く [#b956373c] | | **問題を解く [#b956373c] |
| | | |
- | プログラムを組んで作成した回転置換により元が書き変わらない置換を探す | + | プログラムを組んで回転置換により元が書き変わらない置換を探した。 |
- | これは | + | 条件は\(X=\left\{ 1,2,3,4,5,6 \right\} ,Y=\left\{ A,B \right\} \)。出力結果が以下になる |
| | | |
- | AAAAAA : ι , σ , σ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,\) |
- | BAAAAA : ι , τσ , | + | |
- | ABAAAA : ι , τσ3 , | + | 回転置換の出現回数を数えると以下になる |
- | BBAAAA : ι , τσ2 , | + | |
- | AABAAA : ι , τσ5 , | + | \(\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 }回\) |
- | BABAAA : ι , τσ3 , | + | |
- | ABBAAA : ι , τσ4 , | + | 同値類の個数は |
- | BBBAAA : ι , τσ3 , | + | |
- | AAABAA : ι , τσ , | + | \(同値類の個数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\) |
- | BAABAA : ι , σ3 , τσ , τσ4 , | + | |
- | ABABAA : ι , τσ5 , | + | ここから問題2が解ける |
- | BBABAA : ι , | + | |
- | AABBAA : ι , τ , | + | \(同値類の個数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\) |
- | BABBAA : ι , | + | |
- | ABBBAA : ι , τσ5 , | + | ・・・これは個人的な考えですが、回転置換群を考える時ある程度PCの計算支援が無いと計算量的にイメージがつかめないような気がします。本の読み方がわるいんだろうか・・・ |
- | BBBBAA : ι , τσ4 , | + | |
- | AAAABA : ι , τσ3 , | + | ***支援コード [#c44bc7d8] |
- | BAAABA : ι , τσ5 , | + | この計算を解く目的だけに作っています。汎用性はありません |
- | ABAABA : ι , σ3 , τ , τσ3 , | + | 回転置換群はもっと汎用的に作れると思います。悪い例 |
- | BBAABA : ι , | + | |
- | AABABA : ι , τσ , | + | #code(csharp){{ |
- | BABABA : ι , σ2 , σ4 , τσ , τσ3 , τσ5 , | + | using UnityEngine; |
- | ABBABA : ι , | + | using System.Collections; |
- | BBBABA : ι , τσ3 , | + | using System.Collections.Generic; |
- | AAABBA : ι , τσ2 , | + | using System.IO; |
- | BAABBA : ι , | + | |
- | ABABBA : ι , | + | public class Model2 : MonoBehaviour |
- | BBABBA : ι , σ3 , τσ2 , τσ5 , | + | { |
- | AABBBA : ι , τσ , | + | void Start() |
- | BABBBA : ι , τσ , | + | { |
- | ABBBBA : ι , τ , | + | List<string> strList = Permutation(6, new char[] { 'A', 'B' }); |
- | BBBBBA : ι , τσ5 , | + | RotateGropup rg = new RotateGropup(); |
- | AAAAAB : ι , τσ5 , | + | |
- | BAAAAB : ι , τ , | + | List<string> rotList = new List<string>(); |
- | ABAAAB : ι , τσ , | + | for (int i = 0; i < strList.Count; i++) |
- | BBAAAB : ι , τσ , | + | { |
- | AABAAB : ι , σ3 , τσ2 , τσ5 , | + | rotList.Add(string.Format("{0} : {1}", strList[i],rg.Where(new Rotate(strList[i])))); |
- | BABAAB : ι , | + | } |
- | ABBAAB : ι , | + | |
- | BBBAAB : ι , τσ2 , | + | string folder = Application.dataPath; //これだけでunityの実行ファイルがあるフォルダがわかる |
- | AAABAB : ι , τσ3 , | + | SaveText(folder, @"\置換サーチ結果.txt", rotList.ToArray()); |
- | BAABAB : ι , | + | } |
- | ABABAB : ι , σ2 , σ4 , τσ , τσ3 , τσ5 , | + | |
- | BBABAB : ι , τσ , | + | //順列作成 |
- | AABBAB : ι , | + | public List<string> Permutation(int x, char[] y) |
- | BABBAB : ι , σ3 , τ , τσ3 , | + | { |
- | ABBBAB : ι , τσ5 , | + | |
- | BBBBAB : ι , τσ3 , | + | int[] Z = new int[x+1]; |
- | AAAABB : ι , τσ4 , | + | for (int i = 0; i < Z.Length; i++) |
- | BAAABB : ι , τσ5 , | + | { |
- | ABAABB : ι , | + | Z[i] = (int)Mathf.Pow(y.Length, i); //指数を利用して作成した数列 |
- | BBAABB : ι , τ , | + | } |
- | AABABB : ι , | + | int total = Z[Z.Length - 1]; |
- | BABABB : ι , τσ5 , | + | |
- | ABBABB : ι , σ3 , τσ , τσ4 , | + | |
- | BBBABB : ι , τσ , | + | List<char[]> charList = new List<char[]>(); |
- | AAABBB : ι , τσ3 , | + | for (int i = 0; i < total; i++) |
- | BAABBB : ι , τσ4 , | + | { |
- | ABABBB : ι , τσ3 , | + | charList.Add(new char[x]); |
- | BBABBB : ι , τσ5 , | + | } |
- | AABBBB : ι , τσ2 , | + | |
- | BABBBB : ι , τσ3 , | + | for (int i = 0; i < x; i++) |
- | ABBBBB : ι , τσ , | + | { |
- | BBBBBB : ι , σ , σ2 , σ3 , σ4 , σ5 , τ , τσ , τσ2 , τσ3 , τσ4 , τσ5 , | + | 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; |
| + | } |
| + | } |
| + | }} |