程序员的算法趣题Q52: 糖果恶作剧

1. 问题描述

假设有N种糖果，每种糖果有M颗。不同种类的糖果有不同颜色的糖纸和不同味道。同种糖果的糖纸可以区分，但是糖果本身无法区分。每颗糖果都用自己匹配的糖纸包裹叫做完全匹配；每颗糖果都用与自己不匹配的糖纸包裹叫做完全错配；介乎于两者之间的叫部分错配。

请问，当N=5，M=6时有多少种完全错配的情况？

注意，即便同种糖果的糖纸也是可以区分，而同种糖果之间不可区分。比如说，‘苹果味的糖纸1包裹草莓味的糖果1’与‘苹果味的糖纸1包裹草莓味的糖果2’就不可区分算作相同的组合；‘苹果味的糖纸1包裹草莓味的糖果1’与‘苹果味的糖纸2包裹草莓味的糖果2’则由于糖纸不同因而是可以区分的。

2. 解题分析

在M=1时，这个问题实质上是一个“错排问题”。等价于“n个人互换礼物，每个人最终拿的都不是原本自己送出的礼物的组合方式一共多少种”的问题。

在M>1时问题变得要复杂得多。考虑动态规划策略，先进行子问题分解。

考虑用candy表示当前各种糖果尚未分配的数量的数组；paper表示各种糖纸尚余数量的数组。各数组的序号可以理解为各种糖果/糖纸的种类序号。以candy和paper联合表示当前分配状态,记为{candy,paper}。比如说，candy=[3,3,3]表示共有3种糖果，且每种有3颗糖果未分配，paper=[3,2,1]则表示0号糖纸还有3张，1号糖纸还有2张，2号糖纸还有1张…

为了方便考虑（但并不失一般性），考虑接下来取candy中尚未分配的糖果中种类序号最低的一枚糖果（可能有多枚，但是同种糖果不能区分所以任取一枚）进行分配，假设为k号糖果，那它可以分配给哪种糖纸呢？假定分配j号糖纸，首先不能是k号糖纸，即j!=k；其次，该j号糖纸必须还有未分配的，即paper[j]>0。做完这枚糖果分配后，分配状态需要如下更新：k号糖果数要减一；j号糖纸数也要减一。然后可以基于更新后的{candy,paper}进行递归调用（solving the sub-problem）。

当前状态{candy,paper}下的分配数等于对所有满足条件的j的子问题解之和。由此可得处理流程（伪代码）如下：

但是以上流程中尚未考虑memoization，实现时需要追加进去，否则的话运行时间会变得无法承受。

【吐槽】老实讲这道题断断续续想了两三天理不清，原书没有解说直接上来一段代码，看半天也没看懂，不是因为Ruby语言的问题，而是确实没有看懂他的思路（廉颇老矣。。。但是不服气）。还是得以自己能够理解的方式想清楚、用自己的语言能解说清楚、并用代码实现了才能有最大的收获。从这个意义上来说，原书解说匮乏以及代码看不懂倒是一件好事，逼着自己只能硬着头皮干。。。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Fri Aug 27 08:41:49 2021

@author: chenxy
"""

"""
import sys
import time
import datetime
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque

class Solution:
    def candyMisMatch(self, N: int, M: int) -> int:
        """
        :N:    The number of the kinds of candy
        :M:    The number of candied for each kind
        :ret:  The total number of complete-mismatch
        """                
        memo = dict()
        def explore(candy, paper):
            # print('explore:', candy, paper)
            if candy[-1] == 0:
                return 1
            
            if tuple(candy+paper) in memo:
                return memo[tuple(candy+paper)]
            
            for k in range(N):
                if candy[k] > 0:
                    break
            sum = 0
            for j in range(N):
                if j!=k and paper[j]>0:
                    candy[k] -= 1
                    paper[j] -= 1
                    sum += explore(candy,paper)
                    candy[k] += 1
                    paper[j] += 1
            memo[tuple(candy+paper)] = sum
            
            return sum
        return explore(N*[M], N*[M])

if __name__ == '__main__':        
            
    sln    = Solution()    

    N, M   = 5,6
    tStart = time.time()
    ans    = sln.candyMisMatch(N,M)
    tCost  = time.time() - tStart
    print('N={0}, M={1}, ans={2}, tCost={3:6.2f}(sec)'.format(N,M,ans,tCost))

运行结果：

N=5, M=6, ans=1926172117389136, tCost= 0.06(sec)