中介數

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

基本介紹

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

定義

在組合數學的全排列生成問題里，一個排列與其序號之間是一一對應的關係，在某些全排列生成算法中，如字典序法等，定義了從序號到排列的構造規則，但是二者之間直接轉換比較複雜，因此引入了中介數的概念，中介數顧名思義是起到中介的作用，它的定義如下：
每個排列的序號都可以表示為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。
在不同的全排列生成算法中，從中介數構造排列的規則是不一樣的。

意義

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

相關詞條

熱門詞條

聯絡我們