C++: Variadic Template and Fold Expression are Powerful.

这两天做一个Pipeline的Framework,见识了现在C++ Generic Programming 的强大功能,比原来的 Object Oriented Programming 看上去 Cool 多了:完全没有关系的一堆类型,一样可以放在框架里操作,写出来的程序也没有任何效率的损失,看来这些年C++又进步了很多。下面简要说说我的设计。

Class BaseData 表示 Pipeline 中的一个数据节点。 Class Phase 表示针对数据的某个操作。 Phase 接受一些 BaseData 作为输入,并输出到另外一些BaseData。为了灵活和简单起见,Phase 不设任何 Virtual Method 作为接口,只要就实现一个 Run Method 即可。程序概要如下:

class BaseData {
public:
 get() ...
 set() ...
};

class DataA : public BaseData {...};
class DataB : public BaseData {...};
class DataC : public BaseData {...};
class DataD : public BaseData {...};

class Phase {};

class PhaseA : public Phase {
  void Run(DataA*, DataB*, DataC*) {...}
};
class PhaseB : public Phase {
void Run(DataC*, DataD*) {...}
};

class Pipeline {
private:
  DataA a_;
  DataB b_;
  DataC c_;
  DataD d_;

public:
  Run() {
    AddPhase(new PhaseA(), &a_, &b_, &c);
    AddPhase(new PhaseB(), &c_, &d_);
  }

  void AddData(BaseData* base_data) {
     ...
  }

  // This is variadic template.
  template<typename PhaseType, typename... Types>
  AddPhase(PhaseType* phase, Types args...) {

    // This is fold expression, avoid template recursion.
    (..., AddData(args));

    // This is variadic forward.
    std::function<void()> run = 
        std::bind(&PhaseType::Run, phase, args...);
  }
};

程序的精妙全在最后的AddPhase 这个函数,它首先通过一个 Variadic Template 来处理任意接口的函数,然后又通过一个 Fold Expression 对所有的数据进行了类型检查和处理,最后又使用 variadic forward 创建了一个 Closure 供以后调用,真是妙不可言啊。

 

C++ 的一些新感想

因为在工作中C++用的比较多,听说 C++ 17 最近又引入了很多新特性,就买了几本 C++ 的书回来看。看了一阵,感慨颇多,罗列如下:

  • C++ 在 Library 开发人员和普通使用人员之间的鸿沟是越来越大了。新增加的很多特性都是给Library作者提供的,普通用户平时根本用不到。特别的,我以前总是以为所谓 Library 就是在语言之上提供一些包装好的功能模块,现在看到标准库中很多 Type Traits (比如 is_trivially_destructible) 都需要编译器的特殊支持才能实现,远远地超出了我以前的理解范畴。一般的 C++ 用户,如果打开标准库里面的程序想要研究一下某个特性是如何实现的,多半和天书一样看不懂。
  • C++ 现在的救命稻草就是运行时刻的性能了,这集中体现在C++为程序员提供的内存控制上。为此 C++ 几乎牺牲了其他可能的前进方向,并且不惜在语言上增加了巨大的复杂性。C++ 的创始人 Bjarne Stroustrup 前些年还提要在 C++ 中引入自动内存管理,现在是绝口不提了,估计搞出来也没有人用;为了更有效的支持大型对象,C++ 搞出来 Rvalue Reference 和 Move Constructor,让我这样的 C++ 的老鸟程序员也感到太过复杂;更不用提新的 std::string_view,本身大概唯一的作用就是在大字符串上搞一些子串操作比较有效率,结果强行塞进标准库,连 C++ 的资深作者 Nicolai M. Josuttis 都看不下去,在他的书中大声疾呼:string_view is considered harmful! 即便如此追求性能,看着 Programming Language Popularity Trend 上面 C++ 日渐下滑的曲线,我估计日后 C++ 也就只能守着高性能计算这块阵地了。
  • C++ 现在把编译时刻多态搞得很深,这一点其实和 C++ 把性能作为卖点也息息相关。原本是一个编译时刻模板替换的简单玩意,后来发现这个东西因为没有 Virtual table lookup 从而不损失运行时刻的效率,结果在这个方向上一发不可收拾,各种 type traits 如野草般生长,Library 全部都是模板库,里面根据用户提供的类型各种模板特化层出不穷,对于一般的 C++ 程序员来说根本就是天书,唯一的好处就是运行时刻生成的代码都是直接针对用户提供的类型操作的,效率很高。这方面C++阵营一直使用的例子就是 std::sort vs qsort from C。不过在我看来,最初的简单模板替换就已经完成了 90% 的工作,后来加上的一大堆特性,最多不过使得这个编译时刻多态(现在都叫 meta programming了,据称在 Type Domain 还是 Turing Complete)能够在其他 10% 的场合使用一下,实在算是事倍功半的一个好例子吧。

自己呢,还是好好的搞自己的数学,统计,概率,算法等等。这类语言的东西实在不值得深究啊。

Vim Window Management (Vim 多窗口管理)

我一直使用Vim作为编辑器。现在大屏幕显示器越来越流行,使用Vim的时候也越来越多地同时用到多个窗口。为了能够更有效地利用多个窗口,我琢磨着写了一些脚本来更好地在多个窗口之间切换,下面把我学到的知识说一说。

首先我不会写 Vim Script,所以我的脚本都是用 Python写的,不过 Vim的 Python Interface 也很方便,就把脚本写在一个单独的 window.py 文件中,然后在 vimrc 里面加上:

py3file window.py

就可以了。

要想有效的管理窗口,首先需要能够了解当前的窗口分布情况。Vim 的 Python Interface 提供了一个 vim.windows 对象,不过更好的办法是调用 winlayout 这个函数。因为 Vim 中所有的窗口都是从一个主窗口水平或者垂直切分得到的,所以所有的窗口可以表示为一棵递归二叉树。遍历这棵树就可以得到所有窗口的信息,包括其编号、大小,当前位置,父窗口以及其中显示的数据。具体的调用方法如下:

winlayout = vim.eval('winlayout()')

第二个非常有用的命令是 wincmd。Vim提供的绝大部分窗口管理命令都从快捷键 CTRL+W 开始,但是这个快捷键在脚本中使用起来并不方便,这个时候就可以使用wincmd。比如我们要把输入焦点切换到左面的窗口,可以使用:

vim.command('wincmd l')

最后就是创建新窗口和关闭当前窗口的命令,这方面Vim提供了非常繁多的命令,但是对于脚本作者来讲最实用的也就是下面几个:

  • 关闭当前窗口:vim.command(‘close’)
  • 关闭所有其他窗口,只留下当前窗口:vim.command(‘only’)
  • 垂直切分在右面打开新窗口:vim.command(‘rightbelow vnew’)
  • 垂直切分在左面打开新窗口:vim.command(‘leftabove vnew’)
  • 水平切分在下面打开新窗口:vim.command(‘rightbelow new’)
  • 水平切分在上面打开新窗口:vim.command(‘leftabove new’)

有了这些命令以后,我们就可以编写脚本来控制Vim的多个窗口了。我自己写了一个脚本用于管理两个Side by Side 放置的窗口,再加上一些水平切分的支持,结果挺方便的,以后有机会放到 Github 上吧。

等位基因的组合数目

假定某种形状(比如豌豆花的颜色)由一对等位基因控制,其中显性基因用字母A表示,隐性基因用字母a表示。显而易见,我们一共有三种可能的基因型:AA, Aa, aa,分别对应红色、粉色和白色。如果某个等位基因一共有n种可能的变异,即:

(1)   \begin{equation*} A_1, A_2, A_3, ..., A_n \end{equation*}

那么一共有多少种可能的基因型呢(注意基因型A_nA_mA_mA_n 是一样的)?

这个问题看上去很简单,但是我自己却迷惑了很长一段时间。最后我终于认识到:在阅读 William Feller 老爷爷的概率书的这段时间里,自己在经过了相当多的训练之后,已经习惯性的去考虑样本空间内每一个样本的概率是相等的情形了,从这一点讲,那么很明显我们一共有 n \times n 种基因组合的结果。但是问题是这些组合虽然每一个出现的概率相等,但是其中却有一些重复;等到我们把重复的合并以后,剩下的样本出现的概率却不相等了。具体来讲,纯合的基因型:

(2)   \begin{equation*} (A_1, A_1),  (A_2, A_2), (A_3, A_3), ...,  (A_n, A_n) \end{equation*}

要比杂合的基因型

(3)   \begin{equation*} (A_1, A_2),  (A_1, A_3), (A_1, A_4), ...,  (A_{n-1}, A_n) \end{equation*}

出现的概率要低。具体到豌豆花的例子,也就是白色和红色出现的概率分别是 25%,而粉色出现的概率是50%。在领悟到这一点之后,前面给出的题目就很容易计算了:当某个等位基因一共有n种可能的变异的时候,我们可以把所有的可能的组合排成一个 n \times n的表格,其中对角线上的基因型是纯合的,一共有n个,而非对角线上的基因型是杂合的,一共有 n^2 - n 种。考虑到杂合的基因型每种都会出现两次,那么所有不同的基因型一共有:

(4)   \begin{equation*} \frac{n^2 - n}{2} + n = \frac{n(n+1)}{2} \end{equation*}

这和William Feller 老爷爷书中给出的答案完全一致。

排列组合的新思路

排列就是从一个Population 中有序的采样(Sample),组合就是从一个Population中 无序的采样。无论哪种采样,基本的排列组合公式 P_n^r{n \choose r} 都假定Population 中的每一个对象是可以区分的。但是对于Population 中存在不可区分对象的情况(比如 Sampling with Replacement),我们就需要新的思路。我自己对于这个关键的区别一直没有很深刻的理解,直到最近读 William Feller 老爷爷的概率书,才有了一些进展,下面来说一说。

假定一个长度为 n 的二进制字符串,其中有r (0 \le r \le n)个1的字符串有多少?

这个问题中,Population就是 0 和 1,但是它们可以重复出现在最终的采样中,因此简单的排列组合思路并不适用。解决这个问题有两种传统的思路:

  • 思路一:假定我们在这 n 个字符串中 挑选 r 个 1,然后剩下的全部是0,那么可供挑选的总共方案是:

(1)   \begin{equation*} {n \choose r} = \dfrac{n!}{r! \cdot (n-r)!} \end{equation*}

  • 思路二:假定所有的0和1都是可以区分的,那么所有总共可能的方案就是 n! 种,其中有 r 个1 和 n-r 个0。如果这r个1互相可以区分,那么它们总共有 r!的不同的排列方式,相应的对于这些可以区分的0我们也有 (n-r)!种不同的排列方式。现在这些0和1都变成不可区分的了,所以这些不同的排列方式就变成了一种,那么长度为 n 的二进制字符串,其中有r (0 \le r \le n)个1的字符串就有:

(2)   \begin{equation*} \dfrac{n!}{r! \cdot (n-r)!} = { n \choose r} \end{equation*}

这正好就是思路一中的组合数公式,因此两种思路的结果是一样的。 上面的第二种思路讲述起来要比第一种长很多,但是我反而觉得更容易理解,其主要原因是因为它和组合数的公式推导的思路本身就是一致的。组合基本问题:从 n 个可以互相区分的对象中,取出r个对象的不同组合(也就是不考虑这r个对象的顺序)有多少?很明显如果我们考虑这r个对象的顺序,不同的顺序代表不同的组合的话,那么我们一共有:

(3)   \begin{equation*} n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-r+1) \end{equation*}

种不同的方案,这是一个基本的排列问题。现在考虑 r 个不同的对象有多少种不同的排列方式,很明显这也是个基本的排列问题,答案是 r! 种。现在我们看到,如果相同的r个对象的不同排列方式只能算作同一种组合的话,那么 3 对于所有可能的组合就高估了 r! 倍,因此从 n 个可以互相区分的对象中,取出r个对象的不同组合(也就是不考虑这r个对象的顺序)就有:

(4)   \begin{equation*} \dfrac{n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-r+1)}{r!} = \dfrac{n!}{r! \cdot (n-r)!} = { n \choose r} \end{equation*}

沿着这个新思路,我们可以解决一些新的排列组合题目,下面是一些例子。

假定有n面不同的旗帜,要挂在 r 个旗杆上,一共有多少悬挂的方法?

很明显第一面旗帜有 r 种悬挂的方法,注意到有旗帜的那个旗杆现在如果我们要在上面再挂新的旗帜的话,有上面和下面两种选择,所以第二面旗帜有 r+1种悬挂的方法,以此类推,第三面旗帜有 r+2中悬挂的方法,而所有总共的悬挂方法有:

(5)   \begin{equation*} r \cdot (r+1) \cdot (r+2) \cdot ... \cdot (r+n-1) \end{equation*}

现在假定这 n 面旗帜都是一样的(比方说都是普通的红旗),那么考虑到n 个不同的旗帜一共有 n! 种排列方法,现在这些旗帜都变成一样的了,所以上式的估计就比实际高出了 n! 倍,因此当这 n 面旗帜都是一样的时候总共的悬挂方法就有:

(6)   \begin{equation*} \dfrac{r \cdot (r+1) \cdot (r+2) \cdot ... \cdot (r+n-1)}{n!} \end{equation*}

顺便提一句,帖子 组合数学中的分配问题(二):不能区分的对象和可以区分的组中问到的 18 个相同的文件夹在4个不同的人之间分配,每个人接收到的文件夹数量不做限制的话,就可以利用上式计算:

(7)   \begin{equation*} \dfrac{4 \times 5 \times 6 \times ... \times 21}{18!} = 1330 \end{equation*}

最后,如果我们有两种旗帜:p面红旗和q面蓝旗,很明显我们有p+q=n,那么把它们挂到r 个旗杆上的方法,按照上面的思路很容易就得到了:

(8)   \begin{equation*} \dfrac{r \cdot (r+1) \cdot (r+2) \cdot ... \cdot (r+n-1)}{p! \cdot q!} \end{equation*}

William Feller 老爷爷的思路还真是很强大。

家里有两个男孩的概率是多大?

这道概率的题目我以前在知乎上看见人讨论过,当时的背景是量子力学中概率问题。最近又在 William Feller 老爷爷的书中看到了这道题目。经典的概率已经很难了,量子力学中的概率就更是违反直觉。但是无论如何,我还是反对很多人故弄玄虚,把本来很清楚的问题搞得越来越糊涂,相比之下,老爷爷的书讲得很清楚。下面讲一讲这道问题和我的理解。

考虑所有有两个孩子的家庭,假定我们已经知道家里至少有一个男孩,那么这个家里有两个男孩的概率是多大?

如果每个孩子是男是女的概率相等,那么两个孩子的家庭一共有以下四种可能的基本情况:

  • 男孩,男孩
  • 男孩,女孩
  • 女孩,男孩
  • 女孩,女孩

这四种基本情况的概率是相等的,都是 0.25,也就是说家里有两个男孩的概率是0.25。现在我们给出了条件:家里至少有一个男孩。这个条件过滤掉了两个女孩这种基本情况,只剩下三种基本情况,因此家里有两个男孩的概率变为\dfrac{1}{3}。用概率论的术语来描述的话,两个孩子都是男孩这个事件(A)的概率是:

(1)   \begin{equation*} P(A) = 0.25 \end{equation*}

家里至少有一个男孩这句话给出了一个条件(Hypothesis,H),这个条件(或者假设)发生的概率是:

(2)   \begin{equation*} P(H) = 0.75 \end{equation*}

题目所问的问题实际上就是一个条件概率:在家里至少有一个男孩这个条件(H)之下,家里有两个男孩的这个事件(A)发生的概率是多少?这个概率可以用条件概率公式表达如下:

(3)   \begin{equation*} P(A|H) = \dfrac{P(AH)}{P(H)} \end{equation*}

顺便说一下,对于条件概率公式,我觉得下面的表达方式更自然一些:

(4)   \begin{equation*} P(AH) = P(H) \cdot P(A|H) \end{equation*}

我个人常常把它读作:事件A和H同时发生的概率,就是事件H发生的概率 乘以 当事件H发生时事件A将会发生的条件概率。这样的表达式也很容易拓展到多个事件的情况,比如下面:

(5)   \begin{equation*} P(ABC) = P(C) \cdot P(B|C) \cdot P(A|BC) \end{equation*}

现在回到我们的条件概率公式 (3)。 P(H) 我们已经知道是 0.75,但是 P(AH) 是多少呢?考虑事件 AH的具体含义,它表示“两个孩子都是男孩”而且“至少有一个男孩”这两个事件的交集(即同时发生)。参考上面枚举所有情况,很明显这种事件在所有四个事件中只发生了一次,因此 P(AH) = 0.25。把这个数据代入上式,我们就可以计算得出在家里至少有一个男孩这个条件(H)之下,家里有两个男孩的这个事件(A)发生的概率是:

(6)   \begin{equation*} P(A|H) = \dfrac{P(AH)}{P(H)} = \dfrac{0.25}{0.75} = \dfrac{1}{3} \end{equation*}

和我们直觉推理的结果一致。

下面有意思的事情来了,前面的问题可以被改写为下面的形式:假定你有一个朋友,你知道她有两个小孩,其中有一个是男孩。你可以猜测她的家里两个孩子都是男孩的概率是\dfrac{1}{3},这个结果正如我们前面分析的一样。下面假定有一天,你在公园散步 ,遇到你的这位朋友带着一位男孩也在散步,而这个男孩正是你这位朋友的小孩。现在我们要问一个新问题,你这位朋友家里两个孩子都是男孩的概率是多少?

这个新问题可以按照下面的简单思路来回答:你没有看见的那个孩子是男是女的概率是相等的,都是0.5,如果那个没有看见的孩子是男孩,你的朋友就有两个男孩,如果那个没有看见的孩子是女孩,你的朋友就有一男一女。所以对于这个新问题,你这位朋友家里两个孩子都是男孩的概率是0.5。

很明显,这个新问题的答案和我们原来问题的答案不一样,一个是0.5,一个是\dfrac{1}{3}。为什么会是这样子呢?会不会是某一个答案搞错了?我们原来已经知道朋友家里有一个男孩,现在我们只是实际看到了这个男孩。难道看一眼这个男孩确认一下我们已经知道的事实就会导致概率的变化吗?

上面的问题确实很令人迷惑,这也突出体现了概率论这门学科的众多违反直觉之处。实际上,这个新问题和我们前面讨论的问题确实是不同的问题,就像著名的 Monty Hall Problem 一样,某些被呈现的事件实际上被Over Represented。

原来的问题可以看做采样基本对象是家庭:在所有有两个孩子的家庭中,我们把至少有一个男孩的家庭抽取出来排成一队,队列中的每一个项目都是一个家庭;现在我们从这个队列中随机抽取一个家庭,那么抽到有两个男孩的家庭的概率是 \dfrac{1}{3}

而新问题采样的基本对象是男孩:对于所有的有两个孩子的家庭,把所有的男孩都排成一队,队列中的每一个项目都是一个男孩;下来我们从队伍中随机抽取一个男孩,问他来自于两个男孩的家庭的概率是多少。这种情况下他来自于有两个男孩的家庭的概率是0.5。这是因为两个男孩的家庭男孩比其他家庭要多,所以在这个队列中抽到来自两个男孩家庭的男孩的概率也要比其他家庭大。不易察觉的是,对于两个女孩的家庭,由于这些家庭根本没有办法参与到这个队列中来,如果我们加上限制条件,参加队列的家庭是那些至少有一个男孩的家庭(Hypothesis, H),那么抽到来自两个男孩家庭的男孩的概率依然是0.5。这个过程参见下面的图片。


现在我们言归正传,那么前面那个朋友家庭有两个男孩的概率到底是0.5 还是\dfrac{1}{3} 呢?对于这个问题,我的回答是概率只能应用于统计,而不能应用于个体,所以这个问题没有意义呀。 🙁

字母表(Alphabet)的长度为m,单词(Word)的长度为n,字母表中的每一个字母都用到的单词有多少?

字母表(Alphabet)的长度为m,单词(Word)的长度为n,字母表中的每一个字母都用到的单词有多少?这个问题又是一个可以通过递归分析来解决的组合数学题目。

我们先假定这样的单词总数是 X(n, m)。当字母表的长度为m,单词的长度为n的时候,所有可能的单词总数是:

(1)   \begin{equation*} m^n \end{equation*}

在上面这么多单词中,只含有一个字母的单词总数是:

(2)   \begin{equation*} m \end{equation*}

只含有两个字母,并且这两个字母都用到了的单词总数是多少呢?首先从m个字母中选取两个字母的组合数目是:

(3)   \begin{equation*} C_{m}^2 \end{equation*}

而这两个字母组成的长度为 n ,而且这两个字母都用到了的单词,按照我们上面的递归定义则是 X(n, 2)。因为每个组合中的字母都不一样,而每个单词用到了所有的字母,所以所有这些组合代表的字母表形成的单词互相既不重复,又涵盖了所有长度为n而且用到了两个不同字母的单词。综上所述,所有两字母而且这两个字母都被用到的单词总数是:

(4)   \begin{equation*} C_{m}^2 \cdot X(n, 2) \end{equation*}

以此类推,所有三个字母而且这三个字母都被用到的单词总数是:

(5)   \begin{equation*} C_{m}^3 \cdot X(n, 3) \end{equation*}

这样可以一直推到 m-1。另外我们注意到在单词表只有一个字母的情况下,用到这个字母的长度为 n 的单词为 1,也就是 X(n, 1) = 1。那么我们把上面讨论过的只含有一个字母的单词总数可以表示为:

(6)   \begin{equation*} m = C_{m}^1 \cdot X(n, 1) \end{equation*}

我们从所有可能的 m^n 的单词中去除掉那些只有一个字母的单词、二个字母而且每个字母都被用到的单词、三个字母而且每个字母都被用到的单词、…、一直到m-1 个字母而且每个字母都被用到的单词,就得到了 m 个字母都被用到的单词,也就是:

(7)   \begin{equation*} \begin{split} X(n, m) &= m^n \\ &- C_{m}^1 \cdot X(n, 1) \\ &- C_{m}^2 \cdot X(n, 2) \\ &- ... \\ &- C_{m}^{m-1} \cdot X(n, m-1) \end{split} \end{equation*}

上面就是 X(n, m) 的一个递归定义,具体的实现在这里

from math import factorial

# combination
def C(n,m):
  return factorial(n) / (factorial(m) * factorial(n-m))


# Cache table for X, see below.
X_cache = {}

# A vocabulary of size 'm', a sample of size 'n' with replacement,
# How many possible results with all the 'm' items in it.
def X(n, m):
  if (n, m) in X_cache:
    return X_cache[(n, m)]

  if m == 1:
    result = 1
  elif n < m:
    result = 0
  else:
    # Start with total.
    result = int(m ** n)

    for i in range(1, m):
      # Pick a sub-vocabulary with 'i' items, calculate how many
      # samples can be made by using all of them, remove it from total. 
      result = result - C(m, i) * X (n, i)

  X_cache[(n, m)] = result
  return result


def CallX(n, m):
  result = X(n, m)
  print(f'n={n}, m={m}: {int(result)}')

CallX(25, 5)
print(f'Total: {5**25}')
print(X(25, 5) / 5**25)

在William Feller 的老爷爷原题中,字母表中有5个字母,单词的长度是25,问所有字母的出现的概率是多大,按照上面的公式计算我们有:

(8)   \begin{equation*} \dfrac{X(25, 5)}{5^{25}} = \dfrac{292402196893290112}{298023223876953125} = 98.1 \% \end{equation*}

而当字母表中有3个字母,单词的长度是3的时候,所有字母都出现的概率则是:

(9)   \begin{equation*} \dfrac{X(3, 3)}{3^3} = \dfrac{6}{27} = 22.2 \% \end{equation*}

看来单词一变长,基本上所有的字母也就都包括了。 🙂

An informal (picture based) proof of De Morgan’s laws

很多组合数学的问题正向考虑比较困难,反向考虑就容易很多。这种时候,Morgan 定律就排上了用场,下面是该定律的形象化的证明和一个具体应用的例子。

假定有两个集合 A 和 B,Morgan 定律把它们的交集通过补集和并集操作表示如下:

(1)   \begin{equation*} A \bigcap B = \sim ((\sim A)  \bigcup (\sim B)) \end{equation*}

这个定律一个形象化的证明如下:

下面是 Morgan 定律具体应用的例子,假定我们有一个 k 位的数字,每一位上可以是0-9这10个数字,那么既有0又有1的数字一共有多少?

所有总共可能的数字是 (World):

(2)   \begin{equation*} 10^k \end{equation*}

其中没有0的数字 (定义为集合 \sim A) :

(3)   \begin{equation*} 9^k \end{equation*}

其中没有1的数字 (定义为集合 \sim B) :

(4)   \begin{equation*} 9^k \end{equation*}

所有有0的数字(定义为集合A):

(5)   \begin{equation*} 10^k - 9^k \end{equation*}

所有有1的数字(定义为集合B):

(6)   \begin{equation*} 10^k - 9^k \end{equation*}

那么根据 Morgan 定律,又有0又有1的数字就是:

(7)   \begin{equation*} A \bigcap B = \sim ((\sim A)  \bigcup (\sim B)) \end{equation*}

我们已经知道 (\sim A) = 9^k , (\sim B) = 9^k ,关键是 (\sim A)  \bigcup (\sim B) 如何计算,可以看出,既没有0也没有1的数字是:

(8)   \begin{equation*} (\sim A)  \bigcap (\sim B) = 8^k \end{equation*}

所以我们有:

(9)   \begin{equation*} (\sim A)  \bigcup (\sim B) = (\sim A) + (\sim B) - (\sim A)  \bigcap (\sim B) = 9^k + 9^k - 8^k \end{equation*}

最后对于又有0又有1的数字就是:

(10)   \begin{equation*} A \bigcap B = \sim ((\sim A)  \bigcup (\sim B)) = 10^k - (9^k + 9^k - 8^k) \end{equation*}

对于 k=2 的情况,又有0又有1的数字只有两个:0110,按照上面的公式算一下:

(11)   \begin{equation*} 10^2 - (9^2 + 9^2 - 8^2) = 2 \end{equation*}

Feller 老爷爷后面的东西还是很靠谱呀。 🙂

组合数学中的采样(Sample)问题 (三):组合分析计算概率的关键是所有基本事件的概率应该相等

组合分析是概率论的基础。特别的,在利用组合分析计算某个事件的概率时,我们需要确保所有基本事件的概率是相等的。这一点在我刚刚开始学习概率组合分析的时候并不明显,现在经过 William Feller 老爷爷的一番教育,终于开窍了。下面试举两例。

扔一个6面的骰子,每一面出现的概率都是 \dfrac{1}{6},而且这些基本事件的概率是相等的。从这个基础出发,我们可以计算很多与掷骰子有关的概率问题。

桥牌中5张红心在两个敌手之间有三种可能的组合:0-5,1-4 和 2-3。虽然 Partition Number With k-Part Constraint  可以告诉我们总共可能的组合有三种,但是这三种结果的概率并不相同,所以在这里组合分析必须依赖 可以区分的对象和可以区分的组 一文中的技术,否则将会误入歧途。

问题一:6个骰子出现至少一个1点和12个骰子出现至少两个1点,哪个概率大?

六个骰子的所有可能的结果是 6^6 种,1点从不出现的所有可能的结果是5^6 ,所以至少出现一个1点的概率是:

(1)   \begin{equation*} 1 - \dfrac{5^6}{6^6} = 0.6651020233196159 \end{equation*}

十二个骰子的所有可能的结果是 6^{12} 种,1点从不出现的所有可能的结果是5^{12},1点出现一次的概率是 12 \times 5^{11},(第一个因子12 表示从12个骰子中挑出一个,让它的结果是1点,这一共有12种可能。第二个因子 5^{11} 表示剩下的11个骰子每一个都可以从 2、3、4、5、6 这5个数字中任意选择),所以至少出现两个1点的概率是:

(2)   \begin{equation*} 1 - \dfrac{5^{12} + 12 \times 5^{11}}{6^{12}} = 0.6186673737323087 \end{equation*}

6个骰子出现至少一个1点的概率要大一些,虽然直觉告诉我们这两种相等。 🙁

问题二:桥牌中5张红心在两个敌手之间三种可能的组合:0-5,1-4 和 2-3 的概率分别是多大?

正如前面我们所说的,我们把这5张红心当作不同的牌,两个敌手也当作可以区分的对象,那么总共可能的分配是:0-5, 1-4, 2-3, 3-2, 4-1, 5-0 这么六种,0-5 和5-0 分配的总共可能方案是:

(3)   \begin{equation*} \dfrac{5!}{0!5!} + \dfrac{5!}{5!0!} = 2 \end{equation*}

类似的,1-4 和 4-1 分配的总共可能方案是:

(4)   \begin{equation*} \dfrac{5!}{1!4!} + \dfrac{5!}{4!1!}  = 10 \end{equation*}

而 2-3 和 3-2 分配的总共可能方案是:

(5)   \begin{equation*} \dfrac{5!}{2!3!} + \dfrac{5!}{3!2!} = 20 \end{equation*}

总共可能的方案是:

(6)   \begin{equation*} 2 + 10 + 20 = 32 = 2^5 \end{equation*}

所以这三种情况的概率分别是:

  • 0-5:\frac{1}{16} = 6.25\%
  • 1-4:\frac{5}{16} = 31.25\%
  • 2-3:\frac{5}{8} = 62.5\%

红心 1-4 分配的概率比我想象中要高啊。 🙁

组合数学中的采样(Sample)问题 (二):一个人被选中的概率

很多排列组合的题目都需要一个合适的思路用来描述选择的过程,一旦这个过程确定下来,又容易用基本的排列组合方式去描述,那么解决题目就容易的多了。下面就是一个典型的例子:反向思考要比正向思考容易很多。

假定我们要从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是多少呢?

上一个帖子中我们已经讲到过基本采样问题的计算方法,这里的问题需要更进一步从反向去思考,如果我们需要的这个排列不包含A的话,那么总共可供挑选的人数就是 n-1,从中选出r人的总共可能的排列就是:

(1)   \begin{equation*} P_{n-1}^{r} \end{equation*}

而从 n 个中选出 r 个人编为一个排列的总共可能性是:

(2)   \begin{equation*} P_{n}^{r} \end{equation*}

所以从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是:

(3)   \begin{equation*} \dfrac{P_{n-1}^{r}}{P_{n}^{r}} \end{equation*}

那么相应的,从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率就是1减去上面的概率:

(4)   \begin{equation*} 1 - \dfrac{P_{n-1}^{r}}{P_{n}^{r}} = \dfrac{r}{n} \end{equation*}

如果正向去思考,过程要麻烦一些,可以参考下面的思路:假定我们第一个人就选取A,然后剩下的r-1个人从剩下的n-1个人中选取,总共可能的排列是:

(5)   \begin{equation*} P_{n-1}^{r-1} \end{equation*}

同理,如果我们第二个人选取A,然后剩下的r-1个人从剩下的n-1个人中选取,总共可能的排列也是 P_{n-1}^{r-1}。考虑到我们一共需要选取 r 个人,所以总共包含A 的可能的排列就是:

(6)   \begin{equation*} P_{n-1}^{r-1} \cdot r \end{equation*}

那么相应的,从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是:

(7)   \begin{equation*} \dfrac{P_{n-1}^{r-1} \cdot r}{P_{n}^{r}} = \dfrac{r}{n} \end{equation*}

上面的过程是针对选择对象不能重复(No replacement)的情况,所以正向和反向的分析复杂程度差不太多,如果是对象可以重复(With Replacement),反向分析的思路还是差不多:

n 个人中选取 r 个人的总共排列是:

(8)   \begin{equation*} n^r \end{equation*}

如果排除某个固定的人 A,从剩下的 n-1 个人中选取 r 个人的总共排列是:

(9)   \begin{equation*} (n-1)^r \end{equation*}

所以从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是:

(10)   \begin{equation*} 1 - \dfrac{(n-1)^r}{n^r} \end{equation*}

但是如果我们从正向考虑,第一个人就选取A,然后剩下的r-1个人从n个人中随便选取(注意因为每个元素可以选取多次,所以这里是 n 而不是 n-1),总共可能的排列是:

(11)   \begin{equation*} n ^ {r -1 } \end{equation*}

那么以同样的方式考虑第二个、第三个一直到第 r 个人,我们会得出所有包含 A 的排列总数是:

(12)   \begin{equation*} n ^ {r -1 } \cdot r \end{equation*}

这样我们就会得出结论:从 n 个中选出 r 个人编为一个排列,这个排列中包含某个固定的人A 的概率是:

(13)   \begin{equation*} \dfrac{n ^ {r -1 } \cdot r}{n^r} = \dfrac{r}{n} \end{equation*}

反向思考得出的 10 和 正向思考得出的 13 很明显不同。那么哪个是正确的呢?在这里反向思考的结果 10 依然是正确的,而正向思考过高的估计了概率,因为第一个人固定为 A, 然后剩下的人随便选 和 第二个人固定为 A,然后剩下的人随便选,选出来的排列有可能完全相同,我们必须把这些完全相同的排列去掉才能正确的计算排列的总数。