|
|
> No.3191[元記事へ]
!途中のｋ番目、１回分だけのプログラムで、
! Permutation(n,r) 全体を処理する方法 ６通りほど、まとめてみた
! 先の・・・で、変数名が、mPr と、n= 中間ポインター になっていたが、
!
!●● 通常の変数名、 nPr と、k= 中間ポインター に、全て変更した ●●
!順列 Permutation nPr P(n,r)
!---------------------
! 入力数列 a() の準備
!---------------------
LET n=3
LET r=2
DIM a(n)
!
FOR i=1 TO n
LET a(i)=i
NEXT i
!----------------------------------------------------------
! 出力１行。速度を測るときは、MAT PRINT を削除( 先頭に"!")
!----------------------------------------------------------
SUB output1p
MAT PRINT USING REPEAT$("## ",r)& " 配列の残り(無視)→"& REPEAT$("## ",n-r) :a
END SUB
!----------------------------------------
!(No_print, n=9,r=9 の所要時間)@P3_500MHz
!-------perm00 27.08 sec.
!-------perm50 25.15 sec.
!-------perm10 19.88 sec.
!-------perm40 15.82 sec.
!-------perm20 12.03 sec.
!-------perm30 9.83 sec.
!(No_print, n=8,r=8 の所要時間)@P3_500MHz
!-------perm00 3.02 sec.
!-------perm50 2.75 sec.
!-------perm10 2.2 sec.
!-------perm40 1.76 sec.
!-------perm20 1.37 sec.
!-------perm30 1.1 sec.
!------------------------------------------------------------
!各文の引数から、a() が消え、k のみになっているが、
!元々 a() は、local(局所変数)でないので、問題を簡単にするため
!------------------------------------------------------------
!
MAT PRINT USING REPEAT$("## ",n) :a !入力数列 a()表示。
LET t0=TIME
CALL perm00(1) !( k の初期値=1)
PRINT "-------perm00 ";TIME-t0;"sec."
PRINT
!
MAT PRINT USING REPEAT$("## ",n) :a !入力数列 a()表示。先プログラムでの a() 保存 検査
LET t0=TIME
CALL perm50(1) !( k の初期値=1)
PRINT "-------perm50 ";TIME-t0;"sec."
PRINT
!
MAT PRINT USING REPEAT$("## ",n) :a !入力数列 a()表示。先プログラムでの a() 保存 検査
LET t0=TIME
CALL perm10(1) !( k の初期値=1)
PRINT "-------perm10 ";TIME-t0;"sec."
PRINT
!
MAT PRINT USING REPEAT$("## ",n) :a !入力数列 a()表示。先プログラムでの a() 保存 検査
LET t0=TIME
CALL perm40(1) !( k の初期値=1)
PRINT "-------perm40 ";TIME-t0;"sec."
PRINT
!
MAT PRINT USING REPEAT$("## ",n) :a !入力数列 a()表示。先プログラムでの a() 保存 検査
LET t0=TIME
CALL perm20(1) !( k の初期値=1)
PRINT "-------perm20 ";TIME-t0;"sec."
PRINT
!
MAT PRINT USING REPEAT$("## ",n) :a !入力数列 a()表示。先プログラムでの a() 保存 検査
LET t0=TIME
CALL perm30(1) !( k の初期値=1)
PRINT "-------perm30 ";TIME-t0;"sec."
PRINT
!
MAT PRINT USING REPEAT$("## ",n) :a !入力数列 a()表示。先プログラムでの a() 保存 検査
!----------------------------------------
!１回毎に、右左rotate 復元しながら、一巡。
!----------------------------------------
SUB perm00(k)
local i
IF r< k THEN
CALL output1p
ELSE
FOR i=k TO n
! !-------- !rotate Right 1
LET t=a(i) ! ┌── ← ──┐
FOR j=i-1 TO k STEP -1 ! a(k)・・→・・a(i)
LET a(j+1)=a(j)
NEXT j
LET a(k)=t
!--------
CALL perm00(k+1)
!-------- !rotate Left 1
LET t=a(k) ! ┌── → ──┐
FOR j=k TO i-1 ! a(k)・・←・・a(i)
LET a(j)=a(j+1)
NEXT j
LET a(i)=t
!--------
NEXT i
END IF
END SUB
!------------------------------------------------------------------
! 毎回、右左rotate で復元せず、RETURN までに１巡復元すればよいので、
! rotate １回( rotate の左右方向は、何れかに固定できればよい)
!------------------------------------------------------------------
SUB perm10(k)
local i
IF r< k THEN
CALL output1p
ELSE
FOR i=k TO n
CALL perm10(k+1)
!-------- !rotate Left 1
LET t=a(k) ! ┌── → ──┐
FOR j=k TO n-1 ! a(k)・・←・・a(n)
LET a(j)=a(j+1)
NEXT j
LET a(n)=t
!--------
NEXT i
END IF
END SUB
!------------------------------------------------------------------
! 一巡の要求は、先頭ｋ位置だけで、k+1 ～n は、その残りであればよく、
! 先頭位置・巡回位置の、交換(swap)・復元(swap)を、順番に行なう方法。
! rotate のように全桁の移送をしないため、高速になる。
!------------------------------------------------------------------
SUB perm20(k)
local i
IF r< k THEN
CALL output1p
ELSE
FOR i=k TO n
swap a(k),a(i)
CALL perm20(k+1)
swap a(k),a(i)
NEXT i
END IF
END SUB
!-----------------------------------------------------------------------
! perm20 の高速化。最初の 交換(k,k)・復元(k,k) が無駄で k+1 からに。最速
!-----------------------------------------------------------------------
SUB perm30(k)
local i
IF r< k THEN
CALL output1p
ELSE
CALL perm30(k+1)
FOR i=k+1 TO n
swap a(k),a(i)
CALL perm30(k+1)
swap a(k),a(i)
NEXT i
END IF
END SUB
!---------------------------------------------------------
! Perm30 の swap を１回で巡回させ、最後に rotate１回で補修
!---------------------------------------------------------
SUB perm40(k)
local i
IF r< k THEN
CALL output1p
ELSE
CALL perm40(k+1)
FOR i=k+1 TO n
swap a(k),a(i)
CALL perm40(k+1)
NEXT i
!-------- !rotate Left 1
LET t=a(k) ! ┌── → ──┐
FOR j=k TO n-1 ! a(k)・・←・・a(n)
LET a(j)=a(j+1)
NEXT j
LET a(n)=t
!--------
END IF
END SUB
!---------------------------------------------------------------------
! 保存無し 巡回だけなら、Perm40 の様に swap１回にして、別の b() で保存
!---------------------------------------------------------------------
SUB perm50(k)
local i,b(10) !b()の添字は、変数不可なので大きめ
IF r< k THEN
CALL output1p
ELSE
MAT b=a
CALL perm50(k+1)
FOR i=k+1 TO n
swap a(k),a(i)
CALL perm50(k+1)
NEXT i
MAT a=b
END IF
END SUB
END
|
|