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/ 坐标北京
