コラム

再帰処理（2）

作成日：20200711 テーマ1：情報系テーマ2：プログラムテーマ3：

苦手な再帰処理について、自分が理解したプロセスを備忘録的に残しておく。

今回は、以下の（a1,a2）、（b1,b2,b3,b4）、（c1,c2）の各列から1つずつ選んで“重複なしの組み合わせ”を、再帰処理を使って書いて見る。

プログラムが長いと見る気をなくしてしまうが、一応次のようにモジュールを分けている。従って、一つ一つのモジュールは大して長くないので我慢してみてもらえれば、と思う。

< python >

#***********************************************************
#sampleデータ作成
#	ここを編集すれば組み合わせの数、データをいろいろ変えられる
#***********************************************************
def MakeData():
	dAry = []
	
	#データa
	dAry.append(['a1', 'a2', 'a3'])
	
	#データb
	dAry.append(['b1', 'b2'])
	
	#データc
	dAry.append(['c1', 'c2'])
	
	return dAry

#**********************************************************
#再帰関数
#   comb    :組合せ配列
#   cntC    :組合せ配列のID（組合せ個数分）
#   dAry    :組合せ元のデータ配列
#   IDc     :データ元の番号 a=0, b=1, c=2
#   cutLv   :組合せる変数の数
#           （0にするとaのみ、1にするとaとb、2にするとa,b,cの組合せ）
#**********************************************************
def Recursion(comb, cntC, dAry, IDc, cutLv):
	
	for cnt1 in range(len(dAry[IDc])):
		comb[cntC][IDc] = dAry[IDc][cnt1]
		
		if IDc < cutLv - 1:
			cntC = Recursion(comb, cntC, dAry, IDc + 1, cutLv)
		else:
			if cntC < len(comb) - 1:
				cntC += 1
				
				#↓がないと、歯抜けデータになってしまう。
				#試しにコメントアウトしてマクロを実行してみてもらいたい。
				for cnt2 in range(IDc):
					comb[cntC][cnt2] = comb[cntC - 1][cnt2]
	
	#combCの配列IDを返す
	return cntC

#***********************************************************
#実行
#***********************************************************
if __name__ == '__main__':
	
	#サンプルデータ作成（dAry） >>>>>>>>>>>>>>>>>>>>>>
	dAry = []
	dAry = MakeData()
	
	#確認用
	print(MakeData())
	
	#再帰処理（組合せ = comb）>>>>>>>>>>>>>>>>>>>>>>>>
	#配列準備（combサイズを確定）
	Nary = 1
	for cnt1 in range(len(dAry)):
		Nary *= len(dAry[cnt1]) 
	tmp = []
	for cnt1 in range(len(dAry)):
		tmp.append('')
	comb = []
	for cnt1 in range(Nary):
		comb.append(tmp.copy())		#copyしないと全部同じ要素になる
	
	#再帰処理
	Recursion(comb, 0, dAry, 0, len(dAry))
	
	#出力 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	for rcomb in comb:
		print(rcomb)

pythonサンプルのダウンロード

< Excel VBA >

'**********************************************************
'sampleデータ作成
'   ここを編集すれば組み合わせの数、データをいろいろ変えられる
'**********************************************************
Sub MakeData(dAry)
    
    Dim tmp() As String
    
    '各データで行数がことなるため、ジャグ配列を使う
    ReDim dAry(2)
    
    'データa
    ReDim tmp(2)
    tmp(0) = "a1"
    tmp(1) = "a2"
    tmp(2) = "a3"
    dAry(0) = tmp
        Erase tmp
    
    'データb
    ReDim tmp(1)
    tmp(0) = "b1"
    tmp(1) = "b2"
    dAry(1) = tmp
        Erase tmp
    
    'データc
    ReDim tmp(1)
    tmp(0) = "c1"
    tmp(1) = "c2"
    dAry(2) = tmp
        Erase tmp

End Sub

'**********************************************************
'再帰関数
'   comb    :組合せ配列
'   cntC    :組合せ配列のID（組合せ個数分）
'   dAry    :組合せ元のデータ配列
'   IDc     :データ元の番号 a=0, b=1, c=2
'   cutLv   :組合せる変数の数
'           （0にするとaのみ、1にするとaとb、2にするとa,b,cの組合せ）
'**********************************************************
Sub Recursion(comb, cntC, dAry, IDc, cutLv)
    
    Dim cnt1 As Long, cnt2 As Long
    
    For cnt1 = 0 To UBound(dAry(IDc))
        comb(IDc, cntC) = dAry(IDc)(cnt1)
        
        If IDc < cutLv Then
            Call Recursion(comb, cntC, dAry, IDc + 1, cutLv)
        Else
            cntC = cntC + 1
            
            'ここで配列を追加すると、最後余分に1個配列が追加される
            ReDim Preserve comb(UBound(dAry), cntC)
            
            '↓がないと、歯抜けデータになってしまう。
            '試しにコメントアウトしてマクロを実行してみてもらいたい。
            For cnt2 = 0 To UBound(dAry)
                comb(cnt2, cntC) = comb(cnt2, cntC - 1)
            Next cnt2
        End If
    Next cnt1
End Sub

'**********************************************************
'実行
'**********************************************************
Sub test()
    
    Dim cnt1 As Long, cnt2 As Long
    Dim colNo As Long
    Dim dAry() As Variant
    Dim comb() As String
    
    'サンプルデータ作成（dAry） >>>>>>>>>>>>>>>>>
    Call MakeData(dAry)
    
    '再帰処理（組合せ = comb） >>>>>>>>>>>>>>>>>>
    '   配列は1個余計なものができてしまう（最後尾）
    ReDim Preserve comb(UBound(dAry), 0)
    Call Recursion(comb, 0, dAry, 0, UBound(dAry))
    
    'セルに出力 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    
    '前回データ消去
    Cells.ClearContents
    
    '余計な1個は出力しない
    colNo = Range("E1").Column
    For cnt1 = 0 To UBound(comb, 2) - 1
        For cnt2 = 0 To UBound(comb, 1)
            Cells(cnt1 + 1, colNo + cnt2).Value = comb(cnt2, cnt1)
        Next cnt2
    Next cnt1
End Sub

Excel VBAサンプルのダウンロード

結果は次のようになる。