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.19

178-tall

>2進数の導出規則…

{y1 y2 y3 y4 y5} の有無を 0, 1 で表示した 5 ビット。
たとえば 00111 なら、y3, y4, y5 のセットを示す。

「二項定理」のばあいと同様、「表内検索 (table lookup) 」になります。
「悉皆リスト」のサイズは nC0 + nC1 + nC2 + … + nCn = 2^(n-1) 。(二項定理)
そこから、r 個の非零ビットをもつものだけひろっていく。

コンピュータ・ソフトでは、無用な検索をスキップする工夫をするのがふつう…。

お礼

早速，ご回答をありがとうございます．
だいたい分かって来ました．
手計算でも原理的には出来るでしょうが，結局は，ルックアップテーブルなどを使うコンピュータ頼みになると言うことですね！

ところで，
＞「悉皆リスト」のサイズは nC0 + nC1 + nC2 + … + nCn = 2^(n-1) 。(二項定理)
は，
「悉皆リスト」のサイズは nC0 + nC1 + nC2 + … + nCn = 2^n 。(二項定理)
ではないでしょうか？　0 から n までの和ですから．
因みに，ルックアップテーブルは下記のウィキペディアを参考にしました．

ルックアップテーブル
https://ja.wikipedia.org/wiki/%E3%83%AB%E3%83%83%E3%82%AF%E3%82%A2%E3%83%83%E3%83%97%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB

長々と，お付き合い頂き，ありがとうございました．

回答No.18

178-tall

質問文と照合すると…。
　　↓

　00111　=　(3,4,5)

　01011　=　(2,4,5)
　01101　=　(2,3,5)
　01110　=　(2,3,4)

　10011　=　(1,4,5)
　10101　=　(1,3,5)
　10110　=　(1,3,4)

　11001　=　(1,2,5)
　11010　=　(1,2,4)
　11100　=　(1,2,3)

お礼

丁寧に説明して頂き，ありがとうございます．
ここで，また，質問ですが，10通りの2進数：

　00111　　（7）← 10進数

　01011　　（11）
　01101　　（13）
　01110　　（14）

　10011　　（19）
　10101　　（21）
　10110　　（22）

　11001　　（25）
　11010　　（26）
　11100　　（28）← 10進数

は，どの様な方法（規則・法則）で導出されたのですか？
2進数の右に括弧付きで10進数を書き込みましたが，この10進数も，規則的な並び方ではないようです．
2進数の導出規則で具体的な方法があれば，教えて下さい．お願いします．

回答No.17

178-tall

補足。

モデル想定 (再掲) 。
　　↓
> 3 個の {y1, y2, y3} から 2 個を取り出す組み合せなら、yi (i=1, 2, 3) の有無を 1, 0 で指示した 2 進表示 = y1 y2 y3 の「悉皆リスト」…

{y1 y2 y3 y4 y5} の場合なら、00111 は {y3, y4, y5} に対応します。

お礼

ご回答，有り難う御座いました．

回答No.16

178-tall

>{1,2,3,4,5} の 2 進表示「悉皆リスト」から 3 個の非零ビットをもつものをひろえばよい．　ということは・・・？

　　↓

　00111

　01011
　01101
　01110

　10011
　10101
　10110

　11001
　11010
　11100

…じゃないかナ？

お礼

ご回答，有り難う御座いました．

回答No.15

178-tall

>零から昇順に列挙した「悉皆リスト」
　　↓
　0,　1,　10,　11,　100,　101,　110,　111,　1000,　1001,　1010, …

>非零ビット個数
　　↓
　0,　1,　1,　2,　1,　2,　2,　3,　1,　2,　2, …

なる対応です。

お礼

早速の，ご投稿ありがとうございます．
では，お願いです．

　{y1 y2 y3 y4 y5}＝{1,2,3,4,5} として 5C3（n＝5,r＝3）個（10個）のセットを作って見せて頂けませんか．

　{1,2,3,4,5} の 2 進表示「悉皆リスト」から 3 個の非零ビットをもつものをひろえばよい．
　ということは・・・？

10進数　　　1　　2　　3　　　4　　　5　　　
　　　　　　↓　　↓　　↓　　↓　　　↓　　　　　　
2進数　　　1　　10　　11　　100　　101　　
　　　　　　↓　　↓　　↓　　↓　　↓　
非零ビット　1　　1　　 2　　1　　　2　　

ですから，ここから，どうやるのでしょうか？？　お願いします．

回答No.14

178-tall

>…「ハミング重み」なる概念が未だピンと来ませんが…
　　↑
「ハミング重み」は、たしかに唐突でした。

発想は、
　{y1 y2 y3 … yn} にて nCr のセットを得るのに、
　わざわざ 「二項定理」で展開し yi の r 項積 をピックアップせずとも、
　{y1 y2 y3 … yn} の 2 進表示「悉皆リスト」から r 個の非零ビットをもつものをひろえばよい
…というもの。

零から昇順の「悉皆リスト」に非零ビット個数を書きこんでいくと、
　0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, …
…ならば、と　"The On-Line Encyclopedia of Integer Sequences" にて検索してみると、Hamming weight of n という名前だという。

…というのが裏話です。
「ハミング重み」 "Sequences" の構成は、
たとえばこの説明…。
　　↓
To construct the sequence, start with 0 and use the rule: If k >= 0 and a(0), a(1), ..., a(2^k-1) are the 2^k first terms, then the next 2^k terms are a(0) + 1, a(1) + 1, ..., a(2^k-1) + 1.

お礼

またまた，ご投稿ありがとうございます．

＞零から昇順の「悉皆リスト」に非零ビット個数を書きこんでいくと、
＞　0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, …
この数列が分かりません．
どの数字が「悉皆リスト」で，「非零ビット個数」の数字はどれでしょうか？

因みに，
10進数　　　　　
　0　　1　　2　　　3　　　4　　　5　　　6　　　7　　　8　　　　9　　　　10
　　　 ↓　　　　　　　　↓　　　　　　　↓　　　　　　↓　　　　↓　　　　↓
2進数　↓　　　　　　　　↓　　　　　　　↓　　　　　　↓　　　　↓　　　　↓
　0　　1　　10　　11　　100　　101　　110　　111　　1000　　1001　　1010
　　　　　　　　　↓　　　　　　　↓　　　　　　↓　　　　　　　　↓　　　　↓
非零ビット個数　　↓　　　　　　　↓　　　　　　↓　　　　　　　　↓　　　　↓
　0　　1　　1　　 2　　　1　　　2　　　2　　　3　　　　 1　　　　2　　　　2
になると思いますが・・・．

回答No.13

178-tall

< ANo.12
　　↓
>>…コンピュータ・プログラムを用いて解く方法には，あまり魅力がありません．…
　　↓
コンピュータ屋さんのいう「ハミング重み」もお嫌かな？

たとえば 3 個の {y1, y2, y3} から 2 個を取り出す組み合せなら、yi (i=1, 2, 3) の有無を 1, 0 で指示した 2 進表示 = y1 y2 y3 の「悉皆リスト」から「ハミング重み」が 2 のものをピックアップすれば、3C2 のセットが得られる。
　　↓
参考 URL / Hamming weight of n.

参考URL：

https://oeis.org/search?q=0%2C1%2C1%2C2%2C1%2C2%2C2%2C3%2C1%2C2%2C2%2C3%2C&language=english&go=Search

お礼

度々の投稿，ありがとうございます．
「ハミング重み」なる概念が未だピンと来ませんが，「ハミング重み」を wikipedia で調べてみたら，関連として，「ハミング距離」「ミング符号」「リード・マラー符号」「ターボ符号」などの概念・定義が使えるかもしれません．参考になりました．ありがとうございました．

回答No.12

178-tall

< ANo.11
　　↓
>…コンピュータ・プログラムを用いて解く方法には，あまり魅力がありません．…
　　↓
筆算で間にあいますヨ。

発想は、

　「二項定理」は、(x+y)^n の多項展開に現れる二項積 {x^(n-r) }*(y^r) の係数が nCr である、ということ
　これは、n 個の (相異なる) y から r 個の y をとる組み合わせ総数
　ならば、(1+y1)*(1+y2)* … *(1+yn) の多項展開に現れる yi (i=1～n) の r 項積 を拾っていけば、nCr 個のセット

…というもの。
やってみると、小学方式のかけ算で間にあうヨ、という芸の無いハナシに尽きそう。

お礼

回答者 178-tallさんの仰る通りのようですね！

この質問を出した段階では，(1+y1)*(1+y2)* … *(1+yn) の多項展開で C(n,r)≡nCr個の組み合せの解が出ることに気が付いていませんでした．回答No.6 の 178-tallさんのご投稿で気が付いたわけです．

多項展開 Π[i＝1,i＝n](1+yi)で当初の目的である組み合せの解が出る事を踏まえた上で，別の方法がないかを考えてみます．出来れば，Π[i＝1,i＝n](1+yi)で，長ったらしく計算しなくても済むような方法を・・・．

非常に参考になりました．ありがとうございます．

回答No.11

178-tall

> ANo.8

蛇足…スプレッドシート (シート関数試用) での作例です。

　　　　　　　　　　　1　　　　　　　c1
　　　　　　　　　　　1　　　　　　　c2
　　　　　　　　　　　----------------
　　　　　　　　　　　c2　　　　　　c1*c2
　　　　　1　　　　　 c1
　　　　　----------------------------
　　　　　1　　　　　　c1,c2　　　　　　c1*c2
　　　　　　　　　　　　1　　　　　　　　　c3
　　　　　----------------------------
　　　　　c3　　　　　c3*(c1,c2)　　　　　c1*c2*c3
1　　　　c1,c2　　　　c1*c2
----------------------------------------
1　　　c1,c2,c3　　　c1*c2,c3*(c1,c2)　　　c1*c2*c3
　　　　　　　　　　　=c1*c2,c1*c3,c2*c3

{3C0}　　{3C1}　　　　　　　{3C2}　　　　　　　{3C3}

お礼

度々のご報告，ありがとうございます．
回答者さんの回答No.6 のご投稿で，本質問の趣旨に対して「二項定理」や「パスカルの三角形」も関連がありそうな事に気づきました．
その方面からの考察は未だ，これからです．

今回のご投稿は，スプレッドシートを用いた方法ですが，コンピュータ・プログラムを用いて解く方法には，あまり魅力がありません．
出来れば，純粋数学的な方法を求めています．それを探るのが本筋なのです．

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

回答No.10

nobuyuki0505

#4です。
補足したく、再度投稿します。

補足にあった並び替えを用いた方法は一般化不可能だと考えたので、
その理由を説明します。

補足にあった例で説明しますと、
5C3=10は10が5の倍数であるため、
列挙に成功しました。

しかし、一般にnCrが任意のrについてnの倍数であるのは、
nが素数のときです。

nが素数でなければ、nCrはnの倍数とは限らず、

ゆえに並び替えによる羅列の方法は、明らかに適用不可だと分かります。

たとえば、n=4,r=2だと、
4C2=6
であるが、この6通りは4の倍数ではないので、
補足にあった並び替えの方法では羅列不可だと分かります。

これで補足を終わります。

お礼

補足説明を投稿して下さり，ありがとうございます．
その通りです．非常に参考になりました．