劉 峰

（中國運載火箭技術研究院研究發(fā)展中心，北京，100076）

0 引 言

飛行器研制過程如圖1所示，通常采用六自由度仿真試驗考核飛行器控制系統的性能，通過遍歷飛行器偏差模型前幾項的極限工況，評估偏差項對系統性能的影響程度，找出影響的主要因素。當偏差項有序關聯時，需要通過選排列方式遍歷偏差模型的前幾項，當偏差項相互獨立時，只需要通過組合方式遍歷偏差模型的前幾項。

傳統上的排列組合遍歷方法中[1,2]，特別是組合遍歷，采用傅克慎[3]法的具有較高的運算效率，但生成的組合遍歷序列不具備有序性。趙天玉[4]法體現了遞歸思想，給出了組合構造與序號的函數對應關系，但全面的構造有損運算效率；王孫安等文獻[5～8]給出了組合遍歷的算法研究與應用實例。

圖1 飛行器控制系統六自由度仿真試驗設備示意Fig.1 Six Degree of Freedom Simulation Test Equipment for Aircraft Control System

本文提出多種遍歷算法，分別為全排列遍歷和組合遍歷的序數解析算法和單步遞推算法，從形式上采用序數解析方式或單步遞推方式便于不同遍歷的相互嵌套應用，生成的組合遍歷序列具備有序性，基于運算量優(yōu)選得到全排列遍歷和組合遍歷的單步遞推算法，遍歷序列有序，有利于事后開展偏差因素影響對比分析等工作。

1 排列組合算法原理

1.1 排列組合基本公式

由《數學手冊》第1.1節(jié)[1]和《實用數學手冊》第1.3節(jié)[2]可知，從n個不同的元素中，每次取出n個不同的元素，按一定的順序排成一列，稱為全排列，其排列種數為

從n個不同的元素中，每次取出k個不同的元素，不管其順序合并成一組，稱為組合，其組合種數為不同的元素，按一定的順序排成一列，稱為選排列，其排列種數為

從n個不同的元素中，每次取出k個

可知，選排列可以表示成組合下嵌套全排列。

1.2 全排列遍歷的序數解析

在交換實現排列中，在從1～n的基本整數序列的基礎上，根據商數序列調整基本整數序列中數據項的位置，實現當前排列序列。當商數序列的當前值為零時，表示將基本整數序列當前下標的非零值移到排列序列的對應位置，基本整數序列的當前值為零時，自動向后搜索，在移動后將基本整數序列的被移動值清零；當商數序列的當前值為正i時，表示將基本整數序列當前后第i個下標的非零值移到排列序列的對應位置，基本整數序列的當前值為零時，自動向后搜索，以此類推，得到商數序列d，使得：在移動后將基本整數序列的被移動值清零。

全部移動完畢后，基本整數序列被全清零，得到的排列序列即為序數解析后對應全排列遍歷中某一特定的排列。

1.3 組合遍歷的序數解析

在確定分支中，按照楊輝三角將數據分解為路徑，確定左右支路，左小右大，則左支路取1、右支路取0。根據組合遞推計算公式有

通過左右支路向上遍歷到楊輝三角的頂部后，得到的組合序列即為序數解析后對應組合遍歷中某一特定的排列。

1.4 單步遞推中關于整數序列的名詞解釋

全排列遍歷或組合遍歷中，首先生成整數序列，從左到右，該序列的左端第 1項稱為首項或左端項，左端第2項稱為次項，右端第1項稱為末項或右端項；在搜索過程中，當前搜索索引對應項稱為當前項，鄰近當前項的左側第 1項稱為左側項，鄰近當前項的右側第1項稱為右側項。

1.5 全排列遍歷的單步遞推

單步遞推時，從數列右端向左搜索，若當前項大于左側項，則停止搜索，完全顛倒從右端項到當前項的所有項的順序，然后在右端項到當前項序列中找出比左側項大的最小項，并將其與左側項交換，由此生成新的序列，作為當前全排列遍歷的單步遞推結果。

當搜索序列到次項仍不滿足當前項大于左側項的條件，即此時首項大于次項，數列從左到右按照從大到小排列，則單步遞推過程中止，循環(huán)結束，流程圖如圖2所示。

圖2 全排列單步遞推的算法流程Fig.2 Single Step Recursive Algorithm for Full Permutation

1.6 組合遍歷的單步遞推

單步遞推時，從數列右端向左搜索，若當前項大于左側項，則停止搜索，完全顛倒從右端項到右側項的所有項的順序，交換當前項與左側項，由此生成新的序列，作為當前組合遍歷的單步遞推結果。

當搜索序列到次項仍不滿足當前項大于左側項的條件，即此時首項與次項均為1，數列從左到右的k項為1，剩余項賦值為0，則單步遞推過程中止，循環(huán)結束，流程如圖3所示。

圖3 組合單步遞推的算法流程Fig. 3 Combined Single Step Recursive Algorithm Flow

全排列遍歷和組合遍歷的單步遞推算法生成的序列存在有序性，故沒有重復確保唯一；單步遞推算法從遞歸角度迭代次數符合全排列遍歷和組合遍歷的性質，故沒有遺漏確保完備。

2 排列組合算例推演與分析

2.1 算法的軟件開發(fā)環(huán)境

排列組合遍歷算法基于Windows操作系統，采用Visual C++ 6.0（VC6）編譯環(huán)境和C語言開發(fā)，以VC6提供的編譯環(huán)境進行指令條數統計。為給出直觀的可比性，統計Math.h中基本數學函數的指令條數如表1所示（取x=0.618）。計算其全排列序列。首先依次整除4!3!2!1!，得到商數序列A如下：

表1 基本數學函數的指令條數Tab.1 Mumber of Instructions for Basic Mathematical Functions

2.2 全排列遍歷序數解析的算例

在序數解析時，取n=5時的序數s=59，

第1步：A中第1項為2，則將N中非零首項后的第2項移到P中，原位置清零得到：

式中 ?表示空位。

第2步：A中第2項為1，則將N中非零首項后的第1項移到P中，原位置清零得到：

依此類推，最后得到目標序列：

仿真分析可知，軟件中生成每個排列的平均指令數為340.00條。

2.3 組合遍歷序數解析的算例

仿真分析可知，軟件中生成每個組合的平均指令數為256.68條。

2.4 全排列遍歷單步遞推算例與統計分析

在單步遞推時，取n=5的某一組全排列狀態(tài)如下：

從數列右端向左搜索，當前項5大于左側項2，停止搜索，有：

完全顛倒從右端項1到當前項5的所有項順序，有：

在右端項到當前項序列中找出比左側項大的最小項4，并將其與左側項2交換，由此生成新的序列，作為當前組合遍歷的單步遞推結果如下：

單步遞推時，計算 5n=的所有全排列狀態(tài)的軟件指令條數如圖 3所示。生成每個組合平均指令數為91.43條。

圖4 所有全排列狀態(tài)的軟件指令條數Fig.4 Number of Software Instructions in All Arranged States

在單步遞推時，計算不同n工況下的所有全排列狀態(tài)的軟件指令條數如表2所示。

表2 不同工況下全排列狀態(tài)的軟件指令條數Tab.2 Number of Software Instructions in Full Arrangement under Different Working Conditions

從數列右端向左搜索，若當前項1大于左側項0，得到第1個連續(xù)非零的序列，則停止搜索，有：

完全顛倒從右端項到右側項的所有項的順序，交換當前項與左側項，由此生成新的序列，作為當前組合遍歷的單步遞推結果如下：

2.5 組合遍歷單步遞推算例與統計分析

單步遞推時，取n=7，k=5某一組組合狀態(tài)如下：

在完全顛倒順序的算法中采用折半法可以提高運算效率。

圖5 所有組合狀態(tài)的軟件指令條數Fig.5 Number of Software Instructions in AllCombination States

在單步遞推時，計算不同n與k組合工況下的所有組合狀態(tài)的軟件指令條數如表3所示。

表3 不同組合工況下組合狀態(tài)的軟件指令條數Tab.3 Number of Software Instructions under Different Combination Conditions

2.6 在偏差仿真中的應用

以某飛行器為例，在偏差仿真中共考慮 7n=項偏差，從中隨機選擇 3k=項進行打靶仿真，則構造初始組合數列如下：

其中，按照順序的某一位為1時表示選擇7項中的某一項，為 0時表示不選，然后可通過單步遞推實現偏差項的取舍，從而實現對偏差項的全局遍歷。

假設 7項偏差分別為：大氣密度、水平風、氣動系數、全彈質量、飛行器質量、大氣壓強和風向角，隨機選取3項進行組合遍歷的選取狀態(tài)如圖6所示。

圖6 7項偏差下的組合遍歷狀態(tài)Fig.6 Combinatorial Ergodic States under 7 Deviations

續(xù)圖6

通過帶制導的偏差仿真得到組合偏差下熱流和動壓的最大值如圖7所示。

圖7 組合偏差下的熱流和動壓Fig.7 Heat Flow and Dynamic Pressure under Combined Deviations

通過分析可知，氣動系數和水平風為影響熱流的主要因素，氣動系數和大氣密度為影響動壓的主要因素。取一項偏差進行遍歷的結果與極限偏差法等價，組合所有偏差極限工況進行遍歷的結果與枚舉法等價，而取有限個偏差項進行組合遍歷，便于實現運算效率與交叉影響分析之間的均衡。

3 結束語

本文給出了全排列和組合的序數解析算法和單步遞推算法，序數解析算法得到的排列組合序列與序數嚴格對應，意義直觀便于使用，只是相比的計算量稍大；單步遞推算法的計算量較小，且從算術意義上，可理解為初始化得到量值最低的狀態(tài)，中止時得到量值最高的狀態(tài)，單步遞推時對序列當前項的左側項進位，通過顛倒順序使當前項到右端項的序列獲得量值最低的狀態(tài)，通過單步遞推得到的全排列和組合在量值上嚴格按升冪排列。

此外，對于選排列遍歷，可以通過組合遍歷中嵌套全排列遍歷來實現。通過序數解析算法和單步遞推算法，極大方便了與其他形式的遍歷方式任意組合，能夠應用到飛行器六自由度仿真試驗的偏差組合設計等各種離散問題的全局搜索中。