目录
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)) == 103. 代码及测试
# -*- 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))
运行结果：
????????nums=8, tCost = ?0.152(sec)
????????(34, 179, 205, 68)
????????(34, 205, 179, 68)
????????(68, 179, 205, 34)
????????(68, 205, 179, 34)
????????(179, 34, 68, 205)
????????(179, 68, 34, 205)
????????(205, 34, 68, 179)
????????(205, 68, 34, 179)
? ? ? ? 上一篇：Q31: 计算最短路径
? ? ? ? 下一篇：Q42: 将牌洗为逆序
????????本系列总目录参见：程序员的算法趣题：详细分析和Python全解