算法练习06 从数组中取出n个元素的所有组合

发表于 2019-03-18 分类于算法阅读次数：

用递归实现从数组中取出n个元素的所有组合。

题目

给定一个数组arr，从中选出n个元素，要求给出所有组合的情况（结果在一个数组中）

例子：

const arr = ['1', '2', '3'];
const n = 2;

const result = getCombine(arr, b);
console.log(result);
// ['12', '13', '23' ]

分析

实际上就是一个求排列组合的问题。对上面的例子进行分析

（1）首先arr是['1', '2', '3'],n是2，先取出数组中第一项1，然后需要从剩下的两个元素中取一个

（2）此时可以将arr看做[ '2', '3'],n是1，在从中任取一项就行了

（3）此时结果为['12', '13']

（4）返回第一步，取出数组中第一项1改为取第二项2，然后从剩下的元素中取

（5）重复进行上面的步骤

很明显，分析后发现这是一个递归的过程，不过要注意的是需要控制取出第一个元素的序列，防止12和21作为两种情况出现。控制方法有两种，或者传入一个start作为开始的索引值，或者用slice来剪切数组，将数组已经取过的元素剪切掉

代码

忽略了n大于数组长度的情况的处理。

/**
 * 从数组中取出n个元素的所有排列组合
 * @param arr       待处理数组
 * @param n         要取出的元素个数
 * @param result    返回的结果
 * @param current   当前已经取出的元素
 * @returns {Array} 返回数组，数组元素是各种排列组合的情况
 */
const getCombine = (arr, n, result = [], current = '') => {
  // 如果只要取出一个元素，那么只需要将数组元素与已取出的元素一一组合即可
  if (n === 1) {
    result.push(...arr.map(v => `${current}${v}`))
    ;
    return result;
  }
  // 对当前数组进行遍历，剩余元素个数i等于要取出的元素个数时停止遍历
  for (let i = 0; i < arr.length - n + 1; i++) {
    // 取出当前的元素与已取出的元素组合
    const temp = `${current}${arr[i]}`;
    // 递归调用，数组剪切（相当于开始的索引前进），取出的个数减一
    getCombine(arr.slice(i + 1), n - 1, result, temp);
  }
  return result;
};

参考

从数组中取出n个元素的所有组合（递归实现）@NULL