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:~$

 

74
38
富强,民主,文明,和谐,自由,平等,公正,法治,爱国,敬业,诚信,友善。
打赏二维码
About
Sato
有一个人养了几条鱼死了,悲伤不已,他不想土葬,他说想给他火葬,把鱼灰撒回海洋让它回到母亲的怀抱……谁知道越烤越香,后来他就买了瓶啤酒…… 很多事情,走着走着就忘了初衷…… 几乎每个人都听过:“不忘初心,方得始终”,却少有人知道下一句:“初心易得,始终难守”。 人生是一场修行,很少有人能忠于自己内心的目标和生命的使命,因此善始者多,善终者少。
Category
Tags
Site statistics

本站现有文章17篇,共被浏览11165

本次响应耗时: 0.467s

当前来路IP: 35.173.48.224  美国

您是本站第: 65461 位访客!

本站已苟活: 

All hots
Article archiving