つづき

つづき

SUB PermTranspositionForm(A(), C(,),n) !互換の積の形へ　※C(n,)…C(2,)C(1,)
DIM tmpA(100)
FOR i=1 TO UBOUND(A) !作業変数へ
LET tmpA(i)=A(i)
NEXT i
LET n=0
FOR i=1 TO UBOUND(A)
FOR j=1 TO UBOUND(A)-1
IF tmpA(j)>tmpA(j+1) THEN !隣接交換
LET tmp=tmpA(j)
LET tmpA(j)=tmpA(j+1)
LET tmpA(j+1)=tmp

LET n=n+1 !次の組へ
LET C(n,1)=j
LET C(n,2)=j+1
LET C(n,3)=-1 !終端記号
END IF
NEXT j
NEXT i
FOR i=1 TO INT(n/2) !反転
FOR j=1 TO 3 !UBOUND(C,2)
LET tmp=C(i,j)
LET C(i,j)=C(n-i+1,j)
LET C(n-i+1,j)=tmp
NEXT j
NEXT i
END SUB

!巡回置換
SUB PermCopy(n,Q(,),A()) !巡回置換の１組を得る
FOR j=1 TO UBOUND(A)
LET A(j)=Q(n,j)
NEXT j
IF Q(n,j)<0 THEN !終端記号なら
ELSE
PRINT "次元が違います。長さ=";j-1
STOP
END IF
END SUB
SUB PermCyclic(C(),A()) !巡回置換の標準形を得る
CALL PermIdentity(A)
FOR i=1 TO UBOUND(C)-1
LET A(C(i))=C(i+1)
NEXT i
LET A(C(i))=C(1)
END SUB
FUNCTION PermCyclicSign(C()) !巡回置換の符号を得る
LET PermCyclicSign=(-1)^(UBOUND(C)-1)
END FUNCTION

!互換
SUB PermTransposition(a,b, C()) !互換の標準形を得る
CALL PermIdentity(C)
LET C(a)=b
LET C(b)=a
END SUB
!-------------------- ここまでがサブルーチン

!main

!A=┌ 1 2 3 4 ┐=(1 2 4 3)　※１行目の順番は固定とする
!　└ 2 4 1 3 ┘
DATA 2,4,1,3 !配列変数の「添え字と値」に対応させる
DIM A(4)
MAT READ A

CALL PermPrintOut(A)
DIM Q5(5,5)
CALL PermCyclicForm(A, Q5,n) !巡回置換の積へ
CALL PermCyclicMultiplyPrintOut(n,Q5)
PRINT PermSign(A) !符号

!B=┌ 1 2 3 4 ┐=(1 2 3)
!　└ 2 3 1 4 ┘
DATA 2,3,1,4
DIM B(4)
MAT READ B

CALL PermPrintOut(B)
CALL PermCyclicForm(B, Q5,n) !巡回置換の積へ
CALL PermCyclicMultiplyPrintOut(n,Q5)
PRINT PermSign(B)

DIM C(4)
CALL PermMultiply(A,B,C) !積AB
CALL PermPrintOut(C)

DIM InvB(4)
CALL PermInverse(B,InvB) !逆置換b
CALL PermPrintOut(InvB)

CALL PermMultiply(B,InvB, C) !Bb=E
CALL PermPrintOut(C)

END

Re: 置換（Permutation）の計算	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/10/30 11:39:25 ** この記事は1回修正されてます
つづき SUB PermTranspositionForm(A(), C(,),n) !互換の積の形へ　※C(n,)…C(2,)C(1,) DIM tmpA(100) FOR i=1 TO UBOUND(A) !作業変数へ LET tmpA(i)=A(i) NEXT i LET n=0 FOR i=1 TO UBOUND(A) FOR j=1 TO UBOUND(A)-1 IF tmpA(j)>tmpA(j+1) THEN !隣接交換 LET tmp=tmpA(j) LET tmpA(j)=tmpA(j+1) LET tmpA(j+1)=tmp LET n=n+1 !次の組へ LET C(n,1)=j LET C(n,2)=j+1 LET C(n,3)=-1 !終端記号 END IF NEXT j NEXT i FOR i=1 TO INT(n/2) !反転 FOR j=1 TO 3 !UBOUND(C,2) LET tmp=C(i,j) LET C(i,j)=C(n-i+1,j) LET C(n-i+1,j)=tmp NEXT j NEXT i END SUB !巡回置換 SUB PermCopy(n,Q(,),A()) !巡回置換の１組を得る FOR j=1 TO UBOUND(A) LET A(j)=Q(n,j) NEXT j IF Q(n,j)<0 THEN !終端記号なら ELSE PRINT "次元が違います。長さ=";j-1 STOP END IF END SUB SUB PermCyclic(C(),A()) !巡回置換の標準形を得る CALL PermIdentity(A) FOR i=1 TO UBOUND(C)-1 LET A(C(i))=C(i+1) NEXT i LET A(C(i))=C(1) END SUB FUNCTION PermCyclicSign(C()) !巡回置換の符号を得る LET PermCyclicSign=(-1)^(UBOUND(C)-1) END FUNCTION !互換 SUB PermTransposition(a,b, C()) !互換の標準形を得る CALL PermIdentity(C) LET C(a)=b LET C(b)=a END SUB !-------------------- ここまでがサブルーチン !main !A=┌ 1 2 3 4 ┐=(1 2 4 3)　※１行目の順番は固定とする !　└ 2 4 1 3 ┘ DATA 2,4,1,3 !配列変数の「添え字と値」に対応させる DIM A(4) MAT READ A CALL PermPrintOut(A) DIM Q5(5,5) CALL PermCyclicForm(A, Q5,n) !巡回置換の積へ CALL PermCyclicMultiplyPrintOut(n,Q5) PRINT PermSign(A) !符号 !B=┌ 1 2 3 4 ┐=(1 2 3) !　└ 2 3 1 4 ┘ DATA 2,3,1,4 DIM B(4) MAT READ B CALL PermPrintOut(B) CALL PermCyclicForm(B, Q5,n) !巡回置換の積へ CALL PermCyclicMultiplyPrintOut(n,Q5) PRINT PermSign(B) DIM C(4) CALL PermMultiply(A,B,C) !積AB CALL PermPrintOut(C) DIM InvB(4) CALL PermInverse(B,InvB) !逆置換b CALL PermPrintOut(InvB) CALL PermMultiply(B,InvB, C) !Bb=E CALL PermPrintOut(C) END