算法基础:排列、组合和子集

1,656 阅读4分钟

1. 排列、组合以及子集问题

1.1 什么是排列、组合和子集?

排列分为全排列和普通排列,全排列表示方法:A{^n_n},表示1到n的阶乘(\prod_{i=1}^ni),普通排列A{^m_n},表示(n-m+1)到n的阶乘。(这是数学里面的定义)

例如:A{^3_3}=3*2*1 = 6A{^4_2}=4*3=12

那全排列有什么应用呢?举个例子,数字排列问题:将1-9排在9个位置,有多少中排法?例如,123456789是一种,213456789也是一种,那么一共多多少种呢?第一个位置有9种情况,第二个位置有8种情况,...,第九个位置有1种情况,总的可能数就是987...*1=A{^9_9}.

组合和排列类似,但是组合不考虑顺序问题,也就是123和321其实是一种情况。例如:有四个数,要从中选两个数,有几种选法?数学解法是C{^4_2}=\frac{4*3}{2*1}=6

子集呢?一个n个元素的集合的子集个数是2^n个,子集可能是空集,一个元素的集合一直到n个元素的集合。例如集合{1,2},其子集可能是{\emptyset, {1}, {2}, {1,2}}

2 用深度优先算法解决排列、组合和子集问题

2.1 排列

2.1.1 问题描述

输入一系列数字,例如123,给出所有可能的排列结果,例如对于输入123,输出123、132、213、231、321、312.

2.1.2 算法思路

对于123而言,有三个位置,我们可以枚举每一个位置,在深度优先搜索中位置的个数就是深度。在每一个位置都枚举可能取的值,注意数字不能重。

上代码:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    var result = [];
    dfs(0,nums,[],result,[]);
    return result;
};

function dfs(depth,nums,temp,result,visited) {
    if(depth == nums.length) {
        result.push([].concat(temp));
        return;
    }
    for(var i = 0;i < nums.length;i++) {
        if(!visited[i]) {
            visited[i] = true;
            temp.push(nums[i]);
            dfs(depth+1,nums,temp,result,visited);
            temp.pop(); // 回溯思想,当前数字被处理了后,在其他情况中还可能需要被处理。
            visited[i] = false; // 同上
        }
    }
}

2.2 组合

2.2.1 问题描述

给定一个集合{1,2,3},选出其中的2个数组成新集合,不能重复。例如:输入{1,2,3},输出[[1,2],[1,3],[2,3]]

2.2.2 算法思路

我们还是应用深度优先搜索的思想,只不过示例中的深度是2。第一层我们可以取的值是,1|2|3,第一层取了的第二层就不能取了。而且为了避免重复,加入我们第一层取2,那么第二层就不能取1了,因为12,21是相同的。第二层只能从3开始取。

上代码:

var combination = function(nums,m) {
  var result = [];
  dfs(0,m,nums,[],result,0);
  return result;
}
// spos是下一次遍历数组时开始的位置,如果上一次我们遍历了1,那么下一次要从2开始,这样才能保证不重复
function dfs(depth,tdep,nums,temp,result,spos) {
  if(depth == tdep) {
      result.push([].concat(temp))
      return;
  }
  for(let i = spos;i < nums.length;i++) {
      temp.push(nums[i]);
      dfs(depth+1,tdep,nums,temp,result,i+1);
      temp.pop();
  }
}

2.3 子集

2.3.1 问题描述

给定一个集合,比如{1,2,3},求其所有子集。 例如:输入{1,2},{\emptyset, {1}, {2}, {1,2}}

2.3.2 算法思路

通过观察我们可以发现,一个集合的子集的元素个数是有规律的,子集中的元素有可能有0个(空集),1个,2个,...,n个。

然后我们就可以将问题缩小了,问题变成了从集合中选出1个(2、3、...n)元素组成新集合?我们发现这变成了一个组合问题了。

所以我们的算法分两步,第一步枚举子集元素的个数,假定当前为i,第二步,求出集合中取i个元素构成的子集,我们可以复用上面组合的代码。

上代码:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    var result = [];
    for(var i = 0;i <= nums.length;i++){
        dfs(0,i, nums,[],result,0);
    }
    return result;
};
// 下面时求集合中取tdep个元素的组合,直接复用了求组合的代码
function dfs(depth,tdep,nums,temp,result,spos) {
  if(depth == tdep) {
      result.push([].concat(temp))
      return;
  }
  for(let i = spos;i < nums.length;i++) {
      temp.push(nums[i]);
      dfs(depth+1,tdep,nums,temp,result,i+1);
      temp.pop();
  }
}

3 思考&总结

这里我们总结排列、组合和子集问题的解法。这是最基本的算法,许多问题可能是这几种思想的变体.

例如,leetcode组合求和问题:给定一个数字集合和一个目标数字,求出所有和是这个数字的数字集合: 输入[1,2,3],4 那么输出[[1,3],[2,2]],因为1+3=4,2+2=4,还要保证不重复。

这个问题可以利用我们前面总结的组合问题的思想,我们求[1,2,3]的组合(这里的组合与上面区别是选取元素个数是不确定的,而且元素可以重复,只要值没到4,就可以一直加)。如果组合集合数字和为4,那么输出这个集合,同时还可以采用回溯的思想优化,如果当前的和或者当前数字的值大于目标数字,那就没必要继续算了,直接回溯。

上面讨论了一种变体,还有很多这类问题的变体,理解了关键思想,就都不困难了。