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

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

問題（４）の考察１

' << SE401.bas >>
' 問題（４）の考察１に基づく部分順列生成プログラム
' Tiny Basic
'
Public A(9)   ' 部分順列を保存する配列。
Public B(9)   ' 深さKの節点の順番。
Public N      ' 要素数。
Public R      ' 取り出す要素数。
Public COUNT  ' 生成された部分順列の個数。
Public P(9,9) ' P(K,I)は、深さKの節点で、確定していく要素の
              ' 配列Aでの位置を保存する。
'
Do
  ' N,Rの読み込み。
  Read N,R
  If (N <= 0) or (R > N) Then Exit Do 
  Data 2,2, 3,3, 4,4
  Data 0,0
  '
  ' 初期設定。
  For I=1 To N: A(I)=I: Next I
  COUNT=0
  For I=0 To N: B(I)=0: Next I
  '
  ' 部分順列生成。
  Call Perm(0)
  '
  ' 結果の表示。
  Print Using"N=## R=## COUNT=######";N;R;COUNT
Loop
End
'
' 部分順列を生成する再帰手続き。
' Kは木の深さを表す。
Sub Perm(K)
  Dim PS(9) ' PS(E)は要素Eが存在する配列A内での位置を保存する。
  '
  ' 生成された順列の表示。
  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
  '
  ' {A(K+1),A(K+2),…,A(N)}の各要素Eに対して、
  ' 配列A内の位置PS(E)を求める。
  For E=1 To N: PS(E)=0: Next E
  For I=K+1 To N: PS(A(I))=I: Next I
  '
  B(K)=B(K)+1
  ' B(K)が奇数なら昇順に取り出し、偶数なら降順に取り出す。
  If B(K) Mod 2 = 1 Then
    ' 配列Pに昇順に取り出す配列Aの位置を保存する。
    I=K+1
    For E=1 To N
      If PS(E) > 0 Then
        P(K,I)=PS(E): I=I+1
      End IF
    Next E
  Else
    ' 配列Pに降順に取り出す配列Aの位置を保存する。
    I=K+1
    For E=N To 1 Step -1
      If PS(E) > 0 Then
        P(K,I)=PS(E): I=I+1
      End IF
    Next E
  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