十進BASIC 第2掲示板 過去ログ

!置換（Permutation）の計算
!※技術メモ
!　A=┌ 1 2 3 4 ┐=(1 2 4 3)　※１行目の順番は固定とする
!　　└ 2 4 1 3 ┘
!の場合、
!　DATA 2,4,1,3 !配列変数の「添え字と値」に対応させる
!　MAT READ A
!とプログラムでは記述する。

SUB PermPrintOut(A()) !表示する　※標準形（２行ｎ列の行列表記する）
   MAT PRINT USING(REPEAT$(" ##",UBOUND(A))): A;
   PRINT
END SUB
SUB PermIdentity(A()) !恒等置換
   FOR i=1 TO UBOUND(A)
      LET  A(i)=i
   NEXT i
END SUB
SUB PermInverse(A(), iA()) !逆置換　※iAはA以外の配列を指定すること
   FOR i=1 TO UBOUND(A)
      LET  iA(A(i))=i
   NEXT i
END SUB
SUB PermMultiply(A(),B(), AB()) !積AB　※ABはAかつB以外の配列を指定すること
   LET  ua=UBOUND(A)
   LET  ub=UBOUND(B)
   IF ua=ub THEN
      FOR i=1 TO ua
         LET  AB(i)=A(B(i)) !※合成写像(AB)(i)=A(B(i))
      NEXT i
   ELSE
      PRINT "次元が違います。A=";ua;" B=";ub
      STOP
   END IF
END SUB

SUB PermReverse(A()) !並び順を反転させる
   LET  ua=UBOUND(A)
   FOR i=1 TO INT(ua/2)
      swap A(i),A(ua-i+1)
   NEXT i
END SUB
!-------------------- ここまでがサブルーチン



!main

LET N=12 !※固定

DIM cc(N)
SUB check(SS(),HH()) !参照を確認する　※共に連番で表示されればＯＫ
   PRINT "check!"
   CALL PermMultiply(HH,SS,cc) !AB=BA=I　※恒等置換
   CALL PermPrintOut(cc)

   CALL PermMultiply(SS,HH,cc)
   CALL PermPrintOut(cc)
END SUB


DIM Rev(N) !反転に相当する置換
CALL PermIdentity(Rev)
CALL PermReverse(Rev)

DIM shuffle(N) !リフルシャッフルに相当する置換
DATA 2,4,6,8,10,12,1,3,5,7,9,11
MAT READ shuffle


DIM H(N),S(N) !ハート、スペードの束

FOR R1=1 TO N !前半のマジックでの「好きな数」

   PRINT "----- Request";R1;"の場合-----"

   !●スペードをシャッフルする
   DIM B(N),c(N)
   CALL PermIdentity(B) !初期値
   FOR k=1 TO 12 !回数　※何回か実行すると元に戻る
      LET S(k)=B(R1)
      CALL PermMultiply(B,shuffle,c)
      MAT B=c
   NEXT k
   CALL PermInverse(S,H) !SH=HS=Iより

   DIM RH(N)
   CALL PermMultiply(H,Rev,RH) !ハートをＫ（キング）でシャッフルする場合
   !!!CALL PermMultiply(S,Rev,RH) !スペードをＫ（キング）でシャッフルする場合
   !!!MAT S=H


   FOR R2=1 TO N
      PRINT "表";R2;"の場合"

      !●ハートをシャッフルする
      DIM M(N) !後半のマジックでの「好きな数」「山の選択」
      MAT M=ZER
      FOR i=1 TO R2 !R番目
         FOR k=1 TO 12
            LET M(k)=MOD(M(k)+k,13)
         NEXT k
      NEXT i
      !※「山の選択」は、１３を底に移動させる調整カットで無効になるので、このいずれかになる。

      DIM c1(N)
      CALL PermMultiply(RH,M,c1)
      CALL PermPrintOut(c1)

      !●スペードをカットする
      LET KEY2=c1(1) !移動先
      FOR x=1 TO N !現在位置を探す
         IF S(x)=1 THEN EXIT FOR
      NEXT x
      PRINT x;"から";KEY2;"へ"
      DIM cut(N) !カットに相当する置換
      FOR i=1 TO N
         LET cut(i)=MOD(i+(x-KEY2)-1,12)+1
      NEXT i
      !!!MAT PRINT cut;
      DIM c2(N)
      CALL PermMultiply(S,cut,c2)
      CALL PermPrintOut(c2)

      CALL check(c1,c2)
   NEXT R2

NEXT R1

END



!-----前半のマジックでの「好きな数」が 1 の場合のシャッフル結果-----
!DATA 1, 2, 5, 3,10, 6,12, 4, 9,11, 8, 7 !ハート
!DATA 1, 2, 4, 8, 3, 6,12,11, 9, 5,10, 7 !スペード
!----- 2 の場合-----
!DATA 12, 1, 4, 2, 9, 5,11, 3, 8,10, 7, 6
!DATA  2, 4, 8, 3, 6,12,11, 9, 5,10, 7, 1
!----- 3 の場合-----
!DATA 9,10, 1,11, 6, 2, 8,12, 5, 7, 4, 3
!DATA 3, 6,12,11, 9, 5,10, 7, 1, 2, 4, 8
!----- 4 の場合-----
!DATA 11,12, 3, 1, 8, 4,10, 2, 7, 9, 6, 5
!DATA  4, 8, 3, 6,12,11, 9, 5,10, 7, 1, 2
!----- 5 の場合-----
!DATA 4, 5, 8, 6, 1, 9, 3, 7,12, 2,11,10 !※代替として混ざられる位置
!DATA 5,10, 7, 1, 2, 4, 8, 3, 6,12,11, 9 !※捨て場へ移される順
!----- 6 の場合-----
!DATA 8, 9,12,10, 5, 1, 7,11, 4, 6, 3, 2
!DATA 6,12,11, 9, 5,10, 7, 1, 2, 4, 8, 3
!----- 7 の場合-----
!DATA 2, 3, 6, 4,11, 7, 1, 5,10,12, 9, 8
!DATA 7, 1, 2, 4, 8, 3, 6,12,11, 9, 5,10
!----- 8 の場合-----
!DATA 10,11, 2,12, 7, 3, 9, 1, 6, 8, 5, 4
!DATA  8, 3, 6,12,11, 9, 5,10, 7, 1, 2, 4
!----- 9 の場合-----
!DATA 5, 6, 9, 7, 2,10, 4, 8, 1, 3, 12,11
!DATA 9, 5,10, 7, 1, 2, 4, 8, 3, 6, 12,11
!----- 10 の場合-----
!DATA  3, 4, 7, 5,12, 8, 2, 6,11, 1,10, 9
!DATA 10, 7, 1, 2, 4, 8, 3, 6,12,11, 9, 5
!----- 11 の場合-----
!DATA  6, 7,10, 8, 3,11, 5, 9, 2, 4, 1,12
!DATA 11, 9, 5,10, 7, 1, 2, 4, 8, 3, 6,12
!----- 12 の場合-----
!DATA  7, 8,11, 9, 4,12, 6,10, 3, 5, 2, 1
!DATA 12,11, 9, 5,10, 7, 1, 2, 4, 8, 3, 6




!後半のマジックでのシャッフルに相当する置換
!DATA  1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12 !「１３でのシャッフル」
!DATA  2, 4, 6, 8,10,12, 1, 3, 5, 7, 9,11
!DATA  3, 6, 9,12, 2, 5, 8,11, 1, 4, 7,10
!DATA  4, 8,12, 3, 7,11, 2, 6,10, 1, 5, 9
!DATA  5,10, 2, 7,12, 4, 9, 1, 6,11, 3, 8
!DATA  6,12, 5,11, 4,10, 3, 9, 2, 8, 1, 7
!DATA  7, 1, 8, 2, 9, 3,10, 4,11, 5,12, 6
!DATA  8, 3,11, 6, 1, 9, 4,12, 7, 2,10, 5
!DATA  9, 5, 1,10, 6, 2,11, 7, 3,12, 8, 4
!DATA 10, 7, 4, 1,11, 8, 5, 2,12, 9, 6, 3
!DATA 11, 9, 7, 5, 3, 1,12,10, 8, 6, 4, 2
!DATA 12,11,10, 9, 8, 7, 6, 5, 4, 3, 2, 1