1467. Probability of a Two Boxes Having The Same Number of Distinct Balls

参考：花花酱的解

问题：

给定c_n个颜色的多个球。balls[i]表示：第i个颜色的球数。

将这些球平均分装两个盒子。每个盒子球数相同。

求最终两个盒子中球色种类数相同的装法概率。

Example 1:
Input: balls = [1,1]
Output: 1.00000
Explanation: Only 2 ways to divide the balls equally:
- A ball of color 1 to box 1 and a ball of color 2 to box 2
- A ball of color 2 to box 1 and a ball of color 1 to box 2
In both ways, the number of distinct colors in each box is equal. The probability is 2/2 = 1

Example 2:
Input: balls = [2,1,1]
Output: 0.66667
Explanation: We have the set of balls [1, 1, 2, 3]
This set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equale probability (i.e. 1/12):
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
After that we add the first two balls to the first box and the second two balls to the second box.
We can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box.
Probability is 8/12 = 0.66667

Example 3:
Input: balls = [1,2,1,2]
Output: 0.60000
Explanation: The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box.
Probability = 108 / 180 = 0.6

Example 4:
Input: balls = [3,2,1]
Output: 0.30000
Explanation: The set of balls is [1, 1, 1, 2, 2, 3]. It is hard to display all the 60 possible random shuffles of this set but it is easy to check that 18 of them will have the same number of distinct colors in each box.
Probability = 18 / 60 = 0.3

Example 5:
Input: balls = [6,6,6,6,6,6]
Output: 0.90327
 
Constraints:
1 <= balls.length <= 8
1 <= balls[i] <= 6
sum(balls) is even.
Answers within 10^-5 of the actual value will be accepted as correct.

　　

解法：Backtracking（回溯算法）

• n：总球数
• c_n：总颜色数

1. 解法一：最简单的想法，暴力求解（运行会超时TLE）

• 状态：当前pos上选择的球，
• 选择：所有颜色中，剩下球数!=0的球。
• 退出递归条件：
  • pos==球数n：找到一个排列res_all
  • 获得一个符合条件的解：box1中的颜色数==box2中的颜色数。：res_same

最终要求的概率为：res_same/res_all

代码参考：

class Solution {
public:
    /*int count=0;
    void print_intend() {
        for(int i=0; i<count; i++) {
            printf("  ");
        }
    }
    void print_path(vector<int>& path) {
        for(int i:path) printf(" %d", i);
        printf(" path.size=%d
", path.size());
    }*/
    int n=0;
    int c_n=0;
    void backtrack(int& res_all, int& res_same, int pos, 
                   unordered_set<int>& box1, unordered_set<int>& box2, vector<int>& balls) {
        if(pos==n) {
            res_all++;
            if(box1.size()==box2.size()) {
                res_same++;
       //     print_intend();
       //     print_path(path);
       //     print_intend();
       //     printf("return res_all:%d, res_same:%d
", res_all, res_same);
            }
            return;
        }
       // print_intend();
       // print_path(path);
       // print_intend();
       // printf("pos:[%d]
", pos);
        for(int i=0; i<balls.size(); i++) {
            if(balls[i]!=0) {
                balls[i]--;
              //  count++;
                if(pos<n/2) {//box1
                    if(box1.count(i)!=0) {
                        backtrack(res_all, res_same, pos+1, box1, box2, balls);
                    } else {
                        box1.insert(i);
                        backtrack(res_all, res_same, pos+1, box1, box2, balls);
                        box1.erase(i);
                    }
                } else {//box2
                    if(box2.count(i)!=0) {
                        backtrack(res_all, res_same, pos+1, box1, box2, balls);
                    } else {
                        box2.insert(i);
                        backtrack(res_all, res_same, pos+1, box1, box2, balls);
                        box2.erase(i);
                    }
                }
              //  count--;
                balls[i]++;
            }
        }
       // print_intend();
       // printf("return res_all:%d, res_same:%d [loop try final]
", res_all, res_same);
        return;
    }
    double getProbability(vector<int>& balls) {
        double res=0;
        int res_all=0, res_same=0;
        unordered_set<int> box1, box2;
        for(int b:balls) n+=b;
        c_n = balls.size();
        backtrack(res_all, res_same, 0, box1, box2, balls);
        res = (double)res_same/res_all;
       // printf("res_same:[%d], res_all:[%d]
", res_same, res_all);
        return res;
    }
};

2. 解法二：

• 状态：对当前颜色位置c_pos，分别选择到box1的球n1 和 box2的球n2。
  • (box1中的颜色数c_n1，box2中的颜色数c_n2
  • 到目前为止，box1的待求所有排列分母p1，box2的待求所有排列分母p2)
• 选择：当前颜色的球数balls[c_pos]中，选择0～all到box1，余下的all～0则全部放在box2中。
• 退出递归条件：
  • 当前：box1的总球数>n/2 or box2的总球数>n/2 -> 直接退出，这种选择不满足题目要求。
  • c_pos==c_n：找到一个组合，
    • 在这种组合中，有多少种排列count
    • = box1的所有排列   *   box2的所有排列 =
    • box1球数n1的阶乘/box1颜色1球数阶乘*颜色2阶乘...*颜色c_n1阶乘    *   
    • box2球数n2的阶乘/box2颜色1球数阶乘*颜色2阶乘...*颜色c_n2阶乘
  • 加入总结果：res_all+=count
  • 获得一个符合条件的解：box1中的颜色数c_n1==box2中的颜色数c_n2。：res_same += count

代码参考：

class Solution {
public:
    //阶乘计算的结果 总共球数最多8*6=48，最多计算的阶乘:48!=fact[48]
    vector<double> fact;
    /*int count=0;
    void print_intend() {
        for(int i=0; i<count; i++) {
            printf("  ");
        }
    }
    void print_path(vector<int>& path) {
        for(int i:path) printf(" %d", i);
        printf(" path.size=%d
", path.size());
    }*/
    int n=0;//ball num
    int c_n=0;//color num
    //选择当前颜色c_pos的情况：
    //当前状态：box1中：已经选了n1个球，共c_n1种颜色。各色颜色球排列后的分母p1：颜色1!*颜色2!*...*颜色c_n1!
    //      ：box2中：已经选择了n2个球，共c_n2种颜色。各色颜色球排列后的分母p2：颜色1!*颜色2!*...*颜色c_n2!
    void backtrack(double& res_all, double& res_same, int c_pos, 
                   int n1, int n2, int c_n1, int c_n2,
                   double p1, double p2, vector<int>& balls) {
        if(n1>n/2 || n2>n/2) return;//任意一个box中的球超过总球数一半
        if(c_pos==c_n) {//颜色选完
            //计算当前这种颜色选法，的所有排列可能count
            //=box1的所有排列可能*box2的所有排列可能
            double count = fact[n1]/p1 * fact[n2]/p2;
            res_all += count;
            if(c_n1==c_n2) res_same += count;
            return;
        }
        
        //s1:给box1，选择颜色c_pos的球，0个～balls[c_pos]全部
        //s2:给box2，c_pos颜色中剩下的球：balls[c_pos]-s1
        for(int s1=0; s1<=balls[c_pos]; s1++) {
            int s2 = balls[c_pos]-s1;
            backtrack(res_all, res_same, c_pos+1,
                      n1+s1, n2+s2, c_n1+(s1!=0), c_n2+(s2!=0),
                     p1*fact[s1], p2*fact[s2], balls);
        }
        return;
    }
    double getProbability(vector<int>& balls) {
        double res=0.0;
        double res_all=0.0, res_same=0.0;
        for(int b:balls) n+=b;
        c_n = balls.size();
        //求阶乘结果
        fact.resize(50,1);
        fact[0] = 1.0;
        for(int i=1; i<fact.size(); i++) {
            fact[i] = fact[i-1]*i;
        }
        
        backtrack(res_all, res_same, 0, 0, 0, 0, 0, 1.0, 1.0, balls);
        res = res_same/res_all;
       // printf("res_same:[%d], res_all:[%d]
", res_same, res_all);
        return res;
    }
};