Coding-everyday

1. 排列组合

# 1. 排列组合

# 1.1. 走方格

题目描述：在6 * 9的方格中，以左上角为起点，右下角为终点，每次只能向下走或者向右走，请问一共有多少种不同的走法。

思路：一共走13步，其中必然有5步向下，剩下的8步向右。

  5      8
C 13 + C 13 = 1287

# 1.2. 七人站队，保证A在B的左边

题目描述： ABCDEFG七人站队，要求A必须在B的左边，但不要求一定相邻，请问共有多少种排法？如果要求A必须在B的左边，且必须相邻，请问一共有多少种排法？

问题一：不要求相邻的排法？

7!，一半的情况是A在B的左边，一半的情况是B在A的左边，所以：

7! / 2 = 2520 种

问题二：A和B一定相邻，有多少种排法？

将AB看作一个人，那么总共就有6个人，所以：

6! = 720 种

# 1.3. 甲乙、甲丙不相邻

题目描述：六个人排成一排，要求甲乙、甲丙不相邻，请问有多少种排法？

思路：

6个人的全排列总数为6! = 720
甲乙相邻的总数为240种
同理，甲丙相邻的总数为240种
乙甲丙或丙甲乙出现的次数为4! * 2 = 48 种

所以：

720 - 240 - 240 + 48 = 288 种

# 1.4. 分10颗糖果给3个人，每人至少一颗

题目描述： 10颗相同的糖果，分给3个人，每人至少一颗，问有多少种分法？

思路： 10颗糖果中间的位置有9个，所以目标转换为9个空隙中选两个插入插板，所以：

  2
C 9 = 36 种

# 1.5. 10个不同的球放入3个桶里有多少种方法

每个球都要被放进桶里，每个球都有3种可能

3^10 = 59049 种

# 1.6. 十颗糖，每天至少吃一颗，吃完为止，问有多少种不同的吃法？

思路：

如果一天吃完所有的糖，方法有1种
如果两天吃完所有的糖，方法有C(9,1)种
如果三天吃完所有的糖，方法有C(9,2)种
如果四天吃完所有的糖，方法有C(9,3)种

C(N,0) + C(N,1) +…+ C(N,N) = 2的N次方
C(9,0) + C(9,1) +…+ C(9,9) = 2的9次方 = 512 种

# 1.7. 卡特兰数

应用场景：

括号化问题。

矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)

出栈次序问题。

一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?

类似： (1) 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)

(2) 在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。

将多边行划分为三角形问题。

将一个凸多边形区域分成三角形区域的方法数?

类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？

给顶节点组成二叉树的问题。

给定N个节点，能构成多少种形状不同的二叉树？先取一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘，就是h(0)*h(n-1) + h(2)*h(n-2) +…+ h(n-1)h(0)=h(n)（能构成h(N)个）

f(0) = 1
f(1) = 1
f(2) = 2
f(3) = 5
...
f(n) = f(0)*f(n-1)+f(1)*f(n-2)+f(3)*f(n-4)+...+f(n-1)*f(0)
     = (1 / (n + 1)) * C(2*n, n)

C(2*n, n) - C(2*n, n+1) = (1 / (n + 1)) * C(2*n, n)

def solution(n):
  return getCount(2*n, n) / (n+1)


# 获取C(m, n)
def getCount(m, n):
  s, d = 1, 1
  
  for i in range(1, n+1):
    d *= i

  for j in range(m - n + 1, m + 1):
    s *= j

  return s//d

# 1.7.1. 高矮排两排

题目描述：

12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？

给定一个偶数n，请返回所求的排列方式个数。保证结果在int范围内。

思路： 0：在第一排 1：在第二排

任意前缀0的个数不少于1的个数（与括号、栈顺序问题相同），本质上也是一个卡特兰数问题。

# 1.8. 错装信封问题

题目描述：

有n个信封，包含n封信，现在把信拿出来，再装回去，要求每封信不能装回它原来的信封，问有多少种装法?

给定一个整数n，请返回装发个数，为了防止溢出，请返回结果Mod 1000000007的值。保证n的大小小于等于300。

测试样例： 2

返回：1

思路：对于n封信按照题目要求的装法即为f(n) 假设第n封信放入了第i个信封情况一：第i封信也放入了第n个信封，后续为f(n-2) 情况二：第i封信没放入第n个信封，后续为f(n-1)

n封信放入i个信封，i的选择有n-1种所以总数为 f(n) = (n-1)*(f(n-1) + f(n-2))

def env(n):
  res = [0, 0, 1]

  for i in range(n - 2):
    res.append((i + 2) * (res[-1] + res[-2]))
    
  return res[-1]

← math recursion →