Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
VaJoy opened this issue Dec 16, 2015 · 16 comments
Open

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

VaJoy opened this issue Dec 16, 2015 · 16 comments

Comments

@VaJoy
Copy link
Member

VaJoy commented Dec 16, 2015

/*
*返回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]]
@VaJoy VaJoy changed the title [js] [js] 返回arr的所有长度为size的子数组的组合 Dec 16, 2015
@LeoHuiyi LeoHuiyi assigned coxo and LeoHuiyi and unassigned coxo and LeoHuiyi Dec 16, 2015
@LeoHuiyi
Copy link
Member

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
Copy link
Member

erbing commented Dec 17, 2015

//夏神的代码
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
Copy link

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
Copy link

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
Copy link
Member Author

VaJoy commented Dec 17, 2015

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;
}

@VaJoy VaJoy changed the title [js] 返回arr的所有长度为size的子数组的组合 [js] 对数组元素进行排列组合 Dec 17, 2015
@xiaobei666
Copy link

xiaobei666 commented Aug 19, 2016

/*
*返回多个数组的相互组合
* 如
* 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
Copy link

yinyanli commented Oct 2, 2016

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

@VaJoy
Copy link
Member Author

VaJoy commented Oct 8, 2016

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

@yinyanli
Copy link

yinyanli commented Oct 8, 2016

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

@Pines-Cheng
Copy link

Pines-Cheng commented Nov 19, 2016

/**
 * 排列组合
 * @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
Copy link

bilibiliou commented Sep 12, 2017

关于 @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
Copy link

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

@uinz
Copy link

uinz commented Jul 25, 2018

排列组合 既然有 排列 那么 [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
Copy link

AnnVoV commented Mar 11, 2019

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
Copy link

averyby commented Apr 29, 2019

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
Copy link

zhangenming commented Mar 19, 2021

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))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests