質問: こんばんは。 N回コインを投げるとしてコインの表、裏の総数を求めるプログラムを書くのにはどうしたら宜しいでしょうか? もちろん2^Nである事は分かります。 ただ、例えばコインの表裏によって今日食事をする、しないを決めるとします。 日によって食事量が違うとして、その食事の量に比例して体重が増えるとします。 ある一定の体重を超えると死んでしまうので、体重を超えないようにするコイントスの組み合わせを求めたい、と言うのがこの質問の趣旨です。 とりあえず、体重を超えた時点でその時点以降の組み合わせは考えなくて良いことになります。 なので、それまでの道順をどこかに転記しておき、そこを避けるようにコイントスをすればいいのではないかと考えました。 ただ、実際にプログラム上でどうやってこれを表現したら良いのかわかりません。 というか、そもそもにして組み合わせの求め方がわかりません。 for文を力技でネストするにしてもNが分からなければプログラムが書けません。 Itertoolなどのライブラリを使わないで、for文などの極基本的なコードのみを使った再帰的関数を書きたいです。 とりあえず上記のオーバーする道は避ける、という事は置いておいて、なるべく簡潔にこのようなプログラムの書き方を教えて頂けると助かります。 よろしくお願い申し上げます。
回答: 表裏を整数0, 1で表現するとして、N回コインを投げた結果を単純に生成するのが目的だと仮定します。 質問者さんがイメージする方法は以下のようなものだろうと思います。再帰を使えばできそうという感覚は良いと思いますが、実際にどう書くかを考えるならまず「漸化式」を考えるべきです。 * N-1桁の順列の集合{P0, P1, ...}があったとき * N桁の順列はN-1桁の順列の集合のそれぞれに0および1をくっつけた集合である * 0桁の順列は当然ながら空(`[]`)である ``` def toss(n): if n == 0: yield [] else: for s in toss(n - 1): for roll in range(2): yield s + [roll] for s in toss(3): print(s) ``` 尤も本件の場合(表裏の2つの種類しかない場合)、 ``` def toss(n): fmt = '{:0' + str(n) + 'b}' for i in range(1 << n): s = [*map(int, fmt.format(i))] yield s for s in toss(3): print(s) # ==> [0, 0, 0] [0, 0, 1] [0, 1, 0] [0, 1, 1] [1, 0, 0] [1, 0, 1] [1, 1, 0] [1, 1, 1] ``` という考え方も使えます。種類がD通りであるようなN個の順列は要するにD進数で表したN桁で表せる全ての数値であると考えられるからです。 なお上の回答ではどちらもgeneratorを使っています。集合が大きくなったときlistなどを使うとメモリーを非常に多く消費しますが「単に列挙するだけ」ならばgeneratorを使ったほうがメモリーの節約になりますし、一つ一つの要素を計算することだけに集中でき要素を蓄積すること(当然ながら効率よく蓄積することも含む)を考えなくて済みます。 (Python 3.xではgenerator的な機構が組み込み関数の中にも取り入れられており、例えばmapは与えられたiterableの各々の要素に関数を適用しつつそれを順に返すようなものとして定義されていますが、Python 2.xではそうなっておらず結果を無条件にlistにしてしまいます。そういう意味でPython 3.xの方が効率よく書ける手段が豊富といえましょう)