求基于排序4字节二进制IP地址的最多k个子网划分算法

需要开发一种算法，输入为长度为n的已排序列表，列表元素是32位二进制字符串（对应4字节IP地址的二进制形式），要求将其划分为不超过k个子列表（子网），使得每个子列表内的元素拥有尽可能长的公共前缀（即同位置匹配位最多）。

示例1：k=3，n=6 #

输入 #

k = 3
n = 6
binary_strings = [
    "00000000000000000011011000010000",
    "00000000001000000110000001100111",
    "00000000010110000110001111010111",
    "00000000010111010101010001010000",
    "00000011110111101101011111010000",
    "00000011111110000000111100001000",
]

输出 #

00000011110111101101011111010000
00000011111110000000111100001000

00000000010111010101010001010000
00000000010110000110001111010111

00000000000000000011011000010000
00000000001000000110000001100111

示例2：k=2，n=4 #

输入 #

k = 2
n = 4
binary_strings = [
    "00101010101010000000000000101010",
    "10000000000000010000000100000000",
    "11000000101010000000000100000000",
    "11000000110001001100010000000000",
]

输出 #

00101010101010000000000000101010

10000000000000010000000100000000
11000000101010000000000100000000
11000000110001001100010000000000

补充说明 #

• 每个结果子列表本质是一个包含二进制IP地址的子网，目标是生成能适配所有子网的最大可能子网掩码，掩码允许0和1交替（例如"1010"是有效的掩码起始）。
• 以下是生成子网掩码的算法实现：

result_mask = ["." for _ in range(32)]
for subnet in subnets:
    # 转置子网内的二进制字符串，按位分组
    transposed = list(zip(*subnet))
    for j, match in enumerate(transposed):
        # 若当前位所有元素相同
        if len(set(match)) == 1:
            # 仅当该位未被标记为0时，标记为1
            if result_mask[j] != "0":
                result_mask[j] = "1"
        else:
            # 若当前位存在不同元素，标记为0
            result_mask[j] = "0"

result_mask = "".join(result_mask)

内容的提问来源于stack exchange，提问作者banan