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

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

問題（１）の考察３

' << SE111.bas >>
' 問題（１）の考察３に基づく部分順列生成プログラム。
' Tiny Basic
'
Public A(9)   ' 部分順列を保存する配列。
Public N      ' 要素数。
Public R      ' 取り出す要素数。
Public COUNT  ' 生成された部分順列の個数。
Public P(9,9) ' P(K,I)は、深さKにおいて、K+1番目の要素と
'             ' 交換する位置を意味する。
Do
  ' N,R,配列Pの読み込み。
  Read N,R
  If (N <= 0) or (R > N) Then Exit Do 
  For K=0 To R-1
    For I=K+1 To N: Read P(K,I): Next I
  Next K
  '
  Data 4,4, 
  Data 1,2,3,4, 4,3,2, 3,4, 4
  Data 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
  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: Print"   ";: Next I
    For I=K+1 To N: Print Using"###";P(K,I);: Next I
    Print
  Next K
  Print
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の節点から深さK+1の子節点 N-K個を生成する。
  For I=K+1 To N  
    J=P(K,I)
    ' J番目とK+1番目の要素を交換する。
    W=A(J): A(J)=A(K+1): A(K+1)=W  
    ' 深さK+1の子節点を作成する。
    Call Perm(K+1) 
    ' 交換を戻す。          
    W=A(J): A(J)=A(K+1): A(K+1)=W   
  Next I
End Sub