パズル万華鏡

面白いパズルの紹介と解説をします。

順列生成(応用)問題(4)の考察2

 順列生成(応用)問題(4)の考察2を示します。

 

問題(4)考察2

 集合{1,2,...,n}上のフィボナッチ順列の個数をf(n)とする。

求める順列において、p(n)=n または、p(n)=n-1が成り立つ。

そこで、求める順列をp(n)=nとp(n)=n-1で分類する。

前者は、f(n-1)個、後者は、p(n-1)=nとなるので、f(n-2)個となる。

したがって、

  f(n) = f(n-1) + f(n-2) (n≧3) f(1)=1, f(2)=2

を得る。これは、フィボナッチ数である。

f:id:isemba:20200428172748j:plain

 

順列生成(応用)問題(4)の考察1

順列生成(応用)問題(4)の考察1を示します。

問題(4)の考察1
f:id:isemba:20200428172407p:plain

' << FB111.bas >>
' 問題(4)の考察1に基づくプログラム。
' Tiny Basic
'
Public A(9)  ' フィボナッチ順列を保存する配列。
Public N     ' 要素数。
Public COUNT ' 生成されたフィボナッチ順列の個数。
'
Do
  ' Nの読み込み。
  Read N
  If (N <= 0) or (N > 9) Then Exit Do 
  Data 6, 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 (K <= A(I)) and (A(I) <= K+2) 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

f:id:isemba:20200428172454p:plain
f:id:isemba:20200428172506j:plain