排列组合-组合-一一网

给出数据集合，从集合中选出 n 个元素，问可能出现的元素组合情况？

组合特点：内部元素是无序的，即[1,2,3] 和[3,2,1]是同一种组合情况

常用的求组合的方法有：递归法、转换法

递归法

存在 n 元素（无所谓重复与否），每次取出 m 个，问有多少种取法？

举个例子来说，存在[1,2,3,4,5]五个小球，每次可以取出 3 个球来放入 A 中，存在多少种取法？

可以按照如下步骤来取放

第一步：可以将 1 放入 A 中，那么还剩下 2、3、4、5
- 第二步：可以将 2 放入 A 中，那么还剩下 3、4、5
  - 第三步：将 3 放入 A 中，此时完成一次组合
  - 第三步：将 4 放入 A 中，此时完成一次组合
  - 第三步：将 5 放入 A 中，此时完成一次组合
- 第二步：可以将 3 放入 A 中，那么还剩下 4、5
  - 第三步：将 4 放入 A 中，此时完成一次组合
  - 第三步：将 5 放入 A 中，此时完成一次组合
- 第二步：可以将 4 放入 A 中，那么还剩下 5
  - 第三步：将 5 放入 A 中，此时完成一次组合
第一步：可以将 2 放入 A 中，那么还剩下 3、4、5
- 第二步：可以将 3 放入 A 中，那么还剩下 4、5
  - 第三步：可以将 4 放入 A 中，此时完成一次组合
  - 第三步：可以将 5 放入 A 中，此时完成一次组合
…

根据上述继续分析，A 是一个容器，我们每次可以从剩余的一堆小球中，取出一个来放入 A 容器中，例如：

可以将 1、2、3、4、5 中 1 号取出放入 A 容器，此时小球剩余为 2、3、4、5 且容器 A 未满；
可以从剩余小球中，取出 2 号放入容器，此处小球剩余为 3、4、5 且容器未满；
最后我们从剩余小球中取出 3 号放入容器，此时小球剩余 4、5 且容器满了，即满足一次组合

由上面分析可以得出如下思路：

对于一堆小球，每个小球都有可能被取出，那么可以 循环剩余的小球，让小球都有可能放入容器中
由于组合是无序的，那么先后放入小球不影响结果，例如先放入 1，再放入 2 和先放入 2 再放入 1 是一致，为了不产生重复计算，放小球时，不交换小球位置，从前往后依次放置
当把容器占满后，则完成一次组合

根据思路编码

function fullCombination(nums: number[], pick: number): number[][] {
  const ans: number[][] = []; // 结果
  recursion([], 0);
  return ans;

  function recursion(container: number[], startInd: number): void {
    // container 表示当前容器所包含的元素，当容器填满时，即完成一次组合
    if (container.length === pick) {
      ans.push(container);
      return;
    }

    // 已不可能达到pick的个数了，直接放弃
    if(startInd + pick > nums.length)return;

    for (let i = startInd; i < nums.length; i++) {
      const c = container.slice();
      c.push(nums[ i ]);
      recursion(c, i + 1);
    }
  }
}
复制代码

转换法

继续举上面的例子，将[1,2,3,4,5]放入容器内，我们使用 0,1 来来描述某个小球是否被选中，0 表示未选中，1 表示选中。例如五个元素全都不选中和全部选中为 [0,0,0,0,0]、[1,1,1,1,1]，如果只选中三个元素的话，选中最右边的三个为[0,0,1,1,1]，最左边的三个元素选中为[1,1,1,0,0]，那么所有的组合可以描述为从 [1,1,1,0,0] ==> [0,0,1,1,1] 的转换过程

转换方法

假设起始位置是 [1,1,1,0,0]，那么下一次选择应该是 [1,1,0,1,0]，继续下次选择应该是 [1,1,0,0,1] … 直到[0,0,1,1,1]

根据上述找规律：

从数组尾部(index=nums.length-1)向头部(index=0)寻找第一个 1,0,记录此时 10 的索引为 [i,j]；例如 [1,0,0,1,1] 第一个 1,0 索引表示为[0,1]
反转 1,0，即交换 i,j 两个位置的数；交换完后为 [0,1,0,1,1]
对于 j< index <= nums.length-1 的 1，全部移动到数组 j 的右侧，0 移动到最左侧；此时 j 为 1，在 1< index <=4 时，即在 index>j 的情况下，存在两个 1，则将这两个 1 移动到 j 的右侧 [0,1,1,1,0]
直到无法寻找到 1,0 为止

// 移动一步
function stepNext(picks: number[]): boolean {
  const first10Index = findFirst10(picks); // 步骤1 寻找从左至右的第一个1,0

  if (first10Index === -1) return false; // 步骤4 如果无法寻找到，则组合枚举结束

  swap(picks, first10Index, first10Index - 1); // 步骤2 交换i,j
  moveToLeft(picks, first10Index + 1, picks.length - 1); // 步骤3 移动1
  return true;
}

function findFirst10(nums: number[]): number {
  let prev = nums[ nums.length - 1 ];
  let first10Index = nums.length - 1;

  for (let i = nums.length - 2; i >= 0; i--) {
    if (prev === 0 && nums[ i ] === 1) break;
    first10Index = i;
    prev = nums[ i ];
  }
  return first10Index === 0 ? -1 : first10Index;
}

function moveToLeft(nums: number[], left: number, right: number) {
  let i = left, j = left;
  while (j <= right) {
    if (nums[ j ] === 1) {
      swap(nums, i, j);
      i++;
    }
    j++;
  }
}

function swap(nums: number[], i: number, j: number): void {
  const k = nums[ i ];
  nums[ i ] = nums[ j ];
  nums[ j ] = k;
}
复制代码

索引转换

上述只是描述了数对应的下标的组合，例如 [1,1,1,0,0]，它是无法表示最后的数值的，需要将索引转换为数值

function transform(originNums: number[], picks: number[]): number[] {
  const v = [];
  for (let i = 0; i < picks.length; i++) {
    if (picks[ i ] === 1) {
      v.push(originNums[ i ]);
    }
  }
  return v;
}
复制代码

具体实现

function fullCombination(nums: number[], pick: number): number[][] {
  const ans: number[][] = [];

  const start = new Array(nums.length).fill(0);
  for (let i = 0; i < pick; i++){
    start[ i ] = 1;
  }

  do {
    ans.push(transform(nums, start));
  } while (stepNext(start))

  return ans;
}
复制代码