中介數

中介數,顧名思義起到中介的作用,是從一個數字到另外一個數字的中間數字。這裡說的中介數,特指在組合數學的全排列生成方法中的中介數,它是一個排列與其序號之間橋樑。

基本介紹

  • 中文名:中介數
  • 套用學科:組合數學
定義,位置計數法,性質,套用,意義,

定義

在組合數學的全排列生成問題里,一個排列與其序號之間是一一對應的關係,在某些全排列生成算法中,如字典序法等,定義了從序號到排列的構造規則,但是二者之間直接轉換比較複雜,因此引入了中介數的概念,中介數顧名思義是起到中介的作用,它的定義如下:
每個排列的序號都可以表示為a1*(n-1)!+a2*(n-2)!+a3*(n-3)!+...+an-1*1!,而a1, a2, a3,...,an-1的某個排列就是該排列的中介數。
說到中介數,則要提到遞增進位制數和遞減進位制數(Wiki: Decreasing Carry)。

位置計數法

進位制/位置計數法是一種記數方式,故亦稱進位記數法/位值計數法,可以用有限的數字元號代表所有的數值。可使用數字元號的數目稱為基數(radix)或底數,基數為n,即可稱n進位制,簡稱n進制。現在最常用的是十進制,還有二進制,十六進制,八進制,甚至是七進制。
此外,在進位制中的基數不一定是固定的大小。
在組合數學的全排列生成算法中,中介數分為兩類:
  • 遞增進位制中介數:從右到左,隨著位數的增加,進位制也從2依次增加,每次增加1
  • 遞減進位制中介數:從右到左,隨著位數的增加,進位制依次減小,從n減到2

性質

中介數有如下的一些性質:
  • 唯一性:每一個排列有唯一的中介數。因為每個排列有唯一的序號,雖然這個序號在不同的方法中是不一樣的,因此根據遞增進位制數或遞減進位制數的特點,可以唯一確定其中介數。
  • 構造性:從中介數可以構造出排列。在全排列生成方法中,定義了從中介數構造排列的規則,利用該規則再加上中介數,可以唯一構造出一個排列,這也是中介數產生的原因。而中介數到序號之間的轉換就變得相對簡單,參見上節定義。
  • 階乘性:這指的是中介數的範圍是元素個數(N)的階乘(N!),即0~N!。這由中介數的定義決定。而這個範圍也是全排列的個數,因此中介數的集合與排列的集合之間是一一對應的關係。

套用

在一些全排列生成算法中,利用中介數來構造排列。例如在字典序法(見全排列)中規定,中介數記錄的是當前數字右邊比當前數字小的數字的個數,該中介數就是遞增進位制數。若使用字典序法來生成1234的全排列,通過中介數(221)↑構造排列的過程如下:
  1. 首先這個排列的四個數的位置都是未知的:_ _ _ _
  2. 從左向右看中介數,第一個2表示4的右邊有2個數比4小,則確定4的位置: _ 4 _ _
  3. 第二個2表示3的右邊有2個比3小,則確定3的位置:3 4 _ _
  4. 第三個1表示2的右邊有1個比2小,則確定2的位置:3 4 2 _
  5. 最後確定1的位置:3 4 2 1
同時可以知道,3421這個排列的序號是2*4+2*3+1*2=16。
在不同的全排列生成算法中,從中介數構造排列的規則是不一樣的。

意義

其實中介數體現的是模型轉換的思想:當一個問題不好直接求解的時候,可以把它轉化為與它等價的一個問題,通過解轉換後的問題來得到問題最終的解。這似乎也給我們的生活帶來一些啟示,當“山窮水復疑無路”,也許換個角度,換個思路,就會“柳暗花明又一村”。
模型轉換模型轉換

相關詞條

熱門詞條

聯絡我們