mongona

mongona
-- --
正在获取天气

python自带的排列组合函数

python自带的排列组合函数

需求: 在你的面前有一个n阶的台阶,你一步只能上1级或者2级,请计算出你可以采用多少种不同的方法爬完这个楼梯?输入一个正整数表示这个台阶的级数,输出一个正整数表示有多少种方法爬完这个楼梯。

 

分析:提炼出题干的意思:用1和2产生不同组合,使得他们的和等于台阶的级数,输出有多少种组合方式。

 

解决: 主要的问题就是如何利用1和2产生不同的组合,查阅了python关于排列组合相关的资料

  最后发现了一个强大的python库 itertools

In [2]: import itertools

In [3]: for i in itertools.product([1,2],repeat= 1):
   ...:     print(i)
   ...:     
   ...: 
(1,)
(2,)

In [4]: for i in itertools.product([1,2],repeat= 2):
   ...:     print(i)
   ...:     
   ...: 
(1, 1)
(1, 2)
(2, 1)
(2, 2)

In [5]: for i in itertools.product([1,2],repeat= 3):
    ...:     print(i)
    ...:     
    ...: 
(1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 2, 2)
(2, 1, 1)
(2, 1, 2)
(2, 2, 1)
(2, 2, 2)

itertools.permutations(sequence,n)  #  从sequence中拿出n个数做排列, 不放回的拿出, n 只能小于等于sequence的长度 否则没有输出。

demo:

In [6]: for i in itertools.permutations([1,2], 1):
   ...:     print(i)
   ...:     
   ...: 
(1,)
(2,)

In [7]: for i in itertools.permutations([1,2], 2):
   ...:     print(i)
   ...:     
   ...: 
(1, 2)
(2, 1)

In [8]: for i in itertools.permutations([1,2],3):
   ...:     print(i)
   ...:     
   ...: 

In [9]:

 

itertools.combinations(sequence, n )   # 从sequence中选n个数做组合,相当于不放回, 当n 大于sequence的长度自然没有数据。

demo:

In [10]: for i in itertools.combinations([1,2],1):
    ...:     print(i)
    ...:     
    ...: 
(1,)
(2,)

In [11]: for i in itertools.combinations([1,2],2):
    ...:     print(i)
    ...:     
    ...: 
(1, 2)

In [12]: for i in itertools.combinations([1,2],3):
    ...:     print(i)
    ...:     
    ...: 

In [13]:

 

itertools.combinations_with_replacement(sequence, n )  # 从sequence中选n个数做组合,允许元素重复, repeat与sequence的长度无关。 

demo:

In [14]: for i in itertools.combinations_with_replacement([1,2],1):
    ...:     print(i)
    ...:     
    ...: 
(1,)
(2,)

In [15]: for i in itertools.combinations_with_replacement([1,2],2):
    ...:     print(i)
    ...:     
    ...: 
(1, 1)
(1, 2)
(2, 2)

In [16]: for i in itertools.combinations_with_replacement([1,2],3):
    ...:     print(i)
    ...:     
    ...: 
(1, 1, 1)
(1, 1, 2)
(1, 2, 2)
(2, 2, 2)

In [17]: for i in itertools.combinations_with_replacement([1,2],4):
    ...:     print(i)
    ...:     
    ...: 
(1, 1, 1, 1)
(1, 1, 1, 2)
(1, 1, 2, 2)
(1, 2, 2, 2)
(2, 2, 2, 2)

 

回到咱们的问题, 在这几个函数中,选择一个,很明显 itertools.product(sequence,repeat)  符合我们的要求:

 

code:

import itertools
n = int(input("输入台阶数:"))
l = [1,2] # 或者"12",序列即可
m = 0  # 组合数
for i in range(1,n+1):
    for j in itertools.product(l,repeat = i):
        asum = 0
        for k in j:
            asum += k # 累加步数 
        if asum == n: # 判断条件 步数等于台阶数
             m += 1  # 组合数加1
print("总的组合数:{}".format(m))

bash:

kali@Deepin:~$ python3 demo.py 
输入台阶数:1
总的组合数:1
kali@Deepin:~$ python3 demo.py 
输入台阶数:2
总的组合数:2
kali@Deepin:~$ python3 demo.py 
输入台阶数:3
总的组合数:3
kali@Deepin:~$ python3 demo.py 
输入台阶数:4
总的组合数:5
kali@Deepin:~$ python3 demo.py 
输入台阶数:5
总的组合数:8
kali@Deepin:~$ python3 demo.py 
输入台阶数:6
总的组合数:13
kali@Deepin:~$ python3 demo.py 
输入台阶数:7
总的组合数:21
kali@Deepin:~$

 

这个需求的新解法: 利用斐波那契数列的变种也能操作,比使用内置库好像要快点!  不是快点 是快很多!

class Solution:
    def Fibonacci(self, n):
        tempArray = [0, 1]
        if n >= 2:
            for i in range(2, n+1):
                tempArray[i%2] = tempArray[0] + tempArray[1]
        return tempArray[n%2]
    # 青蛙跳台阶, 每次可以跳1级或2级
    def jumpFloor(self, number):
        # write code here
        tempArray = [1, 2]
        if number >= 3:
            for i in range(3, number + 1):
                tempArray[(i + 1) % 2] = tempArray[0] + tempArray[1]
        return tempArray[(number + 1) % 2]

    def jumpFloorII(self, number):
        ans = 1
        if number >= 2:
            for i in range(number-1):
                ans = ans * 2
        return ans

 

递归新解法:

def jump(n):
    if n == 1 or n == 2:
        return n
    return jump(n - 1) + jump(n -2)

 

写在最后:童鞋我知道你是从博客园跳过来的,如果这篇文章对你有帮助,请留个言 点个赞谢谢!  如果有工作机会推荐就更感谢了 :)  

我的简历:http://resume.mongona.com/  坐标北京

 

 

2
0
富强,民主,文明,和谐,自由,平等,公正,法治,爱国,敬业,诚信,友善。
打赏二维码