最大の三角形を探す（2）

まず、しらみつぶしに調べてみましょう。といってもこんな風にやるのは無理なので、数を小さくします。N = 10、M = 7としてみました。

#include <iostream>
#include <algorithm>
#include <functional>

const int   N = 10;
const int   M = 7;
int c[M];

bool is_trianble(int *a) {
    return a[0] < a[1] + a[2];
}

int num_iteration(int *a) {
    std::sort(a, a + M, std::greater<int>());
    for(int k = 1; k < M - 1; k++) {
        if(is_trianble(a + k - 1))
            return k;
    }
    return M - 1;
}

void count(int *first, int *last) {
    if(first == last) {
        int n = num_iteration(first - M);
        c[n]++;
    }
    else {
        for(int k = 1; k <= N; k++) {
            *first = k;
            count(first + 1, last);
        }
    }
}

void main() {
    std::fill(c, c + M, 0);
    int a[M];
    count(a, a + M);
    for(int k = 1; k < M; k++)
        std::cout << k << " " << c[k] << std::endl;
}

1 9686925
2 249487
3 48258
4 9450
5 5880
6 0

この方法では限界があるので、今度は疑似乱数を使ってみましょう。

// 省略

int rand_range(int a, int b) {
    int n = rand();
    return a + n * (b - a + 1) / RAND_MAX;
}

// 省略

void init(int *a) {
    for(int n = 0; n < M; n++)
        a[n] = rand_range(1, N);
}

void count() {
    int a[M];
    for(int k = 0; k < (int)1e7; k++) {
        init(a);
        const int   n = num_iteration(a);
        c[n]++;
    }
    for(int k = 0; k < M; k++)
        std::cout << a[k] << " ";
    std::cout << std::endl;
}

void main() {
    std::fill(c, c + M, 0);
    int t = timeGetTime();
    count();
    std::cout << (timeGetTime() - t) * 1e-3 << std::endl;
    for(int k = 1; k < M; k++)
        std::cout << k << " " << c[k] << std::endl;
}

1 9686617
2 250094
3 48127
4 9450
5 5712
6 0

悪くないですね。
他の場合も、N = 20にすると、

1 9687247
2 250750
3 48438
4 8101
5 3464
6 2000

上の方はあまり変わらないですね。このへんは直感と変わらないと思います。
N = 100として、Mを変えて1回で終わる場合をカウントしてみましょう。Mを3から10とします。

3 5000652
4 7498888
5 8750729
6 9374994
7 9688164
8 9843646
9 9922118
10 9960882

どうやら1回目で三角形になる確率は、

p_M ≒ 1 - 2^2-M

となるようですね。