順列生成（巡回シフト法）問題（４）の考察１

　順列生成（巡回シフト法）問題（４）の考察１を示します。

問題（４）の考察１

' << CS401.bas >>
' 問題（４）の考察１に基づく順列生成プログラム。
' Tiny Basic
'
Public A(9)  ' 順列を保存する配列。
Public B(9)  ' 深さKの節点が生成される順序。
Public N     ' 要素数。
Public COUNT ' 生成された順列の個数。
'
Do
  ' Nの読み込み。
  Read N
  If N <= 0 Then Exit Do 
  Data 1,2,3,4, 0
  '
  ' 初期設定。
  A(1)=1
  COUNT=0
  For I=0 To N: B(I)=0: Next I
  '
  ' 順列生成。
  Call Perm(0)
  '
  ' 結果の表示。
  Print Using"N=##  COUNT=######";N;COUNT
Loop
End
'
' 順列を生成する再帰手続き。
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)は、深さKの節点が生成される順序。
  B(K)=B(K)+1
  '
  If B(K) Mod 2 = 1 Then
    ' B(K)が奇数の場合、要素K+1を末尾から先頭へ巡回シフトしていく。
    ' 深さK+1のK+1個の節点を生成する。                  
    '
    A(K+1)=K+1
    Call Perm(K+1)
    '
    For I=1 To K
      ' 一つ左へ巡回シフトする。先頭の要素は末尾に移動する。
      For J=1 To K+1: A(J-1)=A(J): Next J
      A(K+1)=A(0)
      ' 子節点を作成する。
      Call Perm(K+1)
    Next I
    '
    ' 状態を戻す。
    For J=2 To K+1: A(J-1)=A(J): Next J
  Else
    ' B(K)が偶数の場合、要素K+1を末尾から先頭へ巡回シフトしていく。
    ' 深さKの節点から子節点 K+1個を生成する。

    For J=K To 1 Step -1: A(J+1)=A(J): Next J
    A(1)=K+1
    Call Perm(K+1)
    '
    For I=1 To K
      ' 一つ右へ巡回シフトする。末尾の要素は先頭に移動する。
      A(0)=A(K+1)
      For J=K To 1 Step -1: A(J+1)=A(J): Next J
      A(1)=A(0)
      ' 子節点を作成する。
      Call Perm(K+1)
    Next I
  End If
End Sub