(目的)
前回、組み合わせを列挙するルーチンを再帰で作ったのですが、色々考えていくうちに別のアイデアを思いつきました。（＾＾）それでルーチンを作ってみます。
(方針)
8C3 を良く見てみると
0 0 0 0 0 1 1 1
0 0 0 0 1 0 1 1
...
という感じで、2進数の数に見えてきます。つまり 00000001 から 11111111 まで足し上げていって１のビットの数が３つのものを選べば 8C3 の組合せの列挙になっているのではないか。ということです。
(プログラム例)
上記方針でプログラムを作ってみました。
combination-bitwise.cpp
(実行結果)
$ a
3 2 1
4 2 1
．．．中略
8 7 5
8 7 6
一応正しい結果を出すようです。
(処理時間)
表示部分を殺して実行時間を計ってみました。
$ a
elapsed = 0.083809534452004 (msec) ← 8C3 の処理時間
elapsed = 77023.028066416256000 (msec) ← 30C10 の処理時間
お、遅い．．．ＯＴＺ
考えてみると 30C10 の場合、1 から 2^30(～10億) までカウントアップしてるんだから、まあ遅い筈ですね。
(むだな抵抗。少しだけ、、、)
要は、１のビットが３つの数値を簡単に求められる方法があればいいのですよ。ということでむだな抵抗を少しだけ、、、
例えば 8C3 の場合だと以下のような数値になります。
7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50,
52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112,
131, 133, 134, 137, 138, 140, 145, 146, 148, 152, 161, 162, 164, 168,
176, 193, 194, 196, 200, 208, 224
数直線上に並べるとこんな感じ。
部分的に再帰的な規則はあるっぽいですね。（大きい隙間と小さい隙間の組が入れ子になってる風なところがある）しかし再帰以外の規則が欲しいなと（＾＾；
隣同士の差は、こんな感じです。
7, 4, 2, 1, 5, 2, 1, 3, 1, 2, 7, 2, 1, 3, 1, 2, 5, 1, 2, 4, 11, 2, 1,
3, 1, 2, 5, 1, 2, 4, 9, 1, 2, 4, 8, 19, 2, 1, 3, 1, 2, 5, 1, 2, 4, 9,
1, 2, 4, 8, 17, 1, 2, 4, 8, 16
隣同士の比はこんな感じ。
1.000, 1.571, 1.182, 1.077, 1.357, 1.105, 1.048, 1.136, 1.040, 1.077,
1.250, 1.057, 1.027, 1.079, 1.024, 1.048, 1.114, 1.020, 1.040, 1.077,
1.196, 1.030, 1.014, 1.043, 1.014, 1.027, 1.066, 1.012, 1.024,
1.048, 1.102, 1.010, 1.020, 1.040, 1.077, 1.170, 1.015, 1.008, 1.022,
1.007, 1.014, 1.036, 1.007, 1.014, 1.027, 1.059, 1.006, 1.012, 1.024,
1.048, 1.097, 1.005, 1.010, 1.020, 1.040, 1.077
うう、分からん～（；＿；）。
[参考書]
ビットの数え上げはこの本のルーチン使いました↓
「ハッカーのたのしみ」 ヘンリー・S・ウォーレン、ジュニア著 エスアイビーアクセス発行
(2007-05-12)
Copyright
(C) 2007 Nakayama Masahito