56个相亲对象凑齐12星座的概率

昨天逛豆瓣看到这篇访谈：相亲了56次，我结婚了文章，除了观摩文章主题本身的独特风格外，里头也提到了一个问题：相亲56次，凑齐12星座的可能性多大？于是我整理了一下思路，写了这篇文章。

我的思路基于以下假设：

• 每个人是什么星座的概率是相等的，即1/12.
• 相亲的56个人的星座相互独立.

在上述两个假设的基础上，对于这个群体，其可能包含的星座数为1，2，3，... ,11,12. 那么要求得包含12星座的概率，用必然事件的概率1减去只包含1个，2个，直到11个的概率， 便可得到。即：

p(12/56) = 1 - p(11/56) - p(10/56) - ... - p(2/56) - p(1/56).

其中 p(i/56) = [C(12,i) * i^56] / ( 12^ 56) , C(12,i)是从12个星座中选取i个的组合数，其定义为 C(12,i) = 12!/( i! * (12-i)!) ).

既然p(i/56)的定义公式已经给出，那么其具体算法实现就很简单,以下是一个简单的java实现：

//给定样本总量为n，对于单个样本，其属性有m个可能的取值，且概率相等
    //比如，假设随机相亲了56个人，这56个人是什么星座相互独立，求这56个人集齐了12星座的概率。。
    //这里用到了间接法，即计算只集齐了11，10，9，...,2,1个星座的概率，那么集齐了12星座的概率是1-sum
    public double getNegativeSum(int n, int m){
        double result = 0;
        for(int i = 1; i < m; i++){
            result = result + ( getCombinationSum(m,i) * getPowerValue(i,n) );
        }
        return result / getPowerValue(m,n);
    }

其中getCombinationSum(int m, int i)计算组合数C(m,i),getPowerValue(int m, int n)计算m的n次方，其具体实现如下：

//计算m的n次方
    private double getPowerValue(double m, double n){
        return Math.pow(m, n);
    }

//计算从n个不同元素中取出m个元素的组合数 （ n >= m）
    private double getCombinationSum(int n, int m){
        double tmp_n = getFactorial(n);
        double tmp_m = getFactorial(m);
        double tmp_n_m = getFactorial(n-m);
        return tmp_n / (tmp_m * tmp_n_m);
    }

其中getFactorial(int m)是计算m的阶乘，其具体实现如下：

//计算m的阶乘
    private double getFactorial(int m){
        int result = 1;
        if (m == 1 || m == 0){
            return result;
        }
        for(int i = 1; i < m ; i++){
            result = result * (i+1);
        }
        return result;
    }

所以问题56个相亲对象凑齐12星座的概率的答案是：
1 - getNegativeSum(56,12)，约等于0.91.
具体源码请点击这里.