順列生成（多段順列）問題（３）の考察１を示します。
問題（３）の考察１
' << MP311.bas >>
' 集合{1,2,…,n}上のm段r部分順列の生成（非辞書式順序）
' Tiny Basic
'
Public P(10,10) ' m段r部分順列を保存する配列。
Public N ' 集合の要素数。
Public R ' 部分順列の長さ。
Public M ' 段数。
Public BI ' ブロックの行方向の幅。
PublIc BJ ' ブロックの列方向の幅。
Public COUNT ' 条件を満たす配置の個数。
Public X(10,10) ' 列jに要素yが出現しているとき、x[j][y]=1,
' 出現していないとき、x[j][y]=0
Public B(10,10) ' ブロックkに要素yが出現しているとき、b[k][y]=1,
' 出現していないとき、b[k][y]=0
Do
' N,R,M,BI,BJの読み込み。*/
Read N,R,M,BI,BJ
If (N <= 0) or (N > 10) Then Exit Do
Data 4,4,4,2,2
Data 0,0,0,0,0
'
' 配列Pの初期設定。
For I=1 To M
For J=1 To N: P(I,J)=J: Next J
Next I
'
' 配列Xの初期設定。
For J=1 To R
For Y=1 To N: X(J,Y)=0: Next Y
Next J
'
' 配列Bの初期設定。
For J=1 To N
For Y=1 To N: B(J,Y)=0: Next Y
Next J
'
' 初期設定。
COUNT=0
'
' m段r部分順列生成。
Call Mperm(1,0)
'
' 結果の出力
Print Using"N=## R=## M=## BI=## BJ=## ";N;R;M;BI;BJ
Print "COUNT=";COUNT
Loop
End
'
' D:段数 K:深さ
Sub Mperm(D,K)
If D > M Then
' 解の出力
COUNT=COUNT+1
Print "[";COUNT;"]"
For I=1 To M
For J=1 To R: Print Using"##";P(I,J);: Next J
Print
Next I
Print
Exit Sub
End If
'
If K = R Then
'次の段に進む。
Call Mperm(D+1,0)
Else
' D段目の部分順列中、
' 深さKの節点から深さK+1の子節点 N-K個を生成する。
For I=K+1 To N
T=P(D,I)
'
' D段目K+1列に要素Tが重複出現している場合,次の要素に進める。
If X(K+1,T) = 1 Then Goto *LAB
'
S=Int((D-1)/BI)*BI + Int(K/BJ) + 1
' ブロックSに要素Tが重複出現している場合,次の要素に進める。
If B(S,T) = 1 Then Goto *LAB
'
X(K+1,T)=1
B(S,T)=1
' I番目とK+1番目の要素を交換する。
W=P(D,I): P(D,I)=P(D,K+1): P(D,K+1)=W
' 深さK+1の子節点を作成する。
Call Mperm(D,K+1)
' 交換を戻す。
W=P(D,I): P(D,I)=P(D,K+1): P(D,K+1)=W
X(K+1,T)=0
B(S,T)=0
*LAB:
Next I
End If
End Sub
