n個のものからr個を取り出す実際の計算法を教え乞う

質問

例えば，5個のものを，1,2,3,4,5（n＝5）とします．この5個から2個（r＝2）を取り出す組み合せは，(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5) の10通りです．

また，3個（r＝3）を取り出す組み合せは，やはり，(3,4,5), (2,4,5), (2,3,5), (2,3,4), (1,4,5), (1,3,5), (1,3,4), (1,2,5), (1,2,4), (1,2,3) の10通りです．

では，質問です．

質問：「n 個のものから r 個を取り出す実際の計算法（上記のような組み合せの数列を得る）を教えて下さい．」

よろしくおねがいします．

回答No.20

178-tall · ベストアンサー

>手計算でも原理的には出来るでしょうが，結局は，ルックアップテーブルなどを使うコンピュータ頼みになると言うことですね！…

当方は、逆の印象をもってます。
手計算できる規模なら「悉皆リスト」。
コンピュータ頼みのスケールでは、無用な検索をスキップする洗練「アルゴリズム」。

>サイズは nC0 + nC1 + nC2 + … + nCn = 2^n

…ですね。
空セットを除いて (2^n) - 1 。

お礼

度々，どうも，ありがとうございました．

回答No.9

kanemoto_s

行列として結果を得るような単純な数式は見かけないですね。世の中広いですから私が知らないだけかもしれないです。
求めるアルゴリズムやプログラムは色々公開されています。

全ての順列、組み合わせを配列として取得 - 謎のC言語ブログ
http://hatenaclang.blogspot.jp/2011/09/blog-post_09.html?m=1

お礼

回答を寄せて頂き，ありがとうございます．
このプログラムは，使えそうです．後で，じっくり見てみます．

回答No.8

178-tall

< ANo. 6
ですけど、余りに芸なしなのは致し方ない。

>「二項定理」ないし「パスカルの三角形」のパターンを利用…

たとえば 3Cr 。
(1+c1)*(1+c2)*(1+c3) のかけ算を展開して、累積数で分別。
　　　　　　　　　　　　　　　　↓
　= 1 + (c1+c2+c3) + (c1c2+c1c3+c2c3) + c1c2c3
　= 3C0 + 3C1 + 3C2 + 3C3

お礼

たびたび回答を，ありがとうございます．上記を参考にして，自分なりに考えてみます．

回答No.7

nobuyuki0505

#4です。補足読みました。

つまり、n個の中からr個を取り出す組み合わせを全て列挙する場合に、
どのようなアルゴリズムを使えば最短で全てを列挙することができるか？

という質問ですね。

おそらく、最短なのは、樹形図を用いた方法です。

1→2→3
□□□→4
□□□→5
□→3→4
□□□→5
□→4→5
2→3→4
□□□→5
□→4→5
3→4→5

(□はレイアウトを整えるためのものです。気にしないでください。)
のようなやり方です。

コンピュータなどで列挙させる場合もこの方法が最短で最適であると思います。

例えば、(1,2,☆)
として、☆に3,4,5を順に入れていき、
次は(1,3,☆)
で☆に4,5を入れ、
などとコンピュータ上で動かせば、瞬時に全ての組み合わせをリストアップしてくれるでしょう。

補足にありました1,2,3,4,5の並び替えを用いて、
組み合わせをリストアップする方法は、
残念ながら私は考察したことはありません。

しかし、実行速度だけでいえば、樹形図を用いた方法の方がはるかに早いと思います。

お礼

回答，ありがとうございます．参考になります．

回答No.6

178-tall

>…質問の本当の意味は，一言で言いますと，「組み合せの全てについて，組み合せの解を計算する方法はあるか」です…

「組み合せ」セットを羅列したいのかシラン？

「二項定理」ないし「パスカルの三角形」のパターンを利用して、できませんか？
(「計算する方法」というよりは、「アルゴリズム」に近いものになりそうですけど)

お礼

＞「組み合せ」セットを羅列したいのかシラン？
そうです！　その計算方法がありますか？　というのが質問です．
「計算方法」というのは，数値の計算だけでなく，広い意味で，羅列を実現する方法を指します．

＞「二項定理」ないし「パスカルの三角形」のパターンを利用して、できませんか？
「二項定理」や「パスカルの三角形」は使う事を考えていませんでしたが，考えてみます．

ありがとうございました．

回答No.5

shintaro-2

>例えば，具体的に，n＝5, r＝3 を取ります．5個のものを．1,2,3,4,5 とします．r＝3 ですから，1,2,3,4,5 の5個から3個を取り出す組み合せのすべてを計算して出す方法は，ありますか？ というのが質問です．かつ，一般的に，n, r についても計算して解を出す方法は，ありますか？ というのが質問の本質です．

それは「計算」しているのではなく
単に書き出しているような気がします。

計算はあくまでもｎCrです。

そのような意味では、
プログラムを組んでループを回すというのが一般的です。

５個から２個であれば
変数を2個設定して、
第1の変数を１から４まで
第2の変数を、第1の変数＋１から５まで
第1の変数の１つずつに対して第2の変数を変化させ
第1の変数の４についてすべてが終わったら終了というパターンです。

手でやるのであれば、樹系図的なものを書くということでしょうね。

お礼

過去の数学者が，何かの方法を編み出していて，知らないのは自分だけかな？ という思いもあっての質問でしたが，どうやら良い方法は無いらしいですね！！

回答，ありがとうございました．

回答No.4

nobuyuki0505

#1,#2,#3の解答では質問内容の誤解があるとのことです。

気になるので、質問の本当の意味を解説していただければ、と思います。

補足

＞気になるので、質問の本当の意味を解説していただければ、と思います。
質問の本当の意味は，一言で言いますと，「組み合せの全てについて，組み合せの解を計算する方法はあるか」です．この言い方も抽象的な表現で，分かりにくいと思いますので，以下に具体的な説明をします．

n個のものから r個を取り出す組み合せの総数C(n,r)は，C(n,r)＝n!/{r!(n－r)!}で与えられるのは周知です．
この事は質問の趣旨ではありません．

質問の意味は，このC(n,r)個のすべてを計算して表示する方法を求めています．

例えば，具体的に，n＝5, r＝3 を取ります．5個のものを．1,2,3,4,5 とします．r＝3 ですから，1,2,3,4,5 の5個から3個を取り出す組み合せのすべてを計算して出す方法は，ありますか？ というのが質問です．かつ，一般的に，n, r についても計算して解を出す方法は，ありますか？ というのが質問の本質です．

「計算して出す方法」と言うのは，何か，関数F(n,r,C)とうようなものがあって，数値的に計算する，と言うだけでなく，1,2,3,4,5 を幾つも並べ会わせて解を求める方法でもいいのです．

この，n＝5, r＝3 の場合は，以下のような方法で解が求められます．

a,b,c,d,e
----------
1,2,3,4,5 ← A
2,3,4,5,1 ← B
3,4,5,1,2 ← C

f,g,h,i,j
----------
1,2,3,4,5 ← D
3,4,5,1,2 ← E
4,5,1,2,3 ← F

上記の数表で，a,b,c,d,e,f,g,h,i,j のタテの列の三つの数がC(5,3)の全組み合せの解で，10通りあります．すなわち， (1,2,3), (2,3,4), (3,4,5), (1,4,5), (1,2,5), (1,3,4), (2,4,5), (1,3,5), (1,2,4), (2,3,5) の10通りです．

上記の数表は，見てお分かりでしょうが，1,2,3,4,5 を単に，ひとつづつずらして，A,B,C,D,E,F のように横に書き並べただけです．この「ひとつづつずらして，タテに書き並べる」と言うのが，「計算法」という事になります．この方法は，n, r が大きな数になると，うまくゆかない場合が出てきます．

どうでしょうか？　質問の意味をご理解して頂けたでしょうか？
以上です．

回答No.3

f272

上記のような組み合せの数列の個数を求めるのは#1さんの言うような方法でよいが，組み合わせの数列を求めるのはn 個のものの名前がわからないと書きづらいのですが，例えば
http://shuzo-kino.hateblo.jp/entry/2014/12/07/235215
こんな感じ。

お礼

回答をありがとうございます．
n 個のものの名前は，1,2,3,・・・, n－2, n－1, n でいいと思います．
貼って頂いたＵＲＬは，コンピュータ・プログラムで計算するようですが，後で，ゆっくり検討させて頂きます．

結局，関数のような数式に数値を入れて計算する，というような方法は，無いと考えてよい．
と解釈します．

ありがとうございました．

回答No.2

bran111

n 個のものから r 個を取り出す取り出し方C(n,r)は

C(n,r)=n!/[r!(n-r)!]

で与えられます。

C(n,r)=C(n,n-r)

なので

C(5,3)=C(5,2)=10

となり、質問の２つのケースはいずれも10通りです。

組み合せの数列なるものは、ｎ個のものからr個を系統的に取り出していって個数がC(n,r)となれば正解の可能性があります。

お礼

折角，投稿してもらったのに，残念だなぁ～．
しかし，この質問は，そういう意味ではないんですよ！
でも，ありがとう．時間を無駄にさせましたね！

（独り言！）質問の書き方がマズイのかなぁ～．

回答No.1

agrs

こんにちは。
高校数学で組合せという分野で習います。

n×(n-1)×(n-2)×・・・×(n-r+1)/r×(r-1)×(r-2)×・・・×1
となります。
コンビネーションの頭文字Ｃをとって　nＣｒ　とこの式を表すことが決まっています。
５個から３個取り出す場合、5×4×3/3×2×1=10　より１０となる、とこんな感じです。

http://www.kogures.com/hitoshi/webtext/stat-pc/index.html
参考ＵＲＬ載せておきます。

お礼

わざわざ，参考ＵＲＬまで載せた投稿をしてくれて・・・．
でも，この質問は，そういう意味ではないんですよ！
でも，ありがとう．時間を取らせましたね！