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

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

問題（６）の考察１

' << MP611.bas >>
' n（nは3の倍数）人、3人1組の総当たり戦方式。
' 集合{1,2,…,n}上の(n-1)/2段n部分順列の生成（非辞書式順序）
' に基づく。
' Tiny Basic
'
Public P(9,9) ' (n-1)/2段n部分順列を保存する配列。
Public N      ' 人数。
Public COUNT  ' 条件を満たす配置の個数。
Public X(9,9) ' 人i,jがペアの場合、X[i][j]=1、
              ' その他の場合、X[i][j]=0
'
Do
  ' Nの読み込み。*/
  Read N
  If (N <= 0) or (N > 9) Then Exit Do
  Data 9, 0
  '
  ' 配列Pの初期設定。
  For I=1 To Int((N-1)/2)
    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 = Int((N-1)/2) Then             
    ' 解の出力
    COUNT=COUNT+1
    Print "[";COUNT;"]"
    For I=1 To Int((N-1)/2)
      For J=1 To N Step 3 
        Print Using"(# # #)";P(I,J);P(I,J+1);P(I,J+2);
      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 (D > 1) and (K = 1) and (P(D-1,K+1) > T) Then Goto *LAB 
      '
      If (K+1) Mod 3 = 1 Then
        ' 条件２を調べる。       
        If (K+1 >= 4) Then
          If (P(D,K-2) > T) Then Goto *LAB
        End If
        Goto *LAB1
      End If
      '
      If (K+1) Mod 3 = 2 Then
        S=P(D,K)
        ' 条件３を調べる。*/                               
        If S > T Then Goto *LAB
        ' 条件４を調べる。*/                               
        If X(S,T) = 1 Then Goto *Lab
        X(S,T)=1
        Goto *LAB1
      End If
      '
      If (K+1) Mod 3 = 0 Then
        S=P(D,K): R=P(D,K-1)
        ' 条件３を調べる。*/                               
        If S > T Then Goto *LAB
        ' 条件４を調べる。*/                               
        If X(S,T) = 1 Then Goto *Lab
        If X(R,T) = 1 Then Goto *Lab
        X(S,T)=1
        X(R,T)=1
      End If
      '                                   
    *LAB1:
      ' 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+1) Mod 3 = 2 Then 
        X(S,T)=0
      End If
      If (K+1) Mod 3 = 0 Then 
        X(S,T)=0: X(R,T)=0
      End If
      ' 
    *LAB:
    Next I
  End If
End Sub