排列組合查詢演算法實作：關鍵字全排列生成 SQL LIKE 條件

問題定義

需實作類似 Google 進階搜尋「包含所有關鍵字，順序不拘」的查詢。輸入關鍵字集合 {k1, k2, ..., kn}，產生 SQL：

SELECT ... FROM table
WHERE (col LIKE '%k1%k2%...%kn%')
   OR (col LIKE '%k1%kn%...%k2%')
   OR ... -- 所有 n! 種排列
ORDER BY ...;

核心子問題：給定字串陣列，輸出所有全排列組合字串（以 % 分隔）。

演算法選擇：字典序下一個排列

採用 Donald Knuth / Rosen 教科書經典演算法：

1. 從右向左找第一個 a[j] < a[j+1] 的索引 j
2. 從右向左找第一個 a[k] > a[j] 的索引 k
3. 交換 a[j] ↔ a[k]
4. 反轉 j+1 到末尾的子陣列
5. 重複直到無下一個排列

時間複雜度 O(n! * n)，空間 O(n)，適合 n ≤ 7 (5040 種) 場景。

Java 實作：PermutationGenerator

import java.math.BigInteger;
import java.util.*;

public class PermutationGenerator {
    private final int[] a;        // 當前排列索引
    private BigInteger numLeft;   // 剩餘排列數
    private final BigInteger total;

    public PermutationGenerator(int n) {
        if (n < 1) throw new IllegalArgumentException("Min 1");
        a = new int[n];
        total = factorial(n);
        reset();
    }

    public void reset() {
        for (int i = 0; i < a.length; i++) a[i] = i;
        numLeft = new BigInteger(total.toString());
    }

    public BigInteger getNumLeft() { return numLeft; }
    public BigInteger getTotal() { return total; }
    public boolean hasMore() { return numLeft.compareTo(BigInteger.ZERO) == 1; }

    private static BigInteger factorial(int n) {
        BigInteger f = BigInteger.ONE;
        for (int i = n; i > 1; i--) f = f.multiply(BigInteger.valueOf(i));
        return f;
    }

    /** 回傳下一個排列的索引陣列 */
    public int[] getNext() {
        if (numLeft.equals(total)) { numLeft = numLeft.subtract(BigInteger.ONE); return a; }
        int j = a.length - 2;
        while (j >= 0 && a[j] > a[j + 1]) j--;
        int k = a.length - 1;
        while (a[j] > a[k]) k--;
        swap(j, k);
        reverse(j + 1, a.length - 1);
        numLeft = numLeft.subtract(BigInteger.ONE);
        return a;
    }

    private void swap(int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
    private void reverse(int l, int r) { while (l < r) swap(l++, r--); }

    // 測試主程式
    public static void main(String[] args) {
        String[] kw = {"tom", "tina"};
        PermutationGenerator pg = new PermutationGenerator(kw.length);
        StringBuilder sql = new StringBuilder("SELECT * FROM student WHERE ");
        boolean first = true;
        while (pg.hasMore()) {
            int[] idx = pg.getNext();
            if (!first) sql.append(" OR ");
            first = false;
            sql.append("name LIKE '%");
            for (int i : idx) sql.append(kw[i]).append('%');
            sql.append("'");
        }
        sql.append(" ORDER BY age");
        System.out.println(sql);
    }
}

輸出範例

輸入 {"tom", "tina"}：

SELECT * FROM student WHERE name LIKE '%tom%tina%' OR name LIKE '%tina%tom%' ORDER BY age

效能與適用邊界

工程化改進方向

1. 全文檢索引擎：Lucene/Elasticsearch/OpenSearch 原生支援多關鍵字任意順序匹配，效能與擴展性遠優於 LIKE 全掃描。
2. 資料庫全文索引：MySQL FULLTEXT、PostgreSQL tsvector、SQL Server CONTAINS。
3. 關鍵字去重與停用詞過濾：減少排列基數。
4. 動態 SQL 建構：使用 StringBuilder、參數化查詢 (PreparedStatement) 避免注入。
5. 快取熱門查詢：Redis 快取組合條件或結果集。

結語

全排列生成 LIKE 條件是小規模關鍵字任意順序查詢的直觀實作，代碼簡潔、無外部依賴。但階乘增長極快，n > 6 即進入危險區。實際專案請評估資料量、查詢頻率與延遲要求，優先考慮全文搜尋引擎或資料庫內建全文索引，將演算法作為原型驗證或極小規模場景的備選方案。

1. 上一篇文章： 使用 Spring、JSF、EJB3 設計企業應用程式
2. 下一篇文章： 用 UML 描述 Java 類別

Java 相關知識

SSO 單點登錄解決方案：原理、架構與 Web 實戰完整指南

什麼是 SSO Single Sign On：多應用系統中，

Eclipse 實用技巧大全：插件安裝、MyEclipse 破解、自定義註釋、快捷鍵

本文匯總 Eclipse 日常開發中最高頻的實用技巧，涵蓋插

Eclipse RCP可視化編輯器選型指南：VE vs SWT-Designer深度評測

RCP開發中UI布局代碼繁瑣，可視化編輯器能大幅提效。本文實

J2ME 走向成熟：配置與 Profile 架構深度解析、CDC/CLDC 差異與舊規範現狀

前言 J2ME 於 1999 年隨 Java 2 平台推出，