順列生成（多段順列）問題（４）の考察１

　順列生成（多段順列）問題（４）の考察１を示します。

問題（４）の考察１

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

      ' 条件(a)(b)を満たさない場合、次の要素に進む。
      If P(D,K) > T Then Goto *LAB
      '
      ' 条件(c)を満たさない場合、次の要素に進む。
      If (D = 2) 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