Pythonを使った組み合わせの求め方について

こんばんは。
N回コインを投げるとしてコインの表、裏の総数を求めるプログラムを書くのにはどうしたら宜しいでしょうか？
もちろん2^Nである事は分かります。
ただ、例えばコインの表裏によって今日食事をする、しないを決めるとします。
日によって食事量が違うとして、その食事の量に比例して体重が増えるとします。
ある一定の体重を超えると死んでしまうので、体重を超えないようにするコイントスの組み合わせを求めたい、と言うのがこの質問の趣旨です。

とりあえず、体重を超えた時点でその時点以降の組み合わせは考えなくて良いことになります。
なので、それまでの道順をどこかに転記しておき、そこを避けるようにコイントスをすればいいのではないかと考えました。

ただ、実際にプログラム上でどうやってこれを表現したら良いのかわかりません。
というか、そもそもにして組み合わせの求め方がわかりません。
for文を力技でネストするにしてもNが分からなければプログラムが書けません。

Itertoolなどのライブラリを使わないで、for文などの極基本的なコードのみを使った再帰的関数を書きたいです。
とりあえず上記のオーバーする道は避ける、という事は置いておいて、なるべく簡潔にこのようなプログラムの書き方を教えて頂けると助かります。
よろしくお願い申し上げます。

tiitoi

2018/12/12 12:28 編集

問題は「N回コインを投げるとしてコインの表、裏の総数を求める」ではないわけですよね。動的計画法で解くナップザック問題の類問？すみませんが、結局課題がなんなのかわかりづらいので、もう少し問題を定式化していただけますか？

babbleman

2018/12/12 12:29

分かりづらくてすみません。疑問点を一気に列挙した形になっているので文章が纏まっていなかったです。再帰的関数などを用いて、コイントスの組み合わせを列挙したいです。

tiitoi

2018/12/12 12:43 編集

再帰関数はなんらかの終了条件が必要です。長さ N と固定しないのであれば、それの代わりなんらかの再帰を終了する条件をつけてください。ある体重を超えないように食事する、しないを決めるというのはDP の部分和問題が近いように思いますが、どうでしょうか？ https://qiita.com/drken/items/a5e6fe22863b7992efdb

行動規範の内容に同意します

回答1件

ベストアンサー

表裏を整数0, 1で表現するとして、N回コインを投げた結果を単純に生成するのが目的だと仮定します。

質問者さんがイメージする方法は以下のようなものだろうと思います。再帰を使えばできそうという感覚は良いと思いますが、実際にどう書くかを考えるならまず「漸化式」を考えるべきです。

N-1桁の順列の集合{P0, P1, ...}があったとき
N桁の順列はN-1桁の順列の集合のそれぞれに0および1をくっつけた集合である
0桁の順列は当然ながら空([])である

Python
1def toss(n):
2    if n == 0:
3        yield []
4    else:
5        for s in toss(n - 1):
6            for roll in range(2):
7                yield s + [roll]
8
9for s in toss(3):
10    print(s)

尤も本件の場合（表裏の２つの種類しかない場合）、

Python
1def toss(n):
2    fmt = '{:0' + str(n) + 'b}'
3    for i in range(1 << n):
4        s = [*map(int, fmt.format(i))]
5        yield s
6
7for s in toss(3):
8    print(s)
9# ==>
10[0, 0, 0]
11[0, 0, 1]
12[0, 1, 0]
13[0, 1, 1]
14[1, 0, 0]
15[1, 0, 1]
16[1, 1, 0]
17[1, 1, 1]

という考え方も使えます。種類がD通りであるようなN個の順列は要するにD進数で表したN桁で表せる全ての数値であると考えられるからです。

なお上の回答ではどちらもgeneratorを使っています。集合が大きくなったときlistなどを使うとメモリーを非常に多く消費しますが「単に列挙するだけ」ならばgeneratorを使ったほうがメモリーの節約になりますし、一つ一つの要素を計算することだけに集中でき要素を蓄積すること(当然ながら効率よく蓄積することも含む)を考えなくて済みます。
(Python 3.xではgenerator的な機構が組み込み関数の中にも取り入れられており、例えばmapは与えられたiterableの各々の要素に関数を適用しつつそれを順に返すようなものとして定義されていますが、Python 2.xではそうなっておらず結果を無条件にlistにしてしまいます。そういう意味でPython 3.xの方が効率よく書ける手段が豊富といえましょう)

投稿2018/12/12 19:54

KSwordOfHaste

総合スコア18394

babbleman

2018/12/15 02:20

非常にわかりっっっっっっっっっっっqやすい回答をありがとうござい漸化式を使うと言うのは何となくわかっていたのですが具体的にどのように表現したらいいのか思い付かずに戸惑っておりました。 Generatorの概念がイマイチ分からず、rangeで済むのではないか、と言う考えもまだ錯綜しておりますが、それはおいおい調べていくことにします。 yieldの基本から読み返してみます。参考になりました！ありがとうございます。

行動規範の内容に同意します