[js] 对数组元素进行排列组合

[VaJoy]

/*
*返回arr的所有长度为size的子数组的组合
* 如arr = [1,2,3,4], size = 2
* return [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
*
* 再如arr = [1,2,3,4], size = 3
* return [[1,2,3], [1,2,4],[1,3,4] [2,3,4]];
*/

var a=[1,2,3,4];
function groupSplit(arr, size) {
  //TODO: 完成该函数
}
var ret = groupSplit(a, 2);
console.log(ret); // [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

[LeoHuiyi]

var a = [1, 2, 3, 4];

function groupSplit(arr, size) {
    var maxSize = arr.length, groupArr = [];

    if(size >= 1 && size <= maxSize){
        getArr(arr, 0, []);
    }

    function each(arr, index, fn){
        for (var i = index; i < maxSize; i++) {
            fn(arr[i], i, arr);
        }
    }

    function getArr(arr, _size, _arr, index){
        if(_size === size){
            return;
        }

        var len = _size + 1;

        each(arr, index || 0, function(val, i, arr){

            _arr.splice(_size, 1, val);

            if(_size === size - 1){
                groupArr.push(_arr.slice());
            }

            getArr(arr, len, _arr, i + 1);
        });
    }

    return groupArr;
}

var ret = groupSplit(a, 2);
console.log(ret); // [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

[erbing]

//夏神的代码
var a = [1,2,3,4,5];

function groupSplit(arr ,size) {
    var result = [];

    +function(arr ,size, comArr) {
        var templateArr = [];

        for(var i = 0; i < arr.length; i++) {
            templateArr = [];

            if(comArr instanceof Array) {

                if(comArr[comArr.length - 1] < a[i]) {
                    templateArr = comArr.concat(a[i]);
                    if(size === 1) {
                        result.push(templateArr);
                    } else {
                        arguments.callee( arr, size - 1, templateArr);
                    }
                }

            } else {

                templateArr.push(arr[i]);
                arguments.callee( arr, size - 1, templateArr);

            }
        } 

    }(arr,size);

    return result;
}
console.log(groupSplit(a,4));

[bluesrocker]

var arr = [10, 11, 12, 13, 14, 15, 16,17, 18];
groupSplit(arr, 4);
function groupSplit(arr, size) {
    if(!(typeof arr === 'object' && Object.prototype.toString.call(arr)==='[object Array]')){
        throw new TypeError('arguments[0] of function groupSplit is not a array');
    }
    if(!(typeof size === 'number')){
        throw new TypeError('arguments[1] of function groupSplit is not Number Type');
    }
    if(size < 1){
        throw new Error('arguments[1] of function groupSplit should be greater-than 0');
    }
    var leng = arr.length,
           bigArr = [],
           lay = new Array(size);
    size = Math.floor( Math.min(size, leng) );

    for(var i=0; i<size; i++){
        var smallResult = smallIndex(arr, size, i) ;
        bigArr.push(smallResult);
        lay[i]=0;
    }

    var loopNum=0;
    var group = [];
    (function loop(loopNum, lay){
        var current = loopNum;
        loopNum++;
        for(lay[current]=0; lay[current]<=leng-size; lay[current]++){
            if(loopNum===size){
                var small = [];
                small[0] = bigArr[0][lay[size-1]].value;
                for(var j=1; j<size; j++){
                    if(bigArr[j][lay[size-j-1]].index > bigArr[j-1][lay[size-j]].index){
                        small.push( bigArr[j][lay[size-j-1]].value );
                    }
                }
                if(small.length===size){
                    group.push(small);
                    //document.write(small[0]+'*'+small[1]+'*'+small[2]+'*'+small[3]+'<br/>');
                }
            }
            else if(loopNum < size){
                loop(loopNum, lay);
            }
        }
    }(loopNum, lay));
    return group;
}

function smallIndex(arr, size, start){
    var small = [],
           leng = arr.length;
    for(var i=start; i<=leng-size+start; i++){
        small.push({index:i, value:arr[i]});
    }
    return small;
}

[overkazaf]

var cache = {};
function groupSplit (arr, size) {
    if (Object.prototype.toString.call(arr) !== '[object Array]') throw new Error('Please pass a valid array as the first argument');
    if (arguments.length !== 2) throw new Error('Please check your arguments, which should be arr and size');
    if (isNaN(size)) throw new Error('The second parameter should be an interger');
    if (size < 0 || size > arr.length) throw new Error('Size parameter is illegal');

    var result = [], 
        tmp    = [],
        l      = arr.length,
        key    = arr.join('&') + '_' + size;

    if (key in cache) return cache[key];

    (function (arr, size, current){
        if (size == 0) {
            result.push(tmp.slice(0));
        } else {
            for (var j = current; j < l; j++) {
                tmp.push(arr[j]);
                arguments.callee.call(null, arr, size-1, j+1);
                tmp.pop();
            }
        }
    })(arr, size, 0);

    return (cache[key] = result);
};

[VaJoy]

function groupSplit (arr, size) {
  var r = []; //result

  function _(t, a, n) { //tempArr, arr, num
    if (n === 0) {
      r[r.length] = t;
      return;
    }
    for (var i = 0, l = a.length - n; i <= l; i++) {
      var b = t.slice();
      b.push(a[i]);
      _(b, a.slice(i + 1), n - 1);
    }
  }
  _([], arr, size);
  return r;
}

[xiaobei666]

/*
*返回多个数组的相互组合
* 如
* arr1= [1,2,3];
* arr2= [a,b,c];
* return [1,a], [1,b], [1,c], [2,a], [2,b], [2,c], [3,a], [3,b], [3,c]
*/

help

[yinyanli]

@VaJoy 觉得你的实现方法很棒，但是在for循环那里，b=t.slice()，不是很懂，slice()方法不带参数的话不是可以直接去掉吗，但是我去掉之后，又出现了错误，求讲解

[VaJoy]

@yinyanli .slice()常规用于数组拷贝，避免影响原数组

[yinyanli]

原来是这样，这种方式拷贝真是机智，超级感谢

[Pines-Cheng]

/**
 * 排列组合
 * @param  {[type]} arr         [数组]
 * @param  {[type]} selectNum   [剩余的选择的个数]
 * @param  {[type]} selectedArr [已选择的元素组成的数组]
 * @return {[type]}             [description]
 */
function getArrange(arr, selectNum, selectedArr) {
    if (selectNum === 1) {
        for (var i = 0; i < arr.length; i++) {
            var newSelectedArr = selectedArr.slice();
            newSelectedArr.push(arr[i]);
            console.log(newSelectedArr);
        }
    } else {
        selectNum -= 1; //剩余选择的减一
        for (var i = 0; i < arr.length; i++) {
            var newSelectedArr = selectedArr.slice();
            var newArr = arr.slice();
            newSelectedArr.push(arr[i]);
            newArr.splice(i, 1); //删除push进去的那一个
            getArrange(newArr, selectNum, newSelectedArr);
        }
    }
}

牛刀小试。

[bilibiliou]

关于 @VaJoy 的方法是这样的

以 [1,2,3,4] 为例子， size = 3

                                       [1,2,3,4] size=3                                                                                                 
                 [1][2,3,4] size=2                                 [2][3,4] size=2                                                                       
          [1,2][3,4] size=1                  [1,3][4] size=1            [2,3][4] size=1                                                                     
[1,2,3][4] size=0    [1,2,4][] size=0            [1,3,4][] size=0                 [2,3,4] size=0                                                                 

最后输出 [1,2,3] [1,2,4] [1,3,4] [2,3,4]

每一层都是一次递归， 不断的从右边的数组中拿数字到左边的数组，每次递归size--，当size为0的时候就取左边拿好的数组，为了避免重复，每次取数组的时候都会从左边数组之后开始取。

[allen391]

你这个只适用于size小于等于数组长度的情况下，如果要的size大于arr的长度就不行了。 @VaJoy

[uinz]

排列组合 既然有 排列 那么 [1, 2] 和 [2, 1] 应该都满足答案

所以 题目是不是应该改为 组合 去掉 排列 ?

---

我的答案

function groupSplit(arr: number[], size: number) {
    if (size > arr.length) {
        throw Error(`"size" should less then ${arr.length}`)
    }
    const result: number[][] = [];

    (function loop(unselectedList: number[], selectedList: number[] = []) {
        unselectedList.forEach((selected, i) => {
            const newSelectedList = [...selectedList, selected];
            const newUnselectedList = unselectedList.filter((_, j) => j > i);

            if (newSelectedList.length === size) {
                result.push(newSelectedList);
                return;
            }
            loop(newUnselectedList, newSelectedList);
        });
    })(arr);

    return result
}

console.log(
    groupSplit([1, 2, 3, 4, 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 ] ]

[AnnVoV]

function groupSplit(arr, size) {
    let result = [];

    function createTree(rootArr, remainArr, size) {
        if (remainArr.length <= 0 || size === 0) {
            result.push(rootArr);
            return;
        }
        for(let i=0; i<= remainArr.length-size; i++) {
            const root = remainArr[i];
            const other = remainArr.slice(i + 1);
            createTree(rootArr.concat(root), other, size - 1);
        }
    }

    createTree([], arr, size);
    return result;
}

console.log(groupSplit([1, 2, 3, 4, 5], 3));

[averyby]

function getGroup(arr, order) {
    if (order === 1) return arr;

    let result = [], length = arr.length;

    for (let i = 0; i < length; i++) {
        const p = arr[i];
        const remaining = arr.slice(i + 1);

        if (remaining.length < order - 1) break;

        result = [
            ...result,
            ...getGroup(remaining, order - 1).map(e => [p].concat(e))
        ];
    }

    return result;
}

console.log(getGroup([1, 2, 3, 4], 2));
console.log('\n');
console.log(getGroup([1, 2, 3, 4, 5], 3));

[zhangenming]

function groupSplit(arr, size, index = 0, results = [], ...tmp) {
  for (let i = index; i < arr.length; i++) {
    groupSplit(arr, size- 1, i + 1, results, ...tmp, arr[i])
  }
  return size ? results : results.push(tmp)
}
console.log(groupSplit([1,2,3,4],2))