輸出陣列元素所有不重複組合 print all unique combination of an array

1月 04, 2011 程式寫作 , JavaScript , Programming/JavaScript 5 Comments Edit Copy Download

程式問題說明

請建立一個函式(function)，輸入一任意長度的陣列，並輸出該陣列所有元素不重複的排列組合的陣列。

舉例1：

• 輸入：["A", "B", "C"]
• 輸出：[["A"], ["B"], ["C"], ["A", "B"], ["A", "C"], ["B", "C"], ["A", "B", "C"]]

舉例2：

• 輸入：["A", "B", "C", "D"]
• 輸出：[["A"],["B"],["C"],["D"],["A","B"],["A","C"],["A","D"],["B","C"],["B","D"],["C","D"],["A","B","C"],["A","B","D"],["A","C","D"],["B","C","D"],["A","B","C","D"]]

答案實作

答案程式碼

注意，有兩隻函式喔。

function unique_combination_of_array(_array) {
    var _combination = [];
    
    var _length = _array.length;
    
    
    for (var _l = 1; _l < _length; _l++)
    {
        _combination = parse_combination(_array, _combination, _l);
    }
    _combination.push(_array);
    
    return _combination;
}

    
function parse_combination(_array, _output, _length, _length_pos, _length_ang)
{
    if (_length_pos == null)
        _length_pos = 1;
    if (_length_ang == null)
        _length_ang = [];
    
    //初始化的部份
    if (_length_ang.length < _length_pos)
    {
        if (_length_pos == 1)
        {
            _length_ang.push(1);
        }
        else
        {
            var _prev_index = _length_ang[(_length_ang.length-1)];
            _length_ang.push(_prev_index+1);
        }
    }
    
    var _index = 0;
    if (_length_pos > 1)
    {
        var _prev_index = _length_ang[(_length_pos-2)];
        _index = _prev_index+1;
    }
    
    if (_length_ang.length < _length_pos)
    {
        _length_ang.push(_index);
    }
    
    for (var _i = _index; _i < _array.length - (_length - _length_pos); _i++)
    {
        if (_length_ang.length > _length_pos)
        {
            //避免受到傳址影響，必須重整
            var _temp = [];
            for (var _p = 0; _p < _length_pos; _p++)
                _temp.push(_length_ang[_p]);
            _length_ang = _temp;
        }
        
        _length_ang[(_length_pos-1)] = _i;
        
        //如果抵達這個長度的話
        if (_length_ang.length == _length)
        {
            //輸出
            var _output_ang = [];
            for (var _a in _length_ang)
            {
                _index = _length_ang[_a];
                var _code = _array[_index];
                _output_ang.push(_code);
            }
            _output.push(_output_ang);
        }
        else    //如果尚未抵達這個長度
        {
            _output = parse_combination(_array, _output, _length, (_length_pos+1), _length_ang);
        }
    }
    
    return _output;
}

結語

陣列元素輸出不重複組合是很基本、很常用，但是卻是一個不容易馬上就寫得出來的程式。這種問題感覺就很像程式設計考試會出的題目，而實際上也的確蠻多情況需要使用。如果陣列的長度是固定的，這樣輸入或輸出參數寫起來容易，但是加入「任意長度」的前提，就需要動動腦筋才寫得出來。基本上「任意長度」的程式都需要用到「遞迴」技巧，構築程式的時候很容易就會腦筋打結呢。

因為覺得這隻程式在很多地方都會用到，所以寫篇blog記錄一下，或許會幫助到研究程式的同伴也說不定。我這隻是以JavaScript來實作，其中還有考慮到JavaScript天生受到的傳址限制。除了這個特殊的限制之外，要替換到其他程式語言應該不會有什麼困難吧。