|
|
碁石（表裏が区別されない）とオセロの石（表裏が区別される）を使ったとき、R個選ぶことを考察する。
まず、碁石を使った場合
a.回転（輪全体を時計まわりに回転させる）
表 1 表 6
6 2 → 5 1
5 3 4 2
4 3
※表、裏は「目」の位置とする。
「対象物の手前から対象物を見る」が表なら、「向う側から見る」が裏になる。
R個に対して、a^0, a^1, a^2, a^3, …, a^(R-1) は、円順列を表す作用となる。
ただし、a^3=a(a(a))、すなわち「3回連続して行う」の意味とする。
4個を並べる場合
1: ○○○○
2: ○○○●（○○●○、○●○○、●○○○）
3: ○○●●（○●●○、●●○○、●○○●）
4: ○●○●（●○●○）
5: ○●●●（●●●○、●●○●、●○●●）
6: ●●●●
LET N=2 !n種類の石
LET R=4 !重複を許してr個選ぶ
LET B=N^R !一列に並べたときの「場合の数」 ※N進法R桁
DIM F(0 TO B-1) !篩い
MAT F=(-1)*CON
LET C=0 !個数
FOR i=0 TO B-1 !小さい順に篩いにかける
IF F(i)<0 THEN
LET W=i !円順列 ※並びを回転させる
FOR K=0 TO R-1
!表 1 表 5
! 5 2 → 4 1
! 4 3 3 2
LET T=MOD(W,B)+INT(W/B) !左ローテイト
IF T<>i THEN LET F(T)=i !自分自身（=最小値）は残す
LET W=W*N !次へ
NEXT K
LET C=C+1 !結果を表示する
PRINT STR$(C);":"; i; "(";
FOR K=i+1 TO B-1 !同一視するもの
IF F(K)=i THEN PRINT K;
NEXT K
PRINT ")"
END IF
NEXT i
END
実行結果
1: 0 ()
2: 1 ( 2 4 8 )
3: 3 ( 6 9 12 )
4: 5 ( 10 )
5: 7 ( 11 13 14 )
6: 15 ()
b.鏡映変換、反転（輪全体として反転させる）
表 1 表 1
6 2 → 2 6
5 3 3 5
4 4
R個に対して、a^0,a^1,a^2,a^3,…,a^(R-1) と b(a^0),b(a^1),b(a^2),b(a^3),…,b(a^(R-1)) は、
じゅず順列を表す作用となる。
LET N=2 !n種類の石
LET R=4 !重複を許してr個選ぶ
LET B=N^R !一列に並べたときの「場合の数」 ※N進法R桁
DIM F(0 TO B-1) !篩い
MAT F=(-1)*CON
LET C=0 !個数
FOR i=0 TO B-1 !小さい順に篩いにかける
IF F(i)<0 THEN
LET W=i !円順列 ※並びを回転させる
FOR K=0 TO R-1
!表 1 表 5
! 5 2 → 4 1
! 4 3 3 2
LET T=MOD(W,B)+INT(W/B) !左ローテイト
IF T<>i THEN LET F(T)=i !自分自身（=最小値）は残す
!表 1 表 1
! 5 2 → 2 5
! 4 3 3 4
LET V=T !数珠順列 ※鏡映変換（対称軸のひとつ、(12345)→(15432) ）
LET T=0
FOR J=1 TO R-1 !N進法R桁
LET T=T*N+MOD(V,N)
LET V=INT(V/N)
NEXT J
LET T=T+V*N^(R-1) !最上位（MSB）
IF T<>i THEN LET F(T)=i
LET W=W*N !次へ
NEXT K
LET C=C+1 !結果を表示する
PRINT STR$(C);":"; i; "(";
FOR K=i+1 TO B-1 !同一視するもの
IF F(K)=i THEN PRINT K;
NEXT K
PRINT ")"
END IF
NEXT i
END
次に、オセロの石を使った場合
反転（裏返す）ことで色が変わるので、上記に加えて次のことにも注意が必要である。
c.桁の反転（石の位置を固定して個々に反転させる）
表 1 表 [1]
6 2 → [6] [2]
5 3 [5] [3]
4 [4]
例
碁石のような表裏が区別されない（色が同じ）場合、
表 ● 表 ●
○ ● → ○ ●
● ○ ● ○
○ ○
恒等変換である。
オセロのような表裏が区別される（色が異なる）場合、
表 ● 表 ○
○ ● → ● ○
● ○ ○ ●
○ ●
円順列
LET N=2 !n種類の色を着けた（オセロの）石
LET R=4 !重複を許してr個選ぶ
LET M=2*COMB(N,2) !m種類の石
LET B=M^R !一列に並べたときの「場合の数」 ※M進法R桁
DIM F(0 TO B-1) !篩い
MAT F=(-1)*CON
LET C=0 !個数
FOR i=0 TO B-1 !小さい順に篩いにかける
IF F(i)<0 THEN
LET W=i !円順列 ※並びを回転させる
FOR K=0 TO R-1
LET T=MOD(W,B)+INT(W/B) !左ローテイト
IF T<>i THEN LET F(T)=i !自分自身（=最小値）は残す
!表 1 表 (1)
! 5 2 → (5) (2)
! 4 3 (4) (3)
LET V=(B-1)-T !桁の反転 ※2進法なら、ビットごとの反転（否定演算、1の補数）
IF V<>i THEN LET F(V)=i
LET W=W*M !次へ
NEXT K
LET C=C+1 !結果を表示する
PRINT STR$(C);":"; i; "(";
FOR K=i+1 TO B-1 !同一視するもの
IF F(K)=i THEN PRINT K;
NEXT K
PRINT ")"
END IF
NEXT i
END
じゅず順列
LET N=2 !n種類の色を着けた（オセロの）石
LET R=4 !重複を許してr個選ぶ
LET M=2*COMB(N,2) !m種類の石
LET B=M^R !一列に並べたときの「場合の数」 ※M進法R桁
DIM F(0 TO B-1) !篩い
MAT F=(-1)*CON
LET C=0 !個数
FOR i=0 TO B-1 !小さい順に篩いにかける
IF F(i)<0 THEN
LET W=i !円順列 ※並びを回転させる
FOR K=0 TO R-1
LET T=MOD(W,B)+INT(W/B) !左ローテイト
IF T<>i THEN LET F(T)=i !自分自身（=最小値）は残す
LET V=(B-1)-T !桁の反転 ※ビットごとの反転（否定演算、1の補数）
IF V<>i THEN LET F(V)=i
LET V=T !数珠順列 ※鏡映変換（対称軸のひとつ、(12345)→(15432) ）
LET T=0
FOR J=1 TO R-1 !M進法R桁
LET T=T*M+MOD(V,M)
LET V=INT(V/M)
NEXT J
LET T=T+V*M^(R-1) !最上位（MSB）
IF T<>i THEN LET F(T)=i
LET V=(B-1)-T !桁の反転 ※ビットごとの反転（否定演算、1の補数）
IF V<>i THEN LET F(V)=i
LET W=W*M !次へ
NEXT K
LET C=C+1 !結果を表示する
PRINT STR$(C);":"; i; "(";
FOR K=i+1 TO B-1 !同一視するもの
IF F(K)=i THEN PRINT K;
NEXT K
PRINT ")"
END IF
NEXT i
END
d.下から見る
表 1 裏 [1]
6 2 → [2] [6]
5 3 [3] [5]
4 [4]
例
碁石のような表裏が区別されない（色が同じ）場合、
表 ● 裏 ●
○ ● → ● ○
● ○ ○ ●
○ ○
鏡映変換である。
オセロのような表裏が区別される（色が異なる）場合、
表 ● 裏 ○
○ ● → ○ ●
● ○ ● ○
○ ●
並びの順序（石の位置）は、鏡映変換である。
b(c)またはc(b)で可能である。
円順列
LET N=2 !n種類の色を着けた（オセロの）石
LET R=4 !重複を許してr個選ぶ
LET M=2*COMB(N,2) !m種類の石
LET B=M^R !一列に並べたときの「場合の数」 ※M進法R桁
DIM F(0 TO B-1) !篩い
MAT F=(-1)*CON
LET C=0 !個数
FOR i=0 TO B-1 !小さい順に篩いにかける
IF F(i)<0 THEN
LET W=i !円順列 ※並びを回転させる
FOR K=0 TO R-1
LET T=MOD(W,B)+INT(W/B) !左ローテイト
IF T<>i THEN LET F(T)=i !自分自身（=最小値）は残す
!表 1 裏 [1]
! 5 2 → [2] [5]
! 4 3 [3] [4]
LET V=T !下から見る、輪全体として反転する (12345)→([1][5][4][3][2])
LET T=0
FOR J=1 TO R-1 !M進法(R-1)桁
LET T=T*M+( (M-1)-MOD(V,M) ) !※桁の反転
LET V=INT(V/M)
NEXT J
LET T=T+( (M-1)-V )*M^(R-1) !最上位(MSB) ※桁の反転
IF T<>i THEN LET F(T)=i
LET W=W*M !次へ
NEXT K
LET C=C+1 !結果を表示する
PRINT STR$(C);":"; i; "(";
FOR K=i+1 TO B-1 !同一視するもの
IF F(K)=i THEN PRINT K;
NEXT K
PRINT ")"
END IF
NEXT i
END
|
|