|
投稿者：GAI
投稿日：2013年10月30日(水)22時01分53秒
|
|
|
|
順列を生成するプログラムで、以下のものをトレースしながらその考え方を理解しようと試みていたんですが、複雑に入り組んでいて特に再帰的構造での動きがいろいろな変数を巧に使い分けられていて、どのような動きになっているのかが解り難い感じでした。
全体的流れの構成や、順列の生成をどの様な考え方で作り出そうとしているのかをプログラムにそって説明して頂けませんでしょうか？
REM 1～nの順列を辞書式順序で生成する。
DECLARE EXTERNAL SUB perm
DIM a(100)
INPUT n
MAT a=ZER(n)
FOR i=1 TO n
LET a(i)=i
NEXT i
CALL perm(a,1)
END
EXTERNAL SUB perm(a(),n)
LET m=UBOUND(a)
IF n=m THEN
MAT PRINT a;
ELSE
FOR i=n TO m
LET t=a(i)
FOR j=i-1 TO n STEP -1
LET a(j+1)=a(j)
NEXT j
LET a(n)=t
CALL perm(a,n+1)
LET t=a(n)
FOR j=n TO i-1
LET a(j)=a(j+1)
NEXT j
LET a(i)=t
NEXT i
END IF
END SUB
|
|
|
|
投稿者：山中和義
投稿日：2013年10月31日(木)10時05分55秒
|
|
|
|
> No.3184[元記事へ]
GAIさんへのお返事です。
> 順列を生成するプログラム
アルゴリズムの本にあります。
サブルーチン perm の処理
先頭から(n-1)までを固定して、その並びから始まる最小のものを用意する（される）。
n
↓
1 i m
□□□□□□□□□
└┘ ← この範囲を右へ1つローテイトさせる
└─┘
└──┘
：
└─────┘
とする。
再帰呼出しされるごとに、辞書式順序で先頭から(n-1)までが確定されていく。
REM 1～nの順列を辞書式順序で生成する。
DECLARE EXTERNAL SUB perm
DIM a(100)
INPUT n
MAT a=ZER(n)
FOR i=1 TO n !並び 1,2,3,4,…,n
LET a(i)=i
NEXT i
CALL perm(a,1)
END
EXTERNAL SUB perm(a(),n)
LET m=UBOUND(a)
!----- debug -----
PRINT REPEAT$(" ",(m+1)*(n-1)); !階層
FOR i=1 TO m !並びを表示する
PRINT STR$(a(i));
NEXT i
PRINT
!----- debug -----
IF n=m THEN !すべて並んだなら
!!MAT PRINT a;
ELSE
FOR i=n TO m !ローテイトする範囲を設定する
LET t=a(i) !右へ1つローテイト
FOR j=i-1 TO n STEP -1
LET a(j+1)=a(j)
NEXT j
LET a(n)=t
CALL perm(a,n+1) !次へ
LET t=a(n) !左へ1つローテイトで元に戻す
FOR j=n TO i-1
LET a(j)=a(j+1)
NEXT j
LET a(i)=t
NEXT i
END IF
END SUB
n=4の場合の実行結果
n=1 n=2 n=3 n=4
? 4
1234
1234
1234
1234
1243
1324
1324
1342
1423
1423
1432
2134
2134
2134
2143
2314
2314
2341
2413
2413
2431
3124
3124
3124
3142
3214
3214
3241
3412
3412
3421
4123
4123
4123
4132
4213
4213
4231
4312
4312
4321
|
|
|
|
投稿者：山中和義
投稿日：2013年10月31日(木)11時13分40秒
|
|
|
|
> No.3186[元記事へ]
つづき
> GAIさんへのお返事です。
>
> > 順列を生成するプログラム
nからiの範囲をローテイトさせる必要がなく、nとiを入れ替えのみで可能です。
ただし、辞書式順序にはなりませんが、代入処理が少ないためやや高速です。
REM 1～nの順列を辞書式順序でなく生成する。
DECLARE EXTERNAL SUB perm
DIM a(100)
INPUT n
MAT a=ZER(n)
FOR i=1 TO n !並び 1,2,3,4,…,n
LET a(i)=i
NEXT i
CALL perm(a,1)
END
EXTERNAL SUB perm(a(),n)
LET m=UBOUND(a)
!----- debug -----
PRINT REPEAT$(" ",(m+1)*(n-1)); !階層
FOR i=1 TO m !並びを表示する
PRINT STR$(a(i));
NEXT i
PRINT
!----- debug -----
IF n=m THEN !すべて並んだなら
!!MAT PRINT a;
ELSE
FOR i=n TO m !箇所を設定する
LET t=a(n) !a[n]とa[i]を入れ替える
LET a(n)=a(i)
LET a(i)=t
CALL perm(a,n+1) !次へ
LET t=a(n) !元に戻す
LET a(n)=a(i)
LET a(i)=t
NEXT i
END IF
END SUB
実行結果
? 4
1234
1234
1234
1234
1243
1324
1324
1342
1432
1432
1423
2134
2134
2134
2143
2314
2314
2341
2431
2431
2413
3214
3214
3214
3241
3124
3124
3142
3412
3412
3421
4231
4231
4231
4213
4321
4321
4312
4132
4132
4123
|
|
|
|
投稿者：SECOND
投稿日：2013年11月 1日(金)05時39分39秒
|
|
|
|
> No.3184[元記事へ]
!左ローテイト１つだけの方法・・・速度は、右左ローテイトより速く、SWAP より遅い。
!●アルゴリズム
! n 番目から、右終点 m 番までを１組に、順列の CALL を受ける。
! n+1 番目から、右終点 m 番までを、次の組として、その順列を、自身へ CALL する。
! これを、rotate left n~m で、先頭を、一順させる ・・・が、プログラムの、ほぼ全部。
!
! 以上の行き着く先は、n+1=m で、組の長さが１になって始めて終端する。
!
! そこでは、各階層での先頭が履歴として、配列 a() の中に、木構造の経路の様に並び、
! １つの順列パターンとなるので、それをプリントして RETURN する。
!
! CALL から戻ったら、
! n+1 番目から、右終点 m 番までの残りも、左ローテイトして先頭へ移し、同様に繰返す。
!
! n 番目から、右終点 m 番の、配列部分は、一順した後、必ず元へ戻るように終了させる。
! 元へ戻っていないと、各階層での CALL~RETURN で、配列が保存されず、一順管理も破綻する。
!------------------------------------------------------------------------------------
LET m=3
DIM a(m)
!
FOR i=1 TO m
LET a(i)=i
NEXT i
CALL perm(a,1) !( m 個の数列, n の初期値)
SUB perm(a(),n)
local i
IF n=m THEN
MAT PRINT USING REPEAT$("## ",m): a
ELSE
FOR i=n TO m
CALL perm(a,n+1)
!-------- !rotate Left 1
LET t=a(n) ! ┌── → ──┐
FOR j=n TO m-1 ! a(n)・・←・・a(m)
LET a(j)=a(j+1)
NEXT j
LET a(m)=t
!--------
NEXT i
END IF
END SUB
END
|
|
|
|
投稿者：SECOND
投稿日：2013年11月 3日(日)17時02分28秒
|
|
|
|
> No.3188[元記事へ]
! m 個から r 個、取る場合は、以下の様に速めに終らせます。
!------------
LET m=4
LET r=2 !m 個から r 個
!
DIM a(m)
FOR i=1 TO m
LET a(i)=i
NEXT i
CALL perm( a,1) !CALL perm_fast( a,1) !速い
SUB perm(a(),n)
local i
IF n >r THEN !● r で、速めに終らせる。
MAT PRINT USING REPEAT$("## ",r)& " 配列の残り(無視)→"& REPEAT$("## ",m-r) :a
ELSE
FOR i=n TO m
CALL perm(a,n+1)
!-------- !rotate Left 1
LET t=a(n) ! ┌── → ──┐
FOR j=n TO m-1 ! a(n)・・←・・a(m)
LET a(j)=a(j+1)
NEXT j
LET a(m)=t
!--------
NEXT i
END IF
END SUB
!-------------------- swap を使った速い方も、同様に・・
SUB perm_fast( a(),n)
local i
IF n<=r THEN
FOR i=n TO m
swap a(n), a(i)
CALL perm_fast( a,n+1)
swap a(n), a(i)
NEXT i
ELSE
MAT PRINT USING REPEAT$("## ",r)& " 配列の残り(無視)→"& REPEAT$("## ",m-r) :a
END IF
END SUB
END
|
|
|
|
投稿者：SECOND
投稿日：2013年11月22日(金)19時43分54秒
|
|
|
|
> 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
|
|
|
戻る