|
|
> No.1991[元記事へ]
GAIさんへのお返事です。
> どんな初期条件でも目的達成をさせるための戦略を練ってください。
ルービックキューブのように順に揃えていく手法です。
6以降の置換がわかりませんので、12!通りすべてが整うことはありません。
例
DATA 12,11,9,6,7,10,1,2,4,5,8,3 など
!散在型単純群M12を表すマシューパズル
PUBLIC NUMERIC R(12),M(12) !置換を定義する
DATA 12,11,10,9,8,7,6,5,4,3,2,1 !Invert (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)
DATA 1,12,2,11,3,10,4,9,5,8,6,7 !Merge (1)(2,3,5,9,8,10,6,11,4,7,12)
MAT READ R
MAT READ M
DIM T(12) !並び
DATA 3,7,6,5,9,8,1,2,4,12,11,10
MAT READ T
MAT PRINT T; !最初の並びを表示する
DIM TT(12)
PRINT "●1を揃える"
IF T(1)=1 THEN
PRINT "1は揃っています。"
ELSE
LET S=0
DO UNTIL T(12)=1
CALL PermMultiply(T,M,TT)
MAT T=TT
LET S=S+1
LOOP
CALL PermMultiply(T,R,TT)
MAT T=TT
IF S>1 THEN PRINT "M^";STR$(S); ELSE PRINT "M";
PRINT "R"
MAT PRINT T;
END IF
PRINT "●2を揃える"
IF T(2)=2 THEN
PRINT "2は揃っています。"
ELSE
LET S=0
DO UNTIL T(2)=2
CALL PermMultiply(T,M,TT)
MAT T=TT
LET S=S+1
LOOP
IF S>1 THEN PRINT "M^";STR$(S); ELSE PRINT "M";
MAT PRINT T;
END IF
PRINT "●3を揃える"
LET x1$="RM^2RM^5RM^4" !X1=(1)(2)(8)(9)(3,10,4,5)(6,7,11,12)
LET x2$="RMRM^3RM^2" !X2=(1)(2)(4,9)(3,11,10,5,8,7,12,6)
IF T(3)=3 THEN
PRINT "3は揃っています。"
ELSEIF T(4)=3 OR T(5)=3 OR T(10)=3 THEN
CALL MOVE(3,3,T,x1$)
ELSEIF T(9)<>3 THEN
CALL MOVE(3,3,T,x2$)
ELSE
CALL MACRO(T,x2$) !9⇒4→3
CALL MOVE(3,3,T,x1$)
END IF
PRINT "●4を揃える"
LET y1$="RM^3RMRM^3RMRM^2RM^3" !Y1=(1)(2)(3)(11)(4,7,6,12)(5,10,8,9)
LET y2$="MRMRMRM^4RM^2RMRMRM^6RM" !Y2=(1)(2)(3)(10)(4,7)(5,6)(8,12)(9,11)
IF T(4)=4 THEN
PRINT "4は揃っています。"
ELSE
IF T(6)=4 OR T(7)=4 OR T(12)=4 THEN
CALL MOVE(4,4,T,y1$)
ELSEIF T(11)=4 THEN
CALL MACRO(T,y2$) !11⇒9→8⇒12→4
CALL MOVE(4,8,T,y1$)
CALL MACRO(T,y2$)
CALL MOVE(4,4,T,y1$)
ELSEIF T(5)=4 OR T(8)=4 OR T(9)=4 OR T(10)=4 THEN
CALL MOVE(4,8,T,y1$) !→8⇒12→4
CALL MACRO(T,y2$)
CALL MOVE(4,4,T,y1$)
END IF
END IF
PRINT "●5を揃える"
LET z1$="M^3RM^2RM^5RM" !Z1=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9)
LET z2$="MRM^3RM^2RM^3RM^5R" !Z2=(1)(2)(3)(4)(5,6,12,11)(7,8,10,9)
IF T(5)=5 THEN
PRINT "5は揃っています。"
ELSE
IF T(7)=5 OR T(10)=5 OR T(12)=5 THEN
CALL MOVE(5,5,T,z1$)
ELSEIF T(6)=5 OR T(8)=5 OR T(9)=5 OR T(11)=5 THEN
CALL MOVE(5,6,T,z1$) !→6→5
CALL MOVE(5,5,T,z2$)
END IF
END IF
PRINT "●6を揃える"
IF T(6)=6 THEN
PRINT "6は揃っています。"
ELSE
PRINT "未サポート"
STOP
END IF
PRINT "●7を揃える"
IF T(7)=7 THEN
PRINT "7は揃っています。"
ELSE
PRINT "未サポート"
STOP
END IF
PRINT "●8を揃える"
IF T(8)=8 THEN
PRINT "8は揃っています。"
ELSE
PRINT "未サポート"
STOP
END IF
PRINT "●9を揃える"
IF T(9)=9 THEN
PRINT "9は揃っています。"
ELSE
PRINT "未サポート"
STOP
END IF
PRINT "●10を揃える"
IF T(10)=10 THEN
PRINT "10は揃っています。"
ELSE
PRINT "未サポート"
STOP
END IF
PRINT "●11,12を揃える"
IF T(11)=11 THEN
PRINT "11,12は揃っています。"
ELSE
PRINT "未サポート"
STOP
END IF
PRINT "完成！"
END
EXTERNAL SUB MOVE(N,P,T(),S$) !数字nを位置pに移動させる
FOR i=1 TO 12
IF T(P)=N THEN EXIT FOR !指定位置まで
CALL MACRO(T,S$)
NEXT i
IF i>12 THEN !ループを確認する
PRINT "並べ替えができません。"
STOP
END IF
END SUB
EXTERNAL SUB MACRO(T(),S$) !マクロとして実行する
PRINT S$ !スクリプトを表示する
DIM TT(12)
LET i=1 !スクリプトを実行する
DO WHILE i<=LEN(S$)
LET t$=UCASE$(S$(i:i)) !1文字コマンドとして
SELECT CASE t$
CASE "M"
CALL PermMultiply(T,M,TT)
MAT T=TT
LET t0$="M"
CASE "R"
CALL PermMultiply(T,R,TT)
MAT T=TT
LET t0$="R"
CASE "^" !べき乗
LET i=i+1
LET V=0 !数値を読み込む
LET t$=UCASE$(S$(i:i))
DO WHILE t$>="0" AND t$<="9" !10進法
LET V=V*10+VAL(t$)
LET i=i+1 !次の位へ
LET t$=UCASE$(S$(i:i))
LOOP
LET i=i-1 !読み過ぎを戻す
IF t0$="R" THEN
FOR J=2 TO V !R^V
CALL PermMultiply(T,R,TT)
MAT T=TT
NEXT J
ELSE
FOR J=2 TO V !M^V
CALL PermMultiply(T,M,TT)
MAT T=TT
NEXT J
END IF
CASE " "
!skip it
CASE ELSE
PRINT "文字列に誤りがあります。";i
STOP
END SELECT
LET i=i+1 !次へ
LOOP
MAT PRINT T; !結果を表示する
END SUB
!置換（Permutation）の計算
EXTERNAL SUB PermIdentity(A()) !恒等置換
FOR i=1 TO UBOUND(A)
LET A(i)=i
NEXT i
END SUB
EXTERNAL SUB PermInverse(A(), iA()) !逆置換 ※iAはA以外の配列を指定すること
FOR i=1 TO UBOUND(A)
LET iA(A(i))=i
NEXT i
END SUB
EXTERNAL SUB PermMultiply(A(),B(), AB()) !積AB ※ABはA以外かつB以外の配列を指定すること
FOR i=1 TO UBOUND(A)
LET AB(i)=A(B(i)) !※合成写像(AB)(i)=A(B(i))
NEXT i
END SUB
実行結果
3 7 6 5 9 8 1 2 4 12 11 10
●1を揃える
MR
1 8 2 9 4 5 12 6 11 7 10 3
●2を揃える
M^10
1 2 4 12 11 10 3 7 6 5 9 8
●3を揃える
RMRM^3RM^2
1 2 10 6 5 8 7 11 12 9 4 3
RMRM^3RM^2
1 2 8 12 9 3 11 5 6 4 10 7
RMRM^3RM^2
1 2 3 6 4 7 5 9 12 10 8 11
●4を揃える
RM^3RMRM^3RMRM^2RM^3
1 2 3 11 12 5 6 10 9 4 8 7
RM^3RMRM^3RMRM^2RM^3
1 2 3 7 9 6 11 4 10 12 8 5
MRMRMRM^4RM^2RMRMRM^6RM
1 2 3 11 6 9 7 5 8 12 10 4
RM^3RMRM^3RMRM^2RM^3
1 2 3 4 8 7 11 12 5 6 10 9
●5を揃える
M^3RM^2RM^5RM
1 2 3 4 11 5 9 7 10 8 12 6
MRM^3RM^2RM^3RM^5R
1 2 3 4 5 6 7 8 9 10 11 12
●6を揃える
6は揃っています。
●7を揃える
7は揃っています。
●8を揃える
8は揃っています。
●9を揃える
9は揃っています。
●10を揃える
10は揃っています。
●11,12を揃える
11,12は揃っています。
完成！
|
|