ActionScript 實作組合枚舉演算法（非遞迴）

演算法核心

從 N 個元素中取出 C 個的所有組合，採用迭代+回溯避免遞迴堆疊溢位，適合大規模枚舉。

完整代碼

private function compound(N:uint, C:uint):void {
    var pickIndex:int = 0;
    var arr:Array = [];
    var src:Array = [];

    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 {
                    arr.pop(); // 繼續嘗試下一個元素
                }
            }
        } else {
            break;
        }
    }
}

邏輯解析

1. 前進：pickIndex 向前掃描，將元素加入 arr
2. 輸出：arr.length == C 時輸出一組合
3. 回溯：掃描到尾或組合滿時，從右向左找第一個「間隙 > 1」的位置 backto
4. 跳躍：將 pickIndex 設為該位置值，彈出後續元素，繼續前進
5. 終止：找不到間隙（backto == -1）表示已枚舉完畢

複雜度

• 時間：O(C(n, k)) —— 必須產生所有組合
• 空間：O(k) —— 僅存儲當前組合
• 無遞迴，適合大 N、大 k 場景

作者：aerror