如何排列 5 M、5 S 和 5 T，使得 M 和 T 不相邻并且字符串以 M 开始并以 T 结束

Question

问题 : 5只猴子、5条蛇和5只老虎在一家杂货店里排成一排，同一物种的动物无法区分。一只猴子站在队伍的最前面，一只老虎站在队伍的最后。不幸的是，老虎和猴子是死敌，所以猴子和老虎不能在相邻的地方站成一排。计算线的可能排列数。

手动解决这个问题是一项艰巨的任务。我想写一个程序输出可能的排列，还要统计总的排列。我的第一个想法是使用蛮力。猴子、蛇和老虎可以分别用字母 M、S 和 T 表示。字符串开头为 1 M，结尾为 1 T，则有 13!/(4!4!5!) = 90,090 种可能性。然后我会删除不满足关于邻接的第二个条件的安排。

我的第二个想法是先计算M和T相邻的排列数，然后从90,090中减去这个数。我是编程新手，所以我不知道该怎么做。

是否有更好的方法来解决这些类型的问题？有什么提示吗？谢谢。

Answer 1

在直接写代码之前，只要把纸上的问题解决到阶乘符号，然后你就可以在代码中轻松找到阶乘

先固定前面1只猴子最后1只老虎。

然后尝试修复剩余的老虎，然后在老虎的相邻位置修复蛇，至少一条蛇必须在老虎的相邻位置，然后在蛇的相邻位置修复猴子

Answer 2

TL;DR: python 使用 sympy

的解决方案

import sympy # sympy.ntheory.multinomial_coefficients
import math  # math.comb

def count_monkeytigers(n_monkeys, n_snakes, n_tigers):
  return sum(
    m * math.comb(n_monkeys - 1, mb_minus1) * math.comb(n_tigers - 1, tb_minus1)
    for (mb_minus1, eb, tb_minus1), m in
      sympy.ntheory.multinomial_coefficients(3, n_snakes-1).items()
  )

说明

我们已经知道开头有一个M，结尾有一个T，字符串中有五个S：

  M??  S  ??  S  ??  S  ??  S  ??  S  ??T

因为M和T不能相邻，唯一的分隔方式是用S，你可以把S当作分隔符；五个 S 将字符串切割成 6 个“箱子”。每个bin可以是空的，或者包含一个或多个M，或包含一个或多个T。此外，第一个bin至少包含一个M，最后一个bin至少包含一个T。

要计算字符串的所有排列，我们可以这样做：

循环三胞胎(monkey_bins, empty_bins, tiger_bins)决定有多少箱子有猴子、空箱子或有老虎；
对于循环，我们可以使用bounds 1 <= monkey_bins <= 5; 0 <= empty_bins <= 5 - monkey_bins; tiger_bins = 6 - monkey_bins - empty_bins;
统计在6个bin中选择monkey_bins个bin、empty_bins个bin和tiger_bins个bin的方法数m(Multinomial coefficient);
数一数 monkey_partitions 种将 n_monkeys 'M' 放入 monkey_bins 箱子的方法，每个箱子至少有一个 M（Stars and bars theorem 1）；
计算 tiger_partitions 种将 n_tigers 'T' 放入 tiger_bins 箱子的方法数量，每个箱子至少有一个 T（Stars and bars theorem 1；
将 m * monkey_partitions * tiger_partitions 添加到计数中。

Python 带循环的代码

import math

def multinomial(*params):
  return math.prod(math.comb(sum(params[:i]), x) for i, x in enumerate(params, 1))

def count_monkeytigers(n_monkeys, n_snakes, n_tigers):
  result = 0
  for monkey_bins in range(1, n_snakes + 1):
    for empty_bins in range(0, n_snakes + 1 - monkey_bins):
      tiger_bins = n_snakes + 1 - monkey_bins - empty_bins
      m = multinomial(monkey_bins - 1, empty_bins, tiger_bins - 1) # nb permutations of the 3 types of bins
      monkey_partitions = math.comb(n_monkeys - 1, monkey_bins - 1)
      tiger_partitions = math.comb(n_tigers - 1, tiger_bins - 1)
      result += m * monkey_partitions * tiger_partitions
  return result

print(count_monkeytigers(5, 5, 5))
# 1251

print(count_monkeytigers(2,2,2))
# 3
# = len(['MMSSTT', 'MSMSTT', 'MMSTST'])

multinomial的代码来自这个问题：

请注意，我们在这里仅使用“三项式”系数，因此您可以根据需要将函数 multinomial 替换为这个更简单的函数：

def trinomial(k1,k2,k3):
  return math.comb(k1+k2+k3, k1) * math.comb(k2+k3, k2)

Python 代码使用 `sympy`

在前面的 python 代码中，我们手动遍历可能的三元组（monkey_bins、empty_bins、tiger_bins）并使用相应的二项式系数。事实证明，sympy.ntheory.multinomial_coefficients(m, n) returns 一个字典，其中专门包含那些三元组作为键，相应的多项式系数作为值！我们可以用它来缩短我们的代码：

import sympy # sympy.ntheory.multinomial_coefficients
import math  # math.comb

def count_monkeytigers(n_monkeys, n_snakes, n_tigers):
  return sum(
    m * math.comb(n_monkeys - 1, mb_minus1) * math.comb(n_tigers - 1, tb_minus1)
    for (mb_minus1, eb, tb_minus1), m in
      sympy.ntheory.multinomial_coefficients(3, n_snakes-1).items()
  )

print(count_monkeytigers(5, 5, 5))
# 1251

print(count_monkeytigers(2,2,2))
# 3
# = len(['MMSSTT', 'MSMSTT', 'MMSTST'])

请注意，字典 multinomial_coefficients(3, n) 包含总和为 n 的所有非负数三元组，包括中间元素 empty_bins 等于 n 的那些，以及其他两个元素为 0。但我们希望至少有一个箱子是猴子，至少一个箱子是老虎；因此我将三元组称为 (mb_minus1, eb, tb_minus1) 而不是 (mb, eb, tb)，因此我使用 n_snakes-1 而不是 n_snakes+1 作为三元组的总和。

如何排列 5 M、5 S 和 5 T，使得 M 和 T 不相邻并且字符串以 M 开始并以 T 结束

How to arrange 5 M, 5 S and 5 T such that M and T are not adjacent and string starts with M and ends with T

math

permutation

TL;DR: python 使用 sympy

说明

Python 带循环的代码

Python 代码使用 sympy

Python 代码使用 `sympy`