pythonのdictを使わずに同じ出力を得るには

Question

下のコードはdictを使ってaとbからなる記号列を長さ n 以下のすべての記号列が辞書順に並ぶようにしたコードなのです。これをdictを使わず、普通の再帰で書き直したいのですが、やり方がわからないので解説をしてもらいたいです。

Python
コード
def dict(str, depth):
  if depth == 0:
    return
  print(str)
  dict(str+'a', depth-1)
  dict(str+'b', depth-1)

n=4
dict('', n)

Comments

[takutakuya]

再帰が必須なのでしょうか？

Answer 1

このコードは普通の再帰となっています。dictという組み込み識別子は、def dictによって上書きされています。よって、dictは辞書型などを使っているのではなく、定義された新たな関数になっています。

Comments

[mothi5656]

dictのところをdict_sortedにすると、('', 4)が出力されました、、、

[toast-uz]

4箇所のdictを全て変換してみてください。

[mothi5656]

タイプミスってました。できました。

Answer 2

再帰は使っていませんが、itertoolsという便利なモジュールがあるので、それを使うと比較的簡単に記号列の組み合わせを得ることができます。辞書順についてはリストのsort()メソッドを使いました。

import itertools

char = ('a', 'b')
n = 3

results = []

for i in range(1, n+1):
    results += list(itertools.product(char, repeat=i))

results.sort()

for result in results:
    print(''.join(result))

# 出力結果
# a
# aa
# aaa
# aab
# ab
# aba
# abb
# b
# ba
# baa
# bab
# bb
# bba
# bbb

同じことを再帰的に書くことのほうが難しいと私は感じます。