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

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

問題（２）の考察１

' << MP211.bas >>
' 集合{1,2,…,n}上のm段r部分順列の生成（非辞書式順序）
' Tiny Basic
'
Public P(10,10) ' m段r部分順列を保存する配列。
Public N        ' 集合の要素数。
Public M        ' 段数。
Public R        ' 部分順列の長さ。        
Public COUNT    ' 条件を満たす配置の個数。
Public X(10,10) ' 列jに要素yが出現しているとき、x[j][y]=1,
                ' 出現していないとき、x[j][y]=0
'
Do
  ' N,R,Mの読み込み。*/
  Read N,R,M
  If N <= 0 Then Exit Do
  Data 3,3,3,
  Data 0,0,0
  '
  ' 配列Pの初期設定。
  For I=1 To N
    For J=1 To N: P(I,J)=J: Next J
  Next I
  '
  ' 配列Xの初期設定。                    
  For J=1 To R                    
    For Y=1 To N: X(J,Y)=0: Next Y   
  Next J     
  '
  ' 初期設定。                       
  COUNT=0
  '
  ' m段r部分順列生成。
  Call Mperm(1,0)
  '
  ' 結果の出力
  Print Using"N=## R=## M=##";N;R;M
  Print "COUNT=";COUNT
Loop
End
'
' D:段数 K:深さ
Sub Mperm(D,K)
  If D > M Then             
    ' 解の出力
    COUNT=COUNT+1
    Print "[";COUNT;"]"
    For I=1 To M
      For J=1 To R: Print Using"##";P(I,J);: Next J   
      Print
    Next I
    Print
    Exit Sub                               
  End If 

  If K = R Then
    '次の段に進む。   
    Call Mperm(D+1,0)
  Else
    ' D段目の部分順列中、
    ' 深さKの節点から深さK+1の子節点 N-K個を生成する。
    For I=K+1 To N
      T=P(D,I)
      '
      ' D段目K+1列に要素Tが重複出現している場合,次の要素に進める。
      If X(K+1,T) = 1 Then Goto *LAB
      '
      X(K+1,T)=1                                        
      '                                   
      ' 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
      X(K+1,T)=0                                        
    *LAB:
    Next I
  End If
End Sub