順列生成（交換法）問題（２）の考察３

　順列生成（交換法）問題（２）の考察３を示します。

問題（２）の考察３


○問題（２）の考察３に基づく順列生成プログラム

' << CH211.bas >>
' 問題（２）の考察３に基づく順列生成プログラム。
' Tiny Basic
'
Public A(9)   ' 順列を保存する配列。
Public N      ' 要素数。
Public COUNT  ' 生成された順列の個数。
Public P(9,9) ' P(K,I)：深さKにおいて、
              ' 要素K+1を交換する位置。
'
Do
  ' Nの読み込み。
  Read N
  If (N <= 0) Or (N > 9) Then Exit Do
  For K=0 To N-1
    For J=1 To K+1: Read P(K,J): Next J
  Next K
  Data 4, 1, 1,2, 3,2,1, 1,2,3,4
  Data 0
  '
  ' 初期設定。
  COUNT=0
  '
  ' 順列生成。
  Call Perm(0)
  '
  ' 結果の表示。
  Print Using"N=##  COUNT=######";N;COUNT
  Print"配列P"
  Print"   ";
  For J=1 To N: Print Using"###";J;: Next J
  Print
  For K=0 To N-1
    Print Using"##:";K;
    For J=1 To K+1
      Print Using"###";P(K,J); 
    Next J
    Print
  Next K
Loop
End
'
' 順列を生成する再帰手続き。
' Kは木の深さを表す。
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
  '
  ' 深さKのK+1個の子節点を生成する。
  For I=1 To K+1
    J=P(K,I)
    ' K+1番目の要素K+1をJ番目と交換。
    A(K+1)=A(J): A(J)=K+1
    ' 深さK+1の子節点を作成する。
    Call Perm(K+1)
    ' 状態を戻す。
    A(J)=A(K+1)
  Next I
End Sub