温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Python组合怎么使用

发布时间:2021-11-26 09:25:25 来源:亿速云 阅读:161 作者:iii 栏目:大数据

这篇文章主要介绍“Python组合怎么使用”,在日常操作中,相信很多人在Python组合怎么使用问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Python组合怎么使用”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

题目


给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解题思路


思路:组合数

先审题,题目要求给定 n,返回 1...n 中所有可能的 k 个数组合。我们可以发现,这其实就是高中数学概念上的组合数问题。

组合的定义: 从 n 个不同元素中,任取 m($m \leq n$)个不同元素组成一组,称为组合。

组合数的定义: 从 n 个不同元素中,任取 m($m \leq n$)个不同元素的所有组合的个数,叫做组合数,记为 $C_{n}^{m}$。

组合数有这样一个性质:

$$C_{n+1}^{m} = C_{n}^{m} + C_{n}^{m-1}$$

这里我们令 n' = n+1,那么上面的式子则会变成:

$$C_{n'}^{m} = C_{n'-1}^{m} + C_{n'-1}^{m-1}$$

其实也就等同于:

$$C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$$

这里我们可以这样去理解上面的式子。假设现在从 n 个元素选 m 个元素,也就是 $C_{n}^{m}$。这里,我们先选择一个需要特殊考虑的元素,那么就会有以下两种情况:

  • 当选取的元素中不含这个特殊元素,那么就需要在剩余的 n-1 个元素中选出 m 个元素,也就是 $C_{n-1}^{m}$;

  • 当选取的元素中含有这个特殊元素,那么就需要从剩余的 n-1 个元素中选出 m-1 个元素,也就是 $C_{n-1}^{m-1}$ 。

最终,将两种情况结合起来,从 n 个元素选 m 个元素的情况。

那么就按照这个思路,进行实现,这里每次选取特殊元素为可选元素集合中最小的元素。

具体代码实现如下(递归方法)。

from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        tmp = []

        def helper(special, n, k):
            # k 个元素选择完成,添加到返回列表中
            if k == 0:
	            # 这里注意添加的是副本
	            # 具体原因,建议自行调试查看
                ans.append(tmp[::])
                return
            # 表示剩余元素不够选择 k 个元素,直接返回
            if k > n:
                return

            tmp.append(special)
            helper(special+1, n-1, k-1)
            tmp.pop()
            helper(special+1, n-1, k)

        helper(1, n, k)

        return ans

# n = 4
# k = 2
# solution = Solution()
# ans = solution.combine(n, k)
# print(ans)

到此,关于“Python组合怎么使用”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI