BuringStraw

作用#

求一個排列結果是在全排列中的第幾項

推導#

先照搬 PPT 裡的過程。

舉例：對於集合{1,2,3}，求{3,2,1}是全排列中的第幾項？

那麼，{3,2,1}之前的有三種情況：

1. 第一項 < 3：

   一定在{3,2,1}前，此時第一項有兩種選擇，後兩位隨意，則共有

   種

2. 第一項 = 3：

   則第二項 < 2 時結果小於{3,2,1}

3. 前兩項相等：

   沒有比{3,2,1}小的

總共2*2!+1*1!+0=5種

計算公式#

其中 pi 表示在沒選中的元素中比 ai 小的的數量

逆推#

給定一個序號，求出排列結果。

例：對於集合{1,2,3,4,5,6}，求出全排列的第 100 項（從 0 開始計數）。

這個。。。直接上張 ppt 吧。