在数组m中找出他们的组合加起来为和为n的几组排列

在数组m中找出他们的组合加起来为和为n的几组排列

数组m:

值 n :

查看效果

/*
		调用说明:

		array: 数据源数组。必选。
		sum: 相加的和。必选。
		tolerance: 容差。如果不指定此参数,则相加的和必须等于sum参数,指定此参数可以使结果在容差范围内浮动。可选。
		targetCount: 操作数数量。如果不指定此参数,则结果包含所有可能的情况,指定此参数可以筛选出固定数量的数相加,假如指定为3,那么结果只包含三个数相加的情况。可选。
		返回值:返回的是数组套数组结构,内层数组中的元素是操作数,外层数组中的元素是所有可能的结果。

		 */

//var arror = [ 540, 251.5, 212, 137 , 285, 288, 1110, 297, 234.5, 459, 301.5, 400, 115, 220, 142, 574, 85];
//getCombBySum(arror,1900)
//console.log(getCombBySum(arror,1900))
//document.write(getCombBySum(arror,1900))
function getCombBySum(array, sum, tolerance, targetCount) {
    document.getElementById("conss").innerHTML = "";
    var array = eval(array);
    var util = {
        /*
			get combination from array
			arr: target array
			num: combination item length
			return: one array that contain combination arrays
			*/
        getCombination: function(arr, num) {
            var r = []; (function f(t, a, n) {
                if (n == 0) {
                    return r.push(t);
                }
                for (var i = 0,
                l = a.length; i <= l - n; i++) {
                    f(t.concat(a[i]), a.slice(i + 1), n - 1);
                }
            })([], arr, num);
            return r;
        },
        //take array index to a array
        getArrayIndex: function(array) {
            var i = 0,
            r = [];
            for (i = 0; i < array.length; i++) {
                r.push(i);
            }

            return r;
        }
    },
    logic = {
        //sort the array,then get what's we need
        init: function(array, sum) {
            //clone array
            var _array = array.concat(),
            r = [],
            i = 0;
            //sort by asc
            _array.sort(function(a, b) {
                return a - b;
            });
            //get all number when it's less than or equal sum
            for (i = 0; i < _array.length; i++) {
                if (_array[i] <= sum) {
                    r.push(_array[i]);
                } else {
                    break;
                }
            }

            return r;
        },
        //important function
        core: function(array, sum, arrayIndex, count, r) {
            var i = 0,
            k = 0,
            combArray = [],
            _sum = 0,
            _cca = [],
            _cache = [];

            if (count == _returnMark) {
                return;
            }
            //get current count combination
            combArray = util.getCombination(arrayIndex, count);
            for (i = 0; i < combArray.length; i++) {
                _cca = combArray[i];
                _sum = 0;
                _cache = [];
                //calculate the sum from combination
                for (k = 0; k < _cca.length; k++) {
                    _sum += array[_cca[k]];
                    _cache.push(array[_cca[k]]);
                }
                if (Math.abs(_sum - sum) <= _tolerance) {
                    r.push(_cache);
                    //console.log(r.length)
                    var html = document.getElementById("conss").innerHTML;
                    //再跟你想追加的代码加到一起插入div中
                    document.getElementById("conss").innerHTML = html + '第' + r.length + '组(共' + _cache.length + '个数):    ' + _cache + '<br /><br />';
                    //document.write("组:    " + _cache + "<br />")
                }
            }

            logic.core(array, sum, arrayIndex, count - 1, r);

        }

    },
    r = [],
    _array = [],
    _targetCount = 0,
    _tolerance = 0,
    _returnMark = 0;

    //check data
    _targetCount = targetCount || _targetCount;
    _tolerance = tolerance || _tolerance;

    _array = logic.init(array, sum);
    if (_targetCount) {
        _returnMark = _targetCount - 1;
    }

    logic.core(_array, sum, util.getArrayIndex(_array), (_targetCount || _array.length), r);

    return r;

}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注