順列生成（多段順列）問題（５）の考察１

　順列生成（多段順列）問題（５）の考察１を示します。

問題（５）の考察１

' << MP511.bas >>
' n（nは偶数）人、2人1組の総当たり戦方式。
' 集合{1,2,…,n}上のn-1段n部分順列の生成（非辞書式順序）に基づく。
' Tiny Basic
'
Public P(10,10) ' n-1段n部分順列を保存する配列。
Public N        ' 人数。
Public COUNT    ' 条件を満たす配置の個数。
Public X(10,10) ' 人i,jがペアの場合、X[i][j]=1、
                ' その他の場合、X[i][j]=0
'
Do
  ' Nの読み込み。*/
  Read N
  If (N <= 0) or (N > 10) Then Exit Do
  Data 4, 0
  '
  ' 配列Pの初期設定。
  For I=1 To N-1
    For J=1 To N: P(I,J)=J: Next J
  Next I
  '
  ' 配列Xの初期設定。                    
  For I=1 To N                    
    For J=1 To N: X(I,J)=0: Next J   
  Next I     
  '
  ' 初期設定。                       
  COUNT=0
  '
  ' m段r部分順列生成。
  Call Mperm(1,0)
  '
  ' 結果の出力
  Print Using"N=##";N
  Print "COUNT=";COUNT
Loop
End
'
' D:段数 K:深さ
Sub Mperm(D,K)
  If D = N Then             
    ' 解の出力
    COUNT=COUNT+1
    Print "[";COUNT;"]"
    For I=1 To N-1
      For J=1 To N Step 2 
        Print Using"(# #)";P(I,J);P(I,J+1);
      Next J
      Print
    Next I
    Print
    Exit Sub                               
  End If 

  If K = N Then
    '次の段に進む。   
    Call Mperm(D+1,0)
  Else
    ' D段目の部分順列中、
    ' 深さKの節点から深さK+1の子節点 N-K個を生成する。
    For I=K+1 To N
      T=P(D,I)
      ' 条件１(各行の１番目の組において、行間で昇順)を調べる。
      If (K = 0) and (T <> 1) Then Goto *LAB
      If (K = 1) and (T <> D+1) Then Goto *LAB 
      If K Mod 2 = 0 Then     
        ' 条件２(各行のペア間が昇順)を調べる。    
        If K >= 2 Then
          If P(D,K-1) > T Then Goto *LAB 
        End If
      Else                                                
        ' 条件３(各行のペア内で昇順)を調べる。        
        S=P(D,K)                         
        If S > T Then Goto *LAB  
        ' 条件４(n-1日間の対戦相手がすべて異なる)を調べる。
        If X(S,T) = 1 Then Goto *LAB 
        X(S,T)=1                                      
      End If
      '                                   
      ' I番目とK+1番目の要素を交換する。
      W=P(D,I): P(D,I)=P(D,K+1): P(D,K+1)=W
      ' 深さK+1の子節点を作成する。
      Call Mperm(D,K+1) 
      ' 交換を戻す。          
      W=P(D,I): P(D,I)=P(D,K+1): P(D,K+1)=W
      If K Mod 2 = 1 Then X(S,T)=0 
    *LAB:
    Next I
  End If
End Sub