您当前的位置：首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q40: 优雅的IP地址

时间：12-30来源：作者：点击数：44

1. 问题描述

IPv4 中的 IP 地址是二进制的 32 位数值。不过，这样的数值对我们人类而言可读性比较差，所以我们通常会以 8 位为 1 组分割，用类似 192.168.1.2 这种十进制数来表示它（图 1）。

图 1　IP 地址（IPv4）

这里，我们思考一下十进制数 0~9 这 10 个数字各出现 1 次的 IP 地址（像正常情况一样，省略每组数字首位的 0。也就是说，不能像 192.168.001.002 这样表示，而要像 192.168.1.2 这样来表示）。

问题：求用二进制数表示上述形式的 IP 地址时，能使二进制数左右对称的 IP 地址的个数（用二进制数表示时不省略 0，用完整的 32 位数表示）。

2. 解题分析

2.1 笨办法

10个数共有10!种排列。IPv4的第一个字段允许为0吗？如果不允许的话，则应该是9*9!。注意，题中的要求是省略每组数字首位的 0，但是单独的0至少对于后面几个字段是允许的。这里先假定第一个字段也允许为0，反正只是定性的分析，差异不大。

将每种排列分割成4段，相当于在9个位置种插入3个分割点。如果第一个数是0，则0后面必须放一个分割点，则总共有C(8,2)种分割点放置方式；如果第一个数不是0，则分割必须不出现在0的前面，因此总共有C(8,3)种分割点放置方式。综合考虑有C(8,2)+9*C(8,3)种分割点放置方式。

然后再进一步去判断这每一种分割方式所生成的IP是否符合题设的要求（每个字段必须在[0,255]之间，且转换成32比特二进制表示后左右对称）。

因此总共需要检查(10!)*( C(8,2)+9*C(8,3))= 1930521600种可能的IP。这是一个巨大的数字，有没有办法削减搜索范围？

2.2 逆向思考

IPv4的每个字段为8比特，十进制表示范围是从0~255。以A、B、C、D分别表示第1、2、3、4个字段的十进制表示的话，如果使得整体用32比特表示的二进制为对称的话，则必然A和D、B和C作为8比特的二进制表示分别构成对称对（顺便说一下，原书的提示不知道是不是翻译的问题，说的非常含糊容易引起误导）。因此，事实上只要对两个8比特数的组合进行扫描，对每一种组合在进一步判断十进制表示是不是刚好包含0~9各1个的10个数字。共有256*256=65536种可能的组合，这个组合数远远地小于上一节的方案。

以下代码按照这种思路来实现。其中有一些小巧的细节，说明如下：

(1) 十进制数转换成二进制数用bin()，但是bin()的输出前面包含’0b’前缀。所以后跟[2:]去除这个前缀。如下所示：

Abin = bin(A)[2:]

(2) 求对称的二进制序列。由于bin()的输出可能不满8比特长。但是在判断二进制序列是否相互对称时是考虑双方都是8比特（不足8比特的先头补0），因此在求与A互补的D的二进制表示时首先用Abin[::-1]取Abin的reverse，然后再在尾部根据需要补0（因为A是头部补0）。如下所示：

Dbin = Abin[::-1] + (8-len(Abin))*'0'

(3) 将二进制转换成十进制，int()函数有参数只是原字符串的进制数，二进制的话则设为2.如下所示：

D    = int(Dbin,2)

(4) 判断是否是刚好0~9各包含一个的10个数。将A、B、C、D变成字符串然后串联起来，然后再传换成set（因为set的元素是unique的，自动剔除重复的元素），因此最后只要判断该set的长度是不是10即可。如下所示：

len(set(combinedStr)) == 10

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Fri Sep  3 07:25:27 2021

@author: chenxy
"""

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

class Solution:
    def elegantIP(self) -> int:
        """
        :ret: The total number of IP satisfying the requirement
        """                
        nums = 0
        rsltLst = []
        for A in range(256):
            for B in range(256):
                Abin = bin(A)[2:]
                Bbin = bin(B)[2:]
                Dbin = Abin[::-1] + (8-len(Abin))*'0'
                Cbin = Bbin[::-1] + (8-len(Bbin))*'0'
                D    = int(Dbin,2)
                C    = int(Cbin,2)
                
                combinedStr = str(A)+str(B)+str(C)+str(D)
                if len(set(combinedStr)) == 10:
                    nums = nums + 1
                    rsltLst.append((A,B,C,D))
                    
        return nums, rsltLst
        
if __name__ == '__main__':        
            
    sln    = Solution()            
    
    tStart = time.time()
    nums, rsltLst = sln.elegantIP()
    tCost  = time.time() - tStart
    print('nums={0}, tCost = {1:6.3f}(sec)'.format(nums,tCost))    
    for item in rsltLst:
        print('{0}'.format(item))