辞書と組み合わせと再帰関数

Photo by joka2000, Double-flowered Cherry Blossoms

辞書が与えられて、そのキーと値の群の中でタプルやリストを持っている値を、任意の値で組み合わせたリストを返すという処理はどう実装すべきか悩んでいました。
言葉にすると難しく聞こえますが、要は
{"a":(1,2), "b":4, "c":(3,4)}という辞書が与えられた場合、返すリストは
[{"a":1, "b":4, "c":3},
{"a":1, "b":4, "c":4},
{"a":2, "b":4, "c":3},
{"a":2, "b":4, "c":4}]
となるわけです。

通常の行列のような処理は単純にループを2回回せばいいわけですが、今回の問題の場合ループ回数は変動するわけで、単純にループを回すわけにはいかない。どうすればいいのかちょっと考えて見たら、再帰関数を使えば案外スマートに実装できそうな気がしたので、実際にやってみました。

from copy import copy
 
def makeKwargsList(kwargs, exceptions=[]):
 """
 タプルやリストを含んだ辞書から、それらの値を含む任意の組み合わせを
 すべてリストとして返します.
 例:
 kwargs     = {"a":(1,2), "b":3, "c":(True,False), "d":(1,2)}
 exceptions = "d"の場合、返される辞書のリストは、
 [{"a":1, "b":3, "c":True, "d":(1,2)},
  {"a":1, "b":3, "c":False, "d":(1,2)},
  {"a":2, "b":3, "c":True, "d":(1,2)},
  {"a":2, "b":3, "c":False, "d":(1,2)}] となります.
  
 kwargs     : タプルやリストを含んだ辞書
 exceptions : 組み合わせとして出力してほしくないキーのリスト
 """
 if type(kwargs) != dict: raise TypeError
 # キーワードの抽出
 kwdict = {}
 base   = {}
 for (key, value) in kwargs.items():
  if (type(value) == list or type(value) == tuple) and \
     (key not in exceptions):
   kwdict[key] = value
  else: base[key] = value
 # key, kw の分離
 keys = kwdict.keys()
 values  = kwdict.values()
 kwargs_list = []
 __makeKw(values, [], kwargs_list)
 # 結合
 r = [dict(zip(base.keys() + keys, base.values() + ag)) for ag in kwargs_list]
 return r

def __makeKw(kwlist=[], base=[], kwargs_list=[]):
 argslist  = kwlist[0]
 if len(kwlist) > 1:
  newKwlist = kwlist[1:]
  for kw in argslist:
   new_base = copy(base)
   new_base.append(kw)
   __makeKw(newKwlist, new_base, kwargs_list)
 else:
  for kw in argslist:
   new_base = copy(base)
   new_base.append(kw)
   kwargs_list.append(new_base)

__makeKw()が再帰関数で、この場合[(1,2),(3,4)]のリストから、[[1,3], [1,4], [2,3], [2,4]]をkwargs_listに代入させていく関数となっています。

本来のプログラマがどうやってこのようなアルゴリズムを組んでいるのかは残念ながら勉強不足で分かりませんが、とりあえずきちんと動作しますし、そこまで速度が重要となるような処理ではないですので(せいぜい100〜10000程度)、べつにこれでいいかなと。

それにしても、1年前は思いつかずに挫折していたであろうアルゴリズムが実際に組めるようになってくると、ちょっと成長している感がありますね。