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

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

問題（４）の考察５

' << INS421.bas >>
' 問題（４）の考察５を確認するプログラム。
' Tiny Basic
'
Public A(9)     ' 順列を保存する配列。
Public B(9)     ' 深さKの節点が生成される順序。
Public BB(9)    ' 直前の順列を保存する配列。
Public N        ' 要素数。
Public COUNT    ' 生成された順列の個数。
Public P(10,10) ' 配列P
Public PCOUNT   ' 配列Pのパターンの個数。
Public F(9)     ' 並べ替えられた要素数mの分布。
Dim X(9)        ' 配列Pのすべてのパターンを作成する配列。
'
' Nの読み込み。
Read N
Data 6
Print Using"N=###";N
'
' 配列Pのすべてのパターンを作成するための初期設定。
For K=0 To N-1
  For I=1 To K+1: P(K,I)=I: Next I
Next K
'
PCOUNT=0
For I=1 To N-1: X(I)=0: Next I
'
' 配列Pのすべてのパターン作成
Do
  ' パターンPについて、すべての順列を生成し、
  ' 並べ替えられた要素数mの分布を求める。
  Call CHK()
  '
  Y=1
  Do
    X(Y)=X(Y)+1
    If X(Y) = 1 Then
      For I=Y+1 To 1 Step -1: P(Y,Y+2-I)=I: Next I
      Exit Do
    Else
      X(Y)=0
      For I=1 To Y+1: P(Y,I)=I: Next I
    End If
    Y=Y+1
  Loop
  If Y = N Then Exit Do
Loop
End
'
Sub CHK()
  ' 初期設定。
  COUNT=0
  For K=1 To N: B(K)=0: Next K
  For I=1 To N: F(I)=0: Next I
  '
  ' 順列生成。
  Call Perm(0)
  '
  ' 並べ替えられた要素数mの分布の表示
  PCOUNT=PCOUNT+1
  ' 配列Pの表示。
  Print Using"配列P ####  ";PCOUNT;
  For I=1 To N: Print "  ";F(I);: Next I
  Print
End Sub
'
' 順列を生成する再帰手続き。
' Kは木の深さを表す。
Sub Perm(K)
  If( K = N ) Then  
    COUNT=COUNT+1
    ' 並べ替えられた要素数mの分布を求める。
    If COUNT = 1 Then
      For J=1 To N: BB(J)=A(J): Next J
    Else
      C=0
      For J=1 To N
        If  A(J) <> BB(J) Then C=C+1
      Next J
      F(C)=F(C)+1
      For J=1 To N: BB(J)=A(J): Next J
    End If
    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