您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 全排列算法實戰：含重複元素、位置限制與相鄰約束條件

編輯：Java 相關知識

給定數字 `1,2,2,3,4,5` (含重複 2)，求所有不重複排列，約束：`4` 不能在第 3 位，`3` 與 `5` 不相鄰。本文提供遞迴回溯完整實現與剪枝優化。

問題數學建模

多重集排列：6 個位置，元素 `2` 出現 2 次，總排列數 = 6! / 2! = 360
約束 1：位置限制 — `indexOf('4') != 2` (0-based 索引)
約束 2：相鄰禁忌 — 不包含子串 `35` 或 `53`

遞迴回溯核心邏輯

public class PermutationSolver {
  private static final List RESULTS = new ArrayList<>();
  private static final String SOURCE = "122345";
  
  public static void main(String[] args) {
    permute("", SOURCE);
    System.out.println("總數: " + RESULTS.size());
    RESULTS.forEach(System.out::println);
  }
  
  static void permute(String prefix, String remaining) {
    if (prefix.length() == SOURCE.length()) {
      RESULTS.add(prefix);
      return;
    }
    
    // 去重：同層級相同字符只用第一次
    Set used = new HashSet<>();
    for (int i = 0; i < remaining.length(); i++) {
      char c = remaining.charAt(i);
      if (used.contains(c)) continue;
      used.add(c);
      
      String nextPrefix = prefix + c;
      // 剪枝：提前檢查約束
      if (violatesConstraints(nextPrefix)) continue;
      
      String nextRemaining = remaining.substring(0, i) + remaining.substring(i + 1);
      permute(nextPrefix, nextRemaining);
    }
  }
  
  static boolean violatesConstraints(String partial) {
    // 4 不能在第三位 (索引 2)
    if (partial.length() >= 3 && partial.charAt(2) == '4') return true;
    // 3 和 5 相鄰
    if (partial.contains("35") || partial.contains("53")) return true;
    return false;
  }
}

關鍵技術點解析

技術	作用	代碼體現
遞迴回溯	系統探索所有排列組合	`permute(prefix, remaining)`
同層去重	避免重複元素產生重複排列	`Set used` 記錄本層已用字符
提前剪枝	部分排列違反約束即停止遞迴	`violatesConstraints(partial)`
字符串操作	構建剩餘字符池	`substring` 拼接

原始代碼改進對比

原始寫法	改進版	優勢
`getRest()` 遍歷替換	`substring` 直接構建	O(n) → O(1) 字符串操作，無 `replaceFirst` 陷阱
完整生成後過濾	遞迴中剪枝	大幅減少遞迴節點，效能指數級提升
靜態 List 儲存	流式處理/回調	記憶體友好，支援百萬級結果
硬編碼約束	獨立驗證方法	易擴展、易測試、符合單一職責