Skip to content
Notes
GitHub

第二章

(nk)=(nn−k)=n!k!(n−k)!\displaystyle{ { n \choose k } = { n \choose n - k } = \frac{ {n !} }{ {k !} {\left( n - k \right) !} } }

随机排列数组

void shuffle(int* a, int n) {
    for (int i = 0; i < n; ++i) {
      swap(a[i], a[rand(i, n)]);
    }
}
void shuffle(int* a, int n) {
    for (int i = 0; i < n; ++i) {
      swap(a[i], a[rand(i, n)]);
    }
}
  • 每次 for 循环之前，每个可能的 i\displaystyle{ i } 排列，数组包含这个 i\displaystyle{ i } 排列的概率是 (n−i)!n!\displaystyle{ \frac{ {\left( n - i \right) !} }{ {n !} } }
  • 终止时 i=n\displaystyle{ i = n }，对于任何排列，出现概率为 1n!\displaystyle{ \frac{ 1 }{ {n !} } }

如果将随机的范围为 [0,n)\displaystyle{ \left[ 0 , n \right) }，数列应该不是随机的

BK=⋂i=1KAiP(Bk)=P(Ak∩Bk−1)=P(Bk−1)P(Ak∣Bk−1)=P(Bk−2)P(Ak−1∣Bk−2)P(Ak∣Bk−1)=P(B1)P(A1∣B1)…P(Ak∣Bk−1)=1⋅n−1n⋅n−2n⋅…⋅n−k+1n=(1−1n)(1−2n)…(1−k−1n)⩽exp⁡(−1n−2n−…−k−1n)=exp⁡(−k(k−1)2n)⩽12\displaystyle{ \begin{aligned}B _{ K } & = \bigcap _{ i = 1 } ^{ K } A _{ i } \\ P \left( B _{ k } \right) & = P \left( A _{ k } \cap B _{ k - 1 } \right) = P \left( B _{ k - 1 } \right) P \left( A _{ k } \mid B _{ k - 1 } \right) \\ & = P \left( B _{ k - 2 } \right) P \left( A _{ k - 1 } \mid B _{ k - 2 } \right) P \left( A _{ k } \mid B _{ k - 1 } \right) \\ & = P \left( B _{ 1 } \right) P \left( A _{ 1 } \mid B _{ 1 } \right) \ldots P \left( A _{ k } \mid B _{ k - 1 } \right) \\ & = 1 \cdot \frac{ n - 1 }{ n } \cdot \frac{ n - 2 }{ n } \cdot \ldots \cdot \frac{ n - k + 1 }{ n } \\ & = \left( 1 - \frac{ 1 }{ n } \right) \left( 1 - \frac{ 2 }{ n } \right) \ldots \left( 1 - \frac{ k - 1 }{ n } \right) \\ & \leqslant \exp \left( - \frac{ 1 }{ n } - \frac{ 2 }{ n } - \ldots - \frac{ k - 1 }{ n } \right) \\ & = \exp \left( - \frac{ k \left( k - 1 \right) }{ 2 n } \right) \leqslant \frac{ 1 }{ 2 }\end{aligned} }