順列生成（挿入法）問題（４）の考察３

　順列生成（挿入法）問題（４）の考察３を示します。

問題（４）の考察３

' << INS411.bas >>
' 問題（４）の考察３に基づく順列生成プログラム。
' Tiny Basic
'
Public A(9)   ' 順列を保存する配列。
Public B(9)   ' 深さKの節点が生成される順序。
Public N      ' 要素数。
Public COUNT  ' 生成された順列の個数。
Public P(9,9) ' 配列P
'
Do
  ' Nの読み込み。
  Read N
  If (N <= 0) Or (N > 9) Then Exit Do 
  ' 配列Pの読み込み。
  For K=0 To N-1
    For I=1 To K+1: Read P(K,I): Next I
  Next K
  Data 1, 1,
  Data 2, 1, 1,2, 
  Data 3, 1, 1,2, 1,2,3
  Data 4, 1, 1,2, 1,2,3, 1,2,3,4
  Data 0
  '
  ' 初期設定。
  COUNT=0
  For K=1 To N: B(K)=0: Next K
  '
  ' 順列生成。
  Call Perm(0)
  '
  ' 結果の表示。
  Print Using"N=##  COUNT=######";N;COUNT
  ' 配列Pの表示。
  Print"配列P"
  Print"   ";
  For I=1 To N: Print Using"###";I;: Next I
  Print
  For K=0 To N-1
    Print Using"##:";K;
    For I=1 To K+1: Print Using"###";P(K,I);: Next I
    Print
  Next K
  Print
Loop
End
'
' 順列を生成する再帰手続き。
' Kは木の深さを表す。
Sub Perm(K)
  ' 生成された順列の表示。
  If( K = N ) Then  
    COUNT=COUNT+1
    Print Using"###: ";COUNT;
    For I=1 To N: Print Using"##";A(I);: Next I
    Print
    Exit Sub
  End If
  '
  B(K)=B(K)+1
  '
  ' 深さKの節点から子節点 K+1個を生成する。
  If B(K) Mod 2 = 1 Then
    ' 木の深さKの節点が奇数の場合
    For I=1 To K+1                              
      Q=P(K,I)                                  
      ' Q番目に要素K+1を挿入する。              
      For J=K To Q Step -1: A(J+1)=A(J): Next J 
      A(Q)=K+1                                  
      ' 子節点を作成する。                      
      Call Perm(K+1)                            
      ' 状態を戻す。                            
      For J=Q To K: A(J)=A(J+1): Next J         
    Next I
  Else
    ' 木の深さKの節点が偶数の場合
    For I=K+1 To 1 Step -1                              
      Q=P(K,I)                                  
      ' Q番目に要素K+1を挿入する。              
      For J=K To Q Step -1: A(J+1)=A(J): Next J 
      A(Q)=K+1                                  
      ' 子節点を作成する。                      
      Call Perm(K+1)                            
      ' 状態を戻す。                            
      For J=Q To K: A(J)=A(J+1): Next J         
    Next I
  End If
End Sub