順列生成（選択法）問題（２）の考察１

　順列生成（選択法）問題（２）の考察１を示します。

問題（２）考察１

' << SE201.bas >>
' 問題（２）の考察１に基づく部分順列生成プログラム
' Tiny Basic
'
Public A(9)  ' 部分順列を保存する配列。
Public N     ' 要素数。
Public R     ' 取り出す要素数。
Public COUNT ' 生成された部分順列の個数。
'
Do
  ' N,Rの読み込み。
  Read N,R
  If (N <= 0) or (R > N) Then Exit Do 
  Data 5,3, 0,0
  '
  ' 初期設定。
  For I=1 To N: A(I)=I: Next I
  COUNT=0
  '
  ' 部分順列生成。
  Call Perm(0)
  '
  ' 結果の表示。
  Print Using"N=## R=## COUNT=######";N;R;COUNT
Loop
End
'
' 部分順列を生成する再帰手続き。
' Kは木の深さを表す。
Sub Perm(K)
  ' 生成された部分順列の表示。
  If( K = R ) Then  
    COUNT=COUNT+1
    Print Using"###: ";COUNT;
    For I=1 To R: Print Using"##";A(I);: Next I
    Print
    Exit Sub
  End If

  ' 深さKにおいて、N-K個の子節点を生成する。
  ' 深さK+1の子節点を作成する。
  Call Perm(K+1) 
  For I=K+2 To N  
    ' K番目からN番目まで左巡回シフト。
    W=A(K+1)
    For J=K+2 To N: A(J-1)=A(J): Next J
    A(N)=W   
    ' 深さK+1の子節点を作成する。
    Call Perm(K+1) 
  Next I
  '
  ' 左巡回シフトを行い親節点の状態に戻す。          
  W=A(K+1)
  For J=K+2 To N: A(J-1)=A(J): Next J
  A(N)=W
End Sub