程序员的算法趣题Q30: 插线板连接方式

1. 问题描述

本题来自《程序员的算法趣题》中的第30题。

假设有双插口和三插口两种插线板。墙壁上只有一个插座能使用。而需要用电的电器有N台，试考虑如何分配插线板。举个例子，当N=4时，共有4种插线板连接方式（使用同一个插线板，不考虑插口位置的差异，只考虑插线板的连接方法）。另外，要是所有插线板上最后没有多余的插口。N=4时的连接方式如下图所示。

图1 N=4时的连接情况示例（共4种）

求N=20时，插线板的插线连接方式有多少种（不考虑电源功率限制的问题）？

2. 递归表达式

令f(N)表示要用电的电器为N台时的插线连线方式数。

很显然，f(1) = 1，此时直接将设备插在墙壁的插孔上就可以了。

当N>=2时，必须使用插线板来扩容。

第1级插线板有两种情况，即双口插线板或者三口插线板。

Case1: 考虑第1级插线板用双口插线板，假设双口插线板的两个插口下的子网络分别提供k1和k2个有效插口数（插线板自身也要消耗插口数，不算在有效插口数内）。则k1和k2必须满足以下条件：

第一个条件源自于“不能有多余的插口”这一限制条件。进一步，由于“使用同一个插线板，不考虑插口位置的差异，只考虑插线板的连接方法”，即{插口1的子网络提供k1个有效插口数，插口2的子网络提供k2个有效插口数}的连接方法与{插口1的子网络提供k2个有效插口数，插口2的子网络提供k1个有效插口数}视为相同的方案，不重复计算。因此可以不失一般性地假定。

由此可以得到递归表达式：

Case2: 考虑第1级插线板用三口插线板，假设三口插线板的三个插口下的子网络分别提供k1、k2和k3个有效插口数（插线板自身也要消耗插口数，不算在有效插口数内）。则k1、k2和k3必须满足以下条件：

同理可得递归表达式：

最后，N个电器时的总的插线连接方式数为：

以下为几种简单情况的手算结果（可以用于调试参考）：

3. 去重(repetition removal)

但是按照上一节的递归表达式编程计算得到结果（74801991）与原书给出的结果（63877262）不一致！原因在于以上递归计算中漏掉了一些重复的情况。比如说，当一个双口插线板的两个插口分配了相同的负载（即k1=k2）时，这个时候存在一些对称的配置，根据题设要求不能重复计算，需要排除掉。以下分双口插线板和三口插线板两种情况来分别考虑如何去重。

3.1 双口插线板的去重

待追加

3.2 三口插线板的去重

待追加

4. 代码和测试

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 17 13:21:23 2021

@author: chenxy
"""

import time

class Solution:

    def patchPanelConnect(self, num):

        memo = dict()

        def recur(num): # Recursive core
            if num == 0:
                print('patchPanelConnectFast(): invalid input parameter')
            if num == 1:
                #print('patchPanelConnect({0}) = {1}'.format(num,1))
                return 1

            if num in memo:
                return memo[num]
                        
            # using two-port patch panel as the first stage
            sum2 = 0
            for n1 in range(1, num//2+1): 
                for n2 in range(n1, num-n1+1): 
                    if n2 == (num - n1):
                        if n2 == n1:                        
                            sum2 = sum2 + recur(n1) * (recur(n1)+1)/2
                        else:
                            sum2 = sum2 + recur(n1) * recur(n2)
                            
            
            # using three-port patch panel as the first stage
            sum3 = 0
            for n1 in range(1, (num//3+1)): # 
                for n2 in range(n1,(num-n1)//2+1): # 
                    for n3 in range(n2,(num-n1-n2+1)):# n3 = n2,n2+1,...num-n1-n2
                        if n3 == (num - (n1 + n2)):
                            if n1 == n2 and n2 == n3:                            
                                sum3 = sum3 + recur(n1) * (recur(n1)+1) * (recur(n1)+2)/6
                            elif n1 == n2:
                                sum3 = sum3 + recur(n1) * (recur(n1)+1) * recur(n3)/2
                            elif n1 == n3:
                                sum3 = sum3 + recur(n1) * recur(n2) * (recur(n1)+1)/2
                            elif n2 == n3:    
                                sum3 = sum3 + recur(n1) * recur(n2) * (recur(n2)+1)/2                                
                            else:
                                sum3 = sum3 + recur(n1) * recur(n2) * recur(n3)
    
            #print('patchPanelConnect({0}) = {1}'.format(num,(sum2+sum3)))
            memo[num] = (sum2 + sum3)
            return (sum2 + sum3)

        return recur(num)

测试如下：

if __name__ == '__main__':

    sln   = Solution()

    # print('num = 7, ans = ', sln.patchPanelConnect(7))    
    # print('num = 10, ans = ', sln.patchPanelConnect(10))
    
    # Testcase1    
    for num in range(4,21,4):
        tStart = time.time()    
        numOfConnect = sln.patchPanelConnect(num)
        tElapsed = time.time() - tStart        
        print('num = {0:2.0f}, connect methods = {1:8.0f}, tCost = {2:6.3f}(sec)'.format(num, numOfConnect,tElapsed))

运行结果：

num = 4, connect methods = 4, tCost = 0.000(sec)

num = 8, connect methods = 156, tCost = 0.000(sec)

num = 12, connect methods = 9802, tCost = 0.000(sec)

num = 16, connect methods = 750908, tCost = 0.000(sec)

num = 20, connect methods = 63877262, tCost = 0.000(sec)