介紹項鍊排列的鄰位互換生成算法
基本介紹
- 中文名：項鍊排列的鄰位互換生成算法
- 屬性：鏈排列
- 對象 ：鄰位互換
- 對應：算法描述
算法定義,算法實現,
算法定義
記集合N={1,2,⋯,)的一個項鍊排列為P1P2P3..PnP1,其中pi∈N,( i=I,2,⋯,n)。
項鍊排列的鄰位互換生成算法算法描述：
n=l,2,3時,集合的項鍊排列只有一種, 唯一的項鍊排列1231;
n≥3時,集後N的所有不同項鍊排列的生成算法。
遞歸調用該算法,生成 Ni=(1,2,⋯ ,n-1)的所有不同的項鍊排列,然後對Ni的每一個項鍊排列分別將n插入該項鍊排列的數Pi之後,其 中 i=n-1,⋯ 2,1,就得到了集合 N= {I,2,⋯ ,n )的所有不同的項鍊排列 。
算法實現
該算法用數組 e[4⋯ n]記錄數 4,5,⋯ ,n上方的箭頭方向 ,若e[k]=-1, 表示數上方的箭頭方向向左 ,若 e[k]=1 ,表 示數上方的箭頭方向向右(4≤k ≤n)。數組 4⋯n]的初值記錄數4,5,⋯,n在項鍊排列12345⋯ n1中的位置,之後利用d[k]之值斷數k是否可以與其上箭頭所指一側相鄰的數進行換位:若 1<d[k]<k ,則表示數k與其上箭頭所指一側相鄰的數a[p]可以進行換位;若d[k]=1,則表示數k在對應的項鍊排序的第2個位置上(從左算起)，需要將k上方的箭頭修改為向右，即令e[k]=1;若d[k]=k,則表示數k在對應的項鍊排序的第n個位置上，需修改數k上方的箭頭向左，即令e[k]=-1, 對數組[1⋯ n]中值的每一次修改,得到一個新的項鍊排列。
