ActionScript 實作組合窮舉演算法

演算法原理

從 N 個元素中取出 C 個元素的所有組合 (Combination)。採用 **迭代法** 配合 **回溯索引**，避免遞迴呼叫開銷。核心邏輯如圖示：

完整 ActionScript 3 實作

private function compoud(N:uint, C:uint):void {
    var pickIndex:int = 0;
    var arr:Array = new Array();      // 目前組合
    var src:Array = new Array();      // 來源元素 1..N
    for (var i:int = 0; i < N; i++) src.push(i + 1);

    while (true) {
        if (pickIndex < N) {
            arr.push(src[pickIndex++]); // 取入下一個元素

            if (arr.length == C) {      // 組合湊齊
                var tmp:String = "";
                for (i = 0; i < C; i++) tmp += arr[i] + " ";
                trace(tmp);             // 輸出一組結果

                if (pickIndex == N) {   // 已到來源尾端，需回溯
                    var backto:int = -1;
                    for (i = C - 1; i > 0; i--) {
                        if (arr[i] - arr[i - 1] > 1) { // 找可遞增的位置
                            backto = i - 1;
                            break;
                        }
                    }
                    if (backto == -1) break; // 全部組合產生完畢
                    pickIndex = arr[backto]; // 回溯點
                    for (i = 0; i < C - backto; i++) arr.pop(); // 移除尾部
                }
            }
        } else {
            // pickIndex 超界，回溯
            arr.pop();
            if (arr.length == 0) break;
            // 找新的回溯點 (同邏輯)
            var backto:int = -1;
            for (i = arr.length - 1; i > 0; i--) {
                if (arr[i] - arr[i - 1] > 1) { backto = i - 1; break; }
            }
            if (backto == -1) break;
            pickIndex = arr[backto];
            for (i = 0; i < arr.length - backto; i++) arr.pop();
        }
    }
}

執行範例

compoud(5, 3);

輸出：

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

複雜度分析

• 時間複雜度：O(C(N, C) * C) — 每個組合輸出需 O(C) 建立字串。
• 空間複雜度：O(N + C) — 儲存來源陣列與目前組合。
• 非遞迴，無堆疊溢位風險，適合較大 N 值。

移植提示

邏輯純粹使用陣列與索引運算，極易移植至 C/C++、Java、C#、Python 等語言。只需替換 Array、push/pop、trace 對應語法。