パズル万華鏡

現在、プログラミング技術の紹介と解説をしています。

順列生成(多段順列)問題(7)の考察1

 順列生成(多段順列)問題(7)の考察1を示します。

問題(7)の考察1
f:id:isemba:20200511191939p:plain

' << MC111.bas >>
' 集合{1,2,…,n}上のm段r組合せの生成(非辞書式順序)
' Tiny Basic
'
Public P(10,10) ' m段r組合せを保存する配列。
Public N        ' 集合の要素数。
Public M        ' 段数。
Public R        ' 組合せの長さ。        
Public COUNT    ' m段r組合せの個数。
'
Do
  ' N,R,Mの読み込み。
  Read N,R,M
  If (N <= 0) or (N > 10) Then Exit Do
  Data 3,2,2
  Data 0,0,0
  '
  ' 配列Pの初期設定。
  For I=1 To M
    For J=0 To N: P(I,J)=J: Next J
  Next I
  '
  ' 初期設定。
  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             
    ' m段r組合せの表示。
    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)
      '  
      ' 各段の要素は昇順。降順の場合、次の要素に進む。
      If P(D,K) > T Then Goto *LAB
      '
      ' 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
    *LAB
    Next I
  End If
End Sub

f:id:isemba:20200511192032p:plain
f:id:isemba:20200511192048j:plain