|
|
問題
1からnまでの数字が書かれたn枚のカードを並べ替えて、n!通りの順列を求めてください。
答え
・挿入法
手順の確認
1を並べる。
①
2を並べる。1の前後に挿入する。
②1、1②
3を並べる。たとえば、21の並びなら、○2○1○の3か所に挿入する。
21に対して、③21、2③1、21③
12に対して、③12、1③2、12③
4を並べる。
321に対して、④321、3④21、32④1、321④
231に対して、④231、2④31、23④1、231④
213に対して、④213、2④13、21④3、213④
312に対して、④312、3④12、31④2、312④
132に対して、④132、1④32、13④2、132④
123に対して、④123、1④23、12④3、123④
（終り）
LET N=4
DIM A(N) !並び
CALL try(1, N,A)
END
EXTERNAL SUB try(K, N,A())
IF K>N THEN
MAT PRINT A; !答え
ELSE
DIM B(N)
LET B(1)=K !kを1番目に挿入する
FOR i=1 TO K-1 !k,a[1],a[2],…,a[k-1] ※a[1..k-1]
LET B(i+1)=A(i)
NEXT i
CALL try(K+1, N,B) !次へ
FOR P=2 TO K !kをp番目に挿入する
LET T=B(P-1) !swap it
LET B(P-1)=B(P)
LET B(P)=T
CALL try(K+1, N,B) !次へ
NEXT P
END IF
END SUB
・並びの反転
手順の確認
(k+1)個の並びを考える。a[1] a[2] … a[k] と a[k+1] に分割される。
0から(k!-1)回で、先頭のk個の並び a[1] a[2] … a[k] の順列を生成する。（辞書順ではない）
具体的には、1≦m＜kとして、m!の倍数のとき、先頭の(m+1)個の並びを反転させる。
最後の並びは、a[k] … a[2] a[1] a[k+1] となる。
続いて、(k!)回目で、a[k+1] a[1] a[2] … a[k]
すなわち、
┌───── ← ────┐
a[k+1] a[1] a[2] … → … a[k]
これを、計(k+1)回繰り返すと、右端がa[k+1] a[k] … a[2] a[1]となって、全順列を生成する。
（終り）
LET N=4
DIM A(N) !並び 1234…n
FOR i=1 TO N
LET A(i)=i
NEXT i
MAT PRINT A;
FOR i=1 TO FACT(N)-1 !場合の数
LET T=i
LET K=2
DO WHILE MOD(T,K)=0
LET T=T/K
LET K=K+1
LOOP
PRINT i;K !debug
CALL Reverse(A,1,K) !先頭のk個
MAT PRINT A;
NEXT i
END
EXTERNAL SUB reverse(A(),L,R) !指定された範囲の並びを逆順にする
LET i=L !左端
LET J=R !右端
DO WHILE i<J !交換位置は半分まで ※全部すると元に戻る
LET t=A(i) !swap it
LET A(i)=A(J)
LET A(J)=t
LET i=i+1 !次へ
LET J=J-1
LOOP
END SUB
|
|