[發明專利]有約束條件排列組合編碼生成算法及MATLAB實現方法

在審

• 申請號: 201710915691.1
• 申請日: 2017-09-30
• 公開（公告）號: CN107526903A
• 公開（公告）日: 2017-12-29
• 發明（設計）人: 杜瑞卿;杜彥輝;顧妍;張征田;張新剛
• 申請（專利權）人: 南陽師范學院
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京中恒高博知識產權代理有限公司11249
• 代理人: 劉洪京

技術領域

本發明屬于運籌、規劃、信息、計算機等領域的編碼生成算法技術領域，特別涉及有約束條件排列組合編碼生成算法及MATLAB實現方法。

背景技術

關于1，2，…，n的全排列及組合生成，目前已有數十種不同的求解算法。典型的排序算法有直接選擇排序、冒泡排序、插入排序、歸并排序、快速排序等；而全排列生成算法典型的如字典序法、進位法、換位法、鄰位對換法等,其中一些是比較難理解的遞歸型算法。但實際應用中不完全是不同元素的全排列或組合，有時是有特殊要求的排列，諸如課程安排算法的求解，體育賽事的安排，車輛調度，整數線性規劃求解，信息編碼、某種算法或程序中的要求等。關于有約束條件要求的排列組合，有部分文獻資料，但存在不足：1、算法思想不夠簡捷，比較復雜。2、算法描述不夠描述精煉，不易讓讀者掌握領會。3、在程序實現上，不夠具體，缺少明確性。4、約束條件簡單，位數少，不具有普遍性。

發明內容

本發明目的是提供一種有約束條件排列組合編碼生成的算法；基于算法的程序實現；以實例演示便于掌握該算法及程序；為信息編碼、運籌、規劃求解等科研、生產實際提供有效服務。

本發明是采用以下技術方案實現的：

一種有約束條件排列組合編碼生成算法，包括有約束條件的排列生成方法和有約束條件的組合生成方法，

有約束條件的排列生成方法:

設排列a₁a₂…a_m，滿足：0≤a_i≤N_i，a₁+a₂+…+a_m＝n，求所有a₁a₂…a_m的生成；

從滿足約束條件的最小全排列開始，按依次增大的方法生成下一個全排列：

(1)從排列a₁a₂…a_n最右邊開始向左邊查找：a_t＜N_t，t＝max{i︱a_i＜N_i，i≠m}，a₁a₂…a_t-1保持不變，a_t+1→a_t；

(2)計算：

(3)重新生成第t+1位到m位：

M_jφN_j時，令a′_j＝N_j，M_j-1＝M_j-N_j；M_j≤N_j時，令a′_j＝M_j，a′_j-1＝a′_j-2＝Λ＝a′_t+1＝0；

(4)形成新的排列：a₁a₂Λa_t-1(a_t+1)a′_t+1Λa′_j-1a′_jΛa′_m；

(5)重復(1)-(3)，可生成全部排列，結束生成。

優選地，有約束條件的組合生成方法：

設求a_i≠a_j，i≠j，a₁+a₂+Λ+a_m＝n，由a₁，a₂，…，a_m組成的所有組合。

從滿足約束條件的最小升序組合開始，按依次增大的方法生成下一個升序組合：

(1)從升序組合a₁a₂…a_m的最右邊開始尋找a_k，t＝max{j|a_j-1φa_j-1}，

k＝max{r|t-rφ1Ιa_r+1-a_r＝2}(1)式或者k＝max{r|a_r+1-a_r≥3}(2)式；