排列数和组合数_组合数转化为排列数 csdn-CSDN博客

本文链接：https://blog.csdn.net/algorithm6/article/details/146473029

排列问题：从n个不同的数字中取出m个数字，进行排序输出。

组合问题：在n个不同的数字中挑选m个数字，并将所有的组合方式输出。

先解决排列问题，假设需要排列[1,2,3,4]这四个数字。可以知道第一个数字有4个选择，第二个数字有3个选择，第三个数字有2个选择，第四个数字有1个选择。

permute(nums)方法的思路如下。

（1）选择第一个位置上的数字，称之为x。

（2）利用permute(nums)方法得到剩余数字的所有排列方式。

（3）把x放入这些数组的第一个位置。保存答案。

（4）回到第一步，改变x。

（5）尝试过所有x后输出答案。

permute(nums)方法的边界条件为，如果nums数组为空，那么将当前的排列方式加入结果集合并返回。

以[1,2,3,4]为例。

（1）初始时，只关心第一个位置的数，它一共有4个选择。遍历这四种选择，第一次选择1。

（2）知道从1开始的排列组合等于1+“[2,3,4]的排列组合”。这时再次调用permute(nums)方法，传入[2,3,4]就能得到“[2,3,4]的排列组合”。

（3）得到6个“[2,3,4]的排列组合”后，将1加入数组，放在第一个位置。

（4）回到第一步，把第一个位置上的数换成2。

代码：

# 排序nums并返回所有组合
def permute(nums, solution=[]):
    if not nums:   # 边界条件
        res.append(solution)
        return  # 返回
    for i in range(len(nums)):
        newSolution = solution + [nums[i]]  # 依次将nums里的数字放置排列组合的下一个位置上
        newList = nums[0:i] + nums[i + 1:]  # newList里是除了nums[i]以外的全部数字
        permute(newList, newSolution)  # 继续排列newList里的数字

输入：

[1,2,3,4]

输出：

[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]

然后解决组合问题，假设从[1,2,3,4,5]中选择3个数字。

步骤如下。

（1）选择第一个位置上的数字，称之为x。

（2）利用combination()方法得到剩余数字的组合。

（3）把x放入第二步得到的数组的第一个位置。保存答案。

（4）回到第一步，改变x。

（5）尝试完所有x后输出答案。

combination()方法与permute()方法不同的一点在于第二步“剩余数字”的定义。permute()方法中，“剩余数字”为除了x的所有数字。但是，在combination()方法中“剩余数字”为x之后的所有数字。比如，如果nums为[1,2,3,4]，当前数字为2，那么permute()方法的“剩余数字”为[1,3,4]，但combination()方法的“剩余数字”为[3,4]。

代码：

# 输出所有组合方式
def combination(nums, solution, n):
    if n == 0:  # 边界条件
        res.append(solution)
        return

    for i in range(len(nums)):
        newSolution = solution + [nums[i]]  # 依次将nums里的数字放入新组合newSolution
        newList = nums[i + 1:]  # 剩余数字
        combination(newList, newSolution, n - 1)  # 在剩余的数字选择n-1个数字

输入：

[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]

注意：

（1）combination()方法多了一个参数n，用来表示需要选择几个数字。每一次combination()方法调用自己的时候，n都减1。

（2）newList的定义不再是nums[0:i]+nums[i+1:]，而是nums[i+1:]。这是因为之前的数字都已经被用过了，而在组合问题中一个数字不能被二次利用。

最后再尝试一下，带重复数字的组合数：

# 组合数带重复
def combination_replace(nums, solution, n):
    if n == 0:  # 边界条件
        res.append(solution)
        return

    for i in range(len(nums)):
        newSolution = solution + [nums[i]]  # 依次将nums里的数字放入新组合newSolution
        newList = nums[:]  # newList里是全部数字
        combination_replace(newList, newSolution, n - 1)  # 在剩余的数字选择n-1个数字