順列生成(多段順列)問題(4)の考察2を示します。
問題(4)の考察2
' << MP421.bas >> ' m段r部分順列の生成(非辞書式順序) ' Tiny Basic ' Public P(10,100) ' m段r部分順列を保存する配列。 Public B(100) ' B[k]=1:数字kが出現しているとき。 ' B[k]=0:数字kが出現していないとき。 Public N ' 集合の要素数。 Public M ' 段数。 Public COUNT ' m段r部分順列の個数。 ' Do ' N,Mの読み込み。 Read N,M If (N <= 0) or (N > 10) Then Exit Do Data 3,3 Data 0,0 ' ' 配列Pの初期設定。 For I=1 To M For J=0 To M*N: P(I,J)=J: Next J Next I ' ' 配列Bの初期設定。 For K=1 To M*N: B(K)=0: Next K ' ' 初期設定。 COUNT=0 ' ' m段r部分順列生成。 Call Mperm(1,0) ' ' 結果の出力 Print Using"N=## M=##";N;M Print "COUNT=";COUNT Loop End ' ' D:段数 K:深さ Sub Mperm(D,K) If D > M Then ' m段n部分順列の表示。 COUNT=COUNT+1 Print "[";COUNT;"]" For I=1 To M For J=1 To N: Print Using"##";P(I,J);: Next J Print Next I Print Exit Sub End If ' If K = N Then '次の段に進む。 Call Mperm(D+1,0) Else ' D段目の部分順列中、 ' 深さKの節点から深さK+1の子節点 N-K個を生成する。 For I=K+1 To M*N T=P(D,I) ' ' 要素Tが重複出現している場合、次の要素に進む。 If B(T) = 1 Then Goto *LAB ' 条件(a)を満たさない場合、次の要素に進む。 If P(D,K) > T Then Goto *LAB ' ' 条件(b)を満たさない場合、次の要素に進む。 If (D > 1) and (P(D-1,K+1) > T) Then Goto *LAB ' B(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 B(T)=0 *LAB: Next I End If End Sub