順列生成（応用）問題（４）の解

　順列生成（応用）問題（４）の解答例を示します。

問題（４）の解

順列生成（応用）問題（４）

　順列生成（応用）問題（４）を紹介します。

問題（４）

順列生成（応用）問題（３）の考察２

　順列生成（応用）問題（３）の考察２を示します。

問題（３）の考察２

' << DE211.bas >>
' 問題（３）の考察２におけるd(n,k)を求めるプログラム。
' Tiny Basic
'
Public A(9)  ' かく乱順列を保存する配列。
Public N     ' 要素数。
Public COUNT ' 生成されたかく乱順列の個数。
Public M(9)  ' M(k)：k番目の要素までで一致した個数。           
Public MC(9) ' MC(i)：要素と位置が一致した数がiとなる回数。
'
Do
  ' Nの読み込み。
  Read N
  If (N <= 0) or (N > 9) Then Exit Do 
  Data 5, 0
  '
  ' 配列Aの初期設定。
  For I=0 To N: A(I)=I: Next I
  '
  ' 配列M,MCの初期設定。
  M(0)=0
  For I=0 To N: MC(I)=0: Next I
  For I=0 To N: A(I)=I: Next I
  '
  ' 初期設定。
  COUNT=0
  '
  ' 順列生成。
  Call Perm(0)
  '
  ' 結果の表示。
  Print Using"N=##";N
  Print "COUNT=";COUNT
  Print"一致数　　個数"
  For I=0 To N: Print Using"##　　########";I;MC(I): Next I
Loop
End
'
' 順列を生成する再帰手続き。
' Kは木の深さを表す。
Sub Perm(K)
  ' 生成された組み合わせの表示。
  If K = N  Then  
    COUNT=COUNT+1
    MC(M(N))=MC(M(N))+1
    Exit Sub
  End If

  ' 深さKの節点から深さK+1の子節点 N-K個を生成する。
  For I=K+1 To N  
    If A(I) = K+1 Then
      M(K+1)=M(K)+1
    Else  
      M(K+1)=M(K)
    End If
    ' I番目とK+1番目の要素を交換する。
    W=A(I): A(I)=A(K+1): A(K+1)=W  
    ' 深さK+1の子節点を作成する。
    Call Perm(K+1) 
    ' 交換を戻す。          
    W=A(I): A(I)=A(K+1): A(K+1)=W  
  Next I
End Sub

順列生成（応用）問題（３）の考察１

　順列生成（応用）問題（３）の考察１を示します。

問題（３）の考察１

' << DE111.bas >>
' 問題（３）の考察１に基づくプログラム。
' Tiny Basic
'
Public A(9)  ' かく乱順列を保存する配列。
Public N     ' 要素数。
Public COUNT ' 生成されたかく乱順列の個数。
'
Do
  ' Nの読み込み。
  Read N
  If (N <= 0) or (N > 9) Then Exit Do 
  Data 5, 0
  '
  ' 配列Aの初期設定。
  For I=0 To N: A(I)=I: Next I
  '
  ' 初期設定。
  COUNT=0
  '
  ' かく乱順列生成。
  Call Perm(0)
  '
  ' 結果の表示。
  Print Using"N=##";N
  Print "COUNT=";COUNT
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の子節点 N-K個を生成する。
  For I=K+1 To N  
    If A(I) <> K+1 Then
      ' I番目とK+1番目の要素を交換する。
      W=A(I): A(I)=A(K+1): A(K+1)=W  
      ' 深さK+1の子節点を作成する。
      Call Perm(K+1) 
      ' 交換を戻す。          
      W=A(I): A(I)=A(K+1): A(K+1)=W  
    End If
  Next I
End Sub

順列生成（応用）問題（３）の解

　順列生成（応用）問題（３）の解答例を示します。

問題（３）の解

順列生成（応用）問題（３）

　順列生成（応用）問題（３）を紹介します。

問題（３）

順列生成（応用）問題（２）の考察１

　順列生成（応用）問題（２）の考察１を示します。

問題（２）の考察１

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

  ' 深さKの節点から深さK+1の子節点 N-K個を生成する。
  For I=K+1 To N  
    If A(K) < A(I) Then
      ' I番目とK+1番目の要素を交換する。
      W=A(I): A(I)=A(K+1): A(K+1)=W  
      ' 深さK+1の子節点を作成する。
      Call Perm(K+1) 
        ' 交換を戻す。          
      W=A(I): A(I)=A(K+1): A(K+1)=W  
    End If
  Next I
End Sub