{"id":313248,"date":"2021-01-18T03:35:55","date_gmt":"2021-01-17T19:35:55","guid":{"rendered":"http:\/\/4563.org\/?p=313248"},"modified":"2021-01-18T03:35:55","modified_gmt":"2021-01-17T19:35:55","slug":"%e8%af%b7%e6%95%99%e4%b8%80%e4%b8%8b%e5%90%84%e7%b1%bb%e5%a4%a7%e4%bd%ac-%e8%bf%99%e4%b8%aa%e6%a6%82%e7%8e%87%e9%a2%98%e6%88%91%e9%94%99%e5%9c%a8%e5%93%aa%e9%87%8c","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=313248","title":{"rendered":"\u8bf7\u6559\u4e00\u4e0b\u5404\u7c7b\u5927\u4f6c, \u8fd9\u4e2a\u6982\u7387\u9898\u6211\u9519\u5728\u54ea\u91cc?"},"content":{"rendered":"
\n
\n
\n

\u8bf7\u6559\u4e00\u4e0b\u5404\u7c7b\u5927\u4f6c, \u8fd9\u4e2a\u6982\u7387\u9898\u6211\u9519\u5728\u54ea\u91cc? <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : gulu <\/span> <\/i> 3<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n
\"\"\" \u4ece\u76ee\u6807\u96c6\u5408 S \u4e2d\u6709\u653e\u56de\u5730\u62bd\u53d6 n \u6b21, \u8ba1\u7b97\u5b50\u96c6 s \u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\u81f3\u5c11\u62bd\u4e2d 1 \u6b21\u7684\u6982\u7387. \u76ee\u6807\u96c6\u5408 S \u4e3a [A, A, B, C...] \u8fd9\u79cd\u6709\u91cd\u590d\u7684\u96c6\u5408. \u96c6\u5408 s \u4e3a S \u7684\u5b50\u96c6, \u4e14 s \u4e2d\u4e0d\u5305\u542b\u91cd\u590d\u5143\u7d20. \"\"\"  import time from typing import List from random import Random from functools import reduce   def frac(n):     \"\"\"     n!     \"\"\"     if n <= 1:         return 1      r = 1     while n > 1:         r *= n         n -= 1     return r   def calculate_probability(choices: List[str], targets: List[str], num_draw: int) -> float:     \"\"\"     \u8ba1\u7b97\u6b64\u6982\u7387:\u4ece\u76ee\u6807\u96c6\u5408 choices \u4e2d\u6709\u653e\u56de\u5730\u62bd\u53d6 num_draw \u6b21, targets \u96c6\u5408\u4e2d\u6bcf\u4e2a\u5143\u7d20\u81f3\u5c11\u62bd\u4e2d\u4e00\u4e2a.     targets \u5fc5\u987b\u662f choices \u7684\u5b50\u96c6     \"\"\"     num_choice = len(choices)     num_target = len(targets)     left_draw = num_draw - num_target     targets = {t: choices.count(t) for t in targets}      if left_draw < 0:         print(f\"0.0%\")         return 0.0      # \u76ee\u6807\u96c6\u5408\u6bcf\u4e2a\u9009\u9879\u51fa\u73b0\u7684\u6b21\u6570\u76f8\u4e58, \u4e3a\u76ee\u6807\u96c6\u5408\u7684\u53ef\u80fd\u6570     count = reduce(lambda x, y: x * y, targets.values())     # \u5982\u679c\u62bd\u53d6\u6b21\u6570\u5927\u4e8e\u76ee\u6807\u96c6\u5408\u4e2a\u6570, \u5219\u8fd8\u53ef\u4ee5\u518d\u62bd\u53d6\u82e5\u5e72\u6b21\u4efb\u610f\u5143\u7d20     count *= (num_choice ** left_draw)     # \u4ee5\u4e0a\u83b7\u5f97\u7684\u53ef\u80fd\u6570\u662f\u56fa\u5b9a\u987a\u5e8f\u4e0b\u7684, \u6240\u4ee5\u603b\u7684\u53ef\u80fd\u6570\u9700\u8981\u518d\u4e58\u4ee5 num_draw \u7684\u9636\u4e58     count *= frac(num_draw)      # \u6bcf\u6b21\u62bd\u53d6\u6709 num_choice \u6b21\u53ef\u80fd, \u603b\u5171\u62bd\u53d6 num_draw \u6b21     total = num_choice ** num_draw     p = round(count \/ total * 100, 2)      print(f\"{p}%\")     return p   def observe_probability(choices, targets, num_draw) -> float:     \"\"\"     \u89c2\u5bdf\u6b64\u6982\u7387:\u4ece\u76ee\u6807\u96c6\u5408 choices \u4e2d\u6709\u653e\u56de\u5730\u62bd\u53d6 num_draw \u6b21, targets \u96c6\u5408\u4e2d\u6bcf\u4e2a\u5143\u7d20\u81f3\u5c11\u62bd\u4e2d\u4e00\u4e2a.     targets \u5fc5\u987b\u662f choice \u7684\u5b50\u96c6.     \"\"\"      rand = Random()     rand.seed(time.time() * 1000)     count = 0     total = 1000000      # \u6a21\u62df total \u6b21     for num_test in range(total):         targets = {t: 0 for t in targets}          # \u6bcf\u6b21\u6a21\u62df\u62bd\u53d6 num_draw \u6b21         for draw in range(num_draw):             choice = rand.choice(choices)             if choice in targets:                 targets[choice] += 1          values = list(targets.values())         match = all(map(lambda x: x >= 1, values))         if match:  # \u6240\u6709\u76ee\u6807\u90fd\u62bd\u5230, \u8ba1\u6570\u52a0 1             count += 1      p = round(count \/ total * 100, 2)     print(f\"{p}%\")      return p   def test():     choices = [         \"A\", \"A\", \"A\", \"A\",         \"B\", \"B\", \"B\", \"B\",         \"C\", \"C\", \"C\", \"C\",         \"D\",         \"E\",     ]     targets = [\"A\", \"B\", \"C\", \"D\"]     num_draw = 5      observe_probability(choices, targets, num_draw)     calculate_probability(choices, targets, num_draw)   if __name__ == \"__main__\":     test() <\/code><\/pre>\n<\/p><\/div>\n
 \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (18<\/span>)        <\/div>\n
 <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
    \n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : ConradG <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u63a8\u6d4b\u662f\u7ed3\u679c\u504f\u5927\uff1f
    \u5982\u679c\u662f\uff0c\u95ee\u9898\u51fa\u5728\u201c\u5982\u679c\u62bd\u53d6\u6b21\u6570\u5927\u4e8e\u76ee\u6807\u96c6\u5408\u4e2a\u6570, \u5219\u8fd8\u53ef\u4ee5\u518d\u62bd\u53d6\u82e5\u5e72\u6b21\u4efb\u610f\u5143\u7d20\u201d\u3002
    \u5982\u679c\u628a\u56db\u4e2a A \u4f9d\u6b21\u6807\u8bb0\u4e3a a1 \u5230 a4\uff0c\u5219 ABCD+A \u8fd9\u79cd\u5f62\u5f0f\u6309\u7167 LZ \u7684\u8ba1\u7b97\u65b9\u6cd5\u4f1a\u51fa\u73b0 a1BCD+a2 \u548c a2BCD+a1 \u7684\u91cd\u590d                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : necomancer <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u6709\u6807\u51c6\u7b54\u6848\u5417\uff1f\u5047\u5b9a s \u662f s \u96c6\u5408\u7684\u957f\u5ea6\uff0c\u4e14 P_{i=1,2,…,s} \u662f\u62bd\u5230 s \u4e2d\u6bcf\u4e2a\u5143\u7d20\u7684\u6982\u7387\uff0c\u90a3\u4e48\u5f53 n < s \u7684\u65f6\u5019\u6982\u7387\u662f 0\uff0c\u5f53 n > s \u7684\u65f6\u5019\u662f P_{n}^s Pi_{i=1}^s p_i                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : necomancer <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 n>=s                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : vance123 <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u4e0d\u5c31\u662f\u968f\u673a\u64ad\u653e\u6b4c\u5355\uff0c\u5e73\u5747\u591a\u5c11\u6b21\u624d\u80fd\u542c\u5b8c\u6240\u6709\u6b4c\u7684\u53d8\u4f53\u5417\uff0c\u6211\u8bb0\u5f97\u671f\u671b\u597d\u50cf\u662f 7 \u70b9\u51e0                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : necomancer <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u6211\u611f\u89c9\u6a21\u62df\u53ef\u4ee5\u8fd9\u4e48\u505a\uff0c\u53cd\u6b63\u662f\u6709\u653e\u56de\u62bd\u6837\uff0c\u90a3\u6bcf\u6b21\u62bd\u5230\u67d0\u4e2a\u5143\u7d20\u7684\u6982\u7387\u90fd\u662f\u7ed9\u5b9a\u7684\uff0c\u6240\u4ee5\u76f4\u63a5\u5f53 n>=s \u7684\u65f6\u5019\u5c31\u4ece\u4e00\u4e2a s+1 \u7684\u6570\u7ec4 S=s+np.inf \uff08\u968f\u4fbf\u4e00\u4e2a\u4ec0\u4e48\u4e1c\u897f\uff09\u6309\u6982\u7387 ps={p_1,p_2,….,p_s,1-sum_i^s p_i}\uff0c\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u53ea\u8981\u548c\u5176\u4ed6\u7684\u90fd\u4e0d\u4e00\u6837\u5c31\u884c\u4e86\uff0c\u7528
    out = np.random.choice(S, size=n,p=ps)\uff0c\u7136\u540e\u7528\u4e2a histogram \u6216\u8005 hash \u5224\u5b9a\u4e00\u4e0b\uff1f                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : gulu <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 @ConradG 
    \u7ed3\u679c\u662f\u504f\u5927\u4e86\u3002
    \u4e0d\u8fc7 a1BCD+a2 \u548c a2BCD+a1 \u4e3a\u4ec0\u4e48\u7b97\u7b97\u91cd\u590d\u7684\u5462\uff1f\u987a\u5e8f\u4e0d\u540c\u5440\u3002\u5206\u6bcd\u4e5f\u662f\u548c\u987a\u5e8f\u6709\u5173\u7684\u6392\u5217\uff0c\u4e0d\u662f\u7ec4\u5408\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : gulu <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 @necomancer 
    \u6211\u611f\u89c9\u6a21\u62df\u7684\u7ed3\u679c\u662f\u6b63\u786e\u7684\uff0c\u5e94\u8be5\u662f\u8ba1\u7b97\u7684\u65b9\u6cd5\u51fa\u9519\u4e86\u5427                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : ConradG <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 @gulu 
    \u56e0\u4e3a\u4f60\u5728\u6700\u540e\u4e00\u6b65\u201ccount *= frac(num_draw)\u201d\u7b97\u4e86\u4e00\u6b21\u5168\u6392\u5217\uff0c\u90a3\u4e48\u5c31\u8981\u6c42\u4e4b\u524d\u7684\u7edf\u8ba1\u7ed3\u679c\u662f\u65e0\u5e8f\u7684\u3002\u800c\u6211\u63d0\u5230\u7684\u91cd\u590d\u662f\u51fa\u73b0\u5728\u7b2c\u4e8c\u6b65\u7ed3\u675f\u65f6\u5019\u3002<\/p>\n
    \u987a\u4fbf\u8fd9\u7c7b\u95ee\u9898\u7684\u5e38\u89c4\u89e3\u6cd5\u662f\u5199\u6210\u9012\u5f52\u3002                                                            <\/p><\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : gulu <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 @ConradG 
    \u975e\u5e38\u611f\u8c22\u5927\u4f6c\uff0c\u6211\u603b\u7b97\u77e5\u9053\u9519\u5728\u54ea\u4e86\u3002
    \u80fd\u5426\u518d\u8bf7\u6559\u4e00\u4e0b\uff0c\u8fd9\u7c7b\u95ee\u9898\u6709\u6240\u5c5e\u7684\u4e13\u6709\u540d\u8bcd\u5417\uff1f\u6211\u60f3\u9488\u5bf9\u6027\u5730\u518d\u7cfb\u7edf\u5b66\u4e60\u4e00\u4e0b\u3002
    \u6982\u7387\u8bba\u7684\u8303\u7574\u592a\u5927\u4e86\uff0c\u73b0\u5728\u770b\u5f97\u6709\u70b9\u5934\u5927\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : necomancer <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u6211\u597d\u50cf\u4e5f\u7b97\u5927\u4e86…. \u7b49\u6982\u7387\u7684\u8bdd\u8fd8\u6709\u529e\u6cd5\u7684\uff0c\u53ef\u4ee5\u8868\u8fbe\u6210 s! S_2(n, s)\uff0c\u6211\u8bb0\u5f97\u8fd9\u4e2a\u53eb\u4f18\u60e0\u5238\u95ee\u9898\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : necomancer <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 p(n,s) = sum_{j=0}^{s-1} (-1)^{s-1-j}C_{m-j-1}^{m-c}sum_{|J|=j}P_J^{n-1}(1-P_J)….(1)
    \u5176\u4e2d
    P_J \u662f\u5b50\u96c6\u6982\u7387\u52a0\u548c\uff0cP_J := sum_{iin J} p_i, sum_{|J|=j} \u4ee3\u8868\u5bf9\u6240\u6709 |J|=j \u5927\u5c0f\u7684\u5b50\u96c6\u7684\u52a0\u548c,m \u4ee3\u8868\u603b\u72ec\u7acb\u5143\u7d20\u4e2a\u6570\u3002\u5bf9\u5747\u5300\u5206\u5e03\u6765\u8bf4\uff0c
    p(n,s) = m! S_2(n-1, s-1)\/((m-s)! m^n)….(2)<\/p>\n
    \u8fd9\u4e48\u770b\u597d\u50cf\u6a21\u62df\u7684\u65f6\u5019\u4e0d\u80fd\u628a m \u4e2a\u72ec\u7acb\u5143\u7d20\u4e2d\u9009\u62e9 s \u4e2a\u6298\u5408\u6210 s+1 \u91cc\u9009 s \u4e2a\u2026\u2026                                                            <\/p><\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : necomancer <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 Google \u4e86\u4e00\u4e0b Coupon collector’s problem \u53d1\u73b0\u8fd9\u73a9\u610f\u513f\u597d\u50cf\u8fd8\u5f88\u96be                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : necomancer <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u57fa\u7840\u77e5\u8bc6\u7684\u8bdd\u5f97\u770b\u770b\u505c\u65f6\u548c\u9785\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : gulu <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 @necomancer 
    \u8c22\u8c22\u5927\u4f6c\uff0c\u6211\u53bb\u5b66\u4e60\u4e00\u4e0b                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : gulu <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 @necomancer 
    \u8001\u54e5\uff0c\u6211\u521d\u6b65\u770b\u4e86\u4e00\u4e0b\u201c\u96c6\u5238\u201d\u95ee\u9898\uff0c\u611f\u89c9\u548c\u6211\u8fd9\u4e2a\u95ee\u9898\u6709\u70b9\u4e0d\u4e00\u6837\u3002<\/p>\n
    \u96c6\u5238\u95ee\u9898\uff1a
    Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once? 
    \u6709 n \u5f20\u4f18\u60e0\u5238\uff0c\u6709\u653e\u56de\u5730\u62bd\u53d6\u591a\u5c11\u6b21\uff0c\u624d\u80fd\u4fdd\u8bc1\u6bcf\u5f20\u5238\u62bd\u53d6\u5230\u81f3\u5c11\u4e00\u6b21\uff1f<\/p>\n
    \u6211\u7684\u95ee\u9898\uff1a
    \u6709 N \u5f20\u4f18\u60e0\u5238\uff0c\u4e0d\u5e73\u5747\u5730\u5206\u7c7b\u4e3a n \u79cd\u3002\u6709\u653e\u56de\u5730\u62bd\u53d6\u591a\u5c11\u6b21\uff0c\u624d\u80fd\u4fdd\u8bc1 m \u79cd\u4f18\u60e0\u5238\u81f3\u5c11\u62bd\u53d6\u5230\u4e00\u6b21\uff1f                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : HelloViper <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u653e\u56de\u53d6 n \u6b21 == len(S)^n ,
    \u76f4\u63a5 product \u51fa\u7b1b\u5361\u5c14\u79ef\uff0c\u7136\u540e\u904d\u5386 set \u540e s \u662f\u5426 in \u5c31\u7ed3\u4e86                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : necomancer <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u4f60 Google \u4e00\u4e0b coupon collector’s problem with unequal probability of subset? 
    @gulu                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : gulu <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 @necomancer 
    \u8fd9\u5c31\u53bb\u770b\u770b                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n","protected":false},"excerpt":{"rendered":"
    \u8bf7\u6559\u4e00\u4e0b\u5404\u7c7b\u5927\u4f6c, \u8fd9\u4e2a\u6982\u7387\u9898\u6211\u9519…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/313248"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=313248"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/313248\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=313248"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=313248"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=313248"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}