T3：字母排列

将LANQIAO中的字母重新排列，可以得到不同的单词，如LANQIAO、AAILNOQ等，注意这7个字母都要被用上，单词不一定有具体的英文意义。请问，总共能排列多少个不同的单词。

  1. string='LANQIAO'
  2. from itertools import permutations
  3. # 使用集合去掉重复的排列
  4. ans=set()
  5. for item in permutations(string):
  6.     ans.add(item)
  8. print(len(ans)) # 2520

关于itertools.permutations：
permutations(p[,r])：返回 p 中任意取 r 个元素做排列的元组的迭代器全排列。

  1. import itertools
  2. nums = ['a','b','c']
  3. for num in itertools.permutations(nums):
  4.     print(num)
  6. ('a', 'b', 'c')
  7. ('a', 'c', 'b')
  8. ('b', 'a', 'c')
  9. ('b', 'c', 'a')
  10. ('c', 'a', 'b')
  11. ('c', 'b', 'a')

T4：括号序列

由1对括号，可以组成一种合法括号序列：()。
由2对括号，可以组成两种合法括号序列：()()、(())。
由4对括号组成的合法括号序列一共有多少种？

思路：
将括号的序列看成二叉树，定义序列(x, y)，只需满足：

  • y >= x
  • x, y >= 0 ```python def dfs(n, x, y, f): global count count += 1 if (x == 0) & (y == 0):
    1.   print(f)
    2.   return
    if (x < 0) | (y < 0):
    1.   return
    for i in range(x, -1, -1):
    1.   for j in range(y, -1, -1):
    2.       if i > j:
    3.           return
    4.       if i > 0:
    5.           f[2*n-i-j+1] = (i-1, j)
    6.           # print(i-1, j, f)
    7.           dfs(n, i-1, j, f)
    8.       if i < j:
    9.           f[2*n-i-j+1] = (i, j-1)
    10.           # print(i, j-1, f)
    11.           dfs(n, i, j-1, f)
    12.       return  # 这里return是因为这是个单向的二叉树，不需要重复计算

n = 4 count = 0 f = [0 for i in range(2*n+1)] f[0] = (n, n) dfs(n, n, n, f) print(f”Count: {count}; Result: {len(f)}”)

  1. 结果：
  2. ```python
  3. [(4, 4), (3, 4), (2, 4), (1, 4), (0, 4), (0, 3), (0, 2), (0, 1), (0, 0)]
  4. [(4, 4), (3, 4), (2, 4), (1, 4), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0)]
  5. [(4, 4), (3, 4), (2, 4), (1, 4), (1, 3), (1, 2), (0, 2), (0, 1), (0, 0)]
  6. [(4, 4), (3, 4), (2, 4), (1, 4), (1, 3), (1, 2), (1, 1), (0, 1), (0, 0)]
  7. [(4, 4), (3, 4), (2, 4), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0)]
  8. [(4, 4), (3, 4), (2, 4), (2, 3), (1, 3), (1, 2), (0, 2), (0, 1), (0, 0)]
  9. [(4, 4), (3, 4), (2, 4), (2, 3), (1, 3), (1, 2), (1, 1), (0, 1), (0, 0)]
  10. [(4, 4), (3, 4), (2, 4), (2, 3), (2, 2), (1, 2), (0, 2), (0, 1), (0, 0)]
  11. [(4, 4), (3, 4), (2, 4), (2, 3), (2, 2), (1, 2), (1, 1), (0, 1), (0, 0)]
  12. [(4, 4), (3, 4), (3, 3), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0)]
  13. [(4, 4), (3, 4), (3, 3), (2, 3), (1, 3), (1, 2), (0, 2), (0, 1), (0, 0)]
  14. [(4, 4), (3, 4), (3, 3), (2, 3), (1, 3), (1, 2), (1, 1), (0, 1), (0, 0)]
  15. [(4, 4), (3, 4), (3, 3), (2, 3), (2, 2), (1, 2), (0, 2), (0, 1), (0, 0)]
  16. [(4, 4), (3, 4), (3, 3), (2, 3), (2, 2), (1, 2), (1, 1), (0, 1), (0, 0)]
  17. Count: 64; Result: 9