問題を解く
<問題2>
赤、青、黄のカラー被覆の銅線を6本束ねたケーブルで製品として異なるものは何種類作れるか?
このケーブルは回転させたり、前後を逆(裏返し)にして利用できるものとする。(書籍「なっとくする群・環・体」 P51問2より)
上記の様な問題を解く。まず順番に考えるために、より小さなスケールに問題を書き換えて考えることにする
問題を以下のように書き換える
<問題2-a>
A、Bの2種の銅線を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,\)
回転置換の出現回数を数えると以下になる
\(\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\)
ここから問題2が解ける。書籍「なっとくする群・環・体」では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\)
合っていたようだ
<個人的認識> これはあくまで演習であり群の利用方法のひとつを学ぶ事が目的だと考えた方が良い(この場合、群Tの存在を認識する事。フロベニウスのようなものが存在すると認識する事が目的) 同値類を求めるだけなら、もっとシンプルに直球なコードをブルートフォースで組んでしまう方が早いと思われる(このような回転置換を考える時、PCの計算支援は非常に強力で便利)
資料:フロベニウス方程式
<メモ>
群の中の関数は「互いに素」の関係に近い?
支援コード
この計算を解く目的だけに作っている。汎用性はない
回転置換群はもっと汎用的に作れる
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
-
|
-
|
|
|
|
|
-
|
!
|
|
|
!
|
-
!
-
|
|
|
-
|
!
|
|
|
|
|
-
|
!
|
|
-
|
|
|
-
-
!
-
|
|
|
!
|
!
!
|
|
|
!
|
-
!
-
|
-
|
-
|
!
!
!
|
!
-
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
!
|
|
-
|
|
|
-
|
!
|
!
!
-
!
-
|
|
|
|
|
-
|
|
|
!
|
|
-
|
|
|
!
|
-
!
-
|
|
|
-
|
!
|
-
|
!
|
-
|
!
|
|
!
|
-
!
-
-
!
-
|
!
|
-
!
-
|
!
|
|
!
|
-
!
-
|
!
|
-
!
-
|
!
!
| using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.IO;
public class Model2 : MonoBehaviour
{
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; 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<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();
}
}
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 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;
}
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); }
public override string ToString()
{
return X;
}
}
|
|